转换成每一步代价不等的最短路问题，采用优先队列（堆）解决

解题思路:

设堆顶的状态为x,y,fat,time。那么从x,y向四个方向搜索下一个点tx,ty时，有的方向会因为肥胖问题无法移动，这时我们减小身材，让他能达到tx,ty这个点（注意身材减小为1时，一定能自由的到达下一个点），可这个过程会导致一个问题,减小身材必须要原地等,因此若减小身材之后到达tx,ty这个点，那么这一步的代价不为1，所以我们无法用普通的队列，改用优先队列。如果还不理解，我举个例子：k=5,设四个方向的下一个点分别为1,2,3,4，且当前fat=5，time=1。其中1，2这两个点当前身材可以过去，那么就往堆里插入（1,fat,time+1），（2，fat,time+1)。3这个点只有当fat=3时可以过去，那么就先在原地等到5，再花费一个时间到达3，向堆里插入（3,3,6)，这就相当于从当前点花费了5个时间单位到达了3。同理，发现4必须身材为1时可以过去，那么就像堆里插入(4,1,11(2*k+1))，相当于花费了10个时间到达这一点。这就转化成了步长不同的bfs搜索了，直接上队列。

注意事项:

起点为3,3。不代表只能走(3,3)-(n-2,n-2)这个区域，别的区域也可以走，因为身材瘦了就可以走了。被这个bug卡了很久

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=505;

char  a[N][N];

int qz[N][N];

int n,k;

int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct rec{

    int x,y,fat,time;

    rec(){}

    rec(int a,int b,int c,int  d)

    {

        x=a;

        y=b;

        fat=c;

        time=d;

    }

    bool operator <(const rec &x) const

    {

        return time>x.time;

    }

};

bool v[N][N];

priority_queue<rec> q;

int main()

{

    cin>>n>>k;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

    {

        cin>>a[i][j];

        qz[i][j]=qz[i-1][j]+qz[i][j-1]-qz[i-1][j-1]+(a[i][j]=='+'?1:0);

    }

    q.push(rec(3,3,5,0));

    v[3][3]=1;

    int cnt=0;

    while(q.empty()==0)

    {

        rec temp=q.top();

        q.pop();

        /*

        cnt++;

        if(cnt>100) break;*/

        //cout<<temp.x<<' '<<temp.y<<' '<<temp.fat<<' '<<temp.time<<endl;

        if(temp.x==n-2&&temp.y==n-2) {cout<<temp.time<<endl;break;}

        if(temp.time==k) temp.fat=3;

        if(temp.time==2*k) temp.fat=1;

        bool flag=0;

        for(int d=0;d<4;d++)

        {

            int tx=temp.x+dir[d][0],ty=temp.y+dir[d][1];

            if(tx>=1&&tx<=n-2&&ty>=1&&ty<=n-2&&v[tx][ty]==0)

            {

                int yxx=tx+temp.fat/2,yxy=ty+temp.fat/2,zsx=tx-temp.fat/2,zsy=ty-temp.fat/2;

                if(qz[yxx][yxy]-qz[yxx][zsy-1]-qz[zsx-1][yxy]+qz[zsx-1][zsy-1]==temp.fat*temp.fat)

                {

                    v[tx][ty]=1;

                    q.push(rec(tx,ty,temp.fat,temp.time+1));

                    flag=1;

                }

                else

                {

                    if(temp.fat==5)

                    {

                        int yxx=tx+1,yxy=ty+1,zsx=tx-1,zsy=ty-1;

                        if(qz[yxx][yxy]-qz[yxx][zsy-1]-qz[zsx-1][yxy]+qz[zsx-1][zsy-1]==3*3)

                        {

                            q.push(rec(tx,ty,3,k+1));

                            v[tx][ty]=1;

                            flag=1;

                        }

                        else

                        {

                            if(a[tx][ty]=='+')

                            q.push(rec(tx,ty,1,2*k+1));

                            v[tx][ty]=1;

                            flag=1;

                        }

                    }

                    else if(temp.fat==3)

                    {

                        if(a[tx][ty]=='+')

                            {

                                q.push(rec(tx,ty,1,2*k+1));

                                v[tx][ty]=1;

                                flag=1;

                            }

                    }

                }

            }

        }

    }

    return 0;

}