屎山BFS 20PTS求条

#include<bits/stdc++.h>
using namespace std;
template<typename T>
class my_queue
{
    public:
    T q[3000009];
    int f,r;
    void push(T val)
    {
        q[++r]=val;
    }
    T pop_and_get()
    {
        return q[++f];
    }
    int size()
    {
        return r-f;
    }
};
struct node
{
    int x,y,dep,rest;
};
struct nod
{
    int x,y;
};
my_queue<node>q;
char f[1009][1009];
bool vis[1009][1009];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>f[i][j];
        }
    }
    vis[1][1]=1;
    q.push({1,1,0,(f[1][1]=='%')*k});
    while(q.size())
    {
        node tmp=q.pop_and_get();
        if(tmp.x==n&&tmp.y==n){cout<<tmp.dep<<endl;return 0;}
        nod tmp2={tmp.x-1,tmp.y};
        if(f[tmp2.x][tmp2.y]!='#' && !vis[tmp2.x][tmp2.y])
        {
            if(f[tmp2.x][tmp2.y]=='%'){q.push({tmp2.x,tmp2.y,tmp.dep+1,k});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='X'&&tmp.rest>0){q.push({tmp2.x,tmp2.y,tmp.dep+1,tmp.rest-1});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='.'){q.push({tmp2.x,tmp2.y,tmp.dep+1,max(tmp.rest-1,0)});vis[tmp2.x][tmp2.y]=1;}
        }
        tmp2={tmp.x+1,tmp.y};
        if(f[tmp2.x][tmp2.y]!='#' && !vis[tmp2.x][tmp2.y])
        {
            if(f[tmp2.x][tmp2.y]=='%'){q.push({tmp2.x,tmp2.y,tmp.dep+1,k});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='X'&&tmp.rest>0){q.push({tmp2.x,tmp2.y,tmp.dep+1,tmp.rest-1});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='.'){q.push({tmp2.x,tmp2.y,tmp.dep+1,max(tmp.rest-1,0)});vis[tmp2.x][tmp2.y]=1;}
        }
        tmp2={tmp.x,tmp.y-1};
        if(f[tmp2.x][tmp2.y]!='#' && !vis[tmp2.x][tmp2.y])
        {
            if(f[tmp2.x][tmp2.y]=='%'){q.push({tmp2.x,tmp2.y,tmp.dep+1,k});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='X'&&tmp.rest>0){q.push({tmp2.x,tmp2.y,tmp.dep+1,tmp.rest-1});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='.'){q.push({tmp2.x,tmp2.y,tmp.dep+1,max(tmp.rest-1,0)});vis[tmp2.x][tmp2.y]=1;}
        }
        tmp2={tmp.x,tmp.y+1};
        if(f[tmp2.x][tmp2.y]!='#' && !vis[tmp2.x][tmp2.y])
        {
            if(f[tmp2.x][tmp2.y]=='%'){q.push({tmp2.x,tmp2.y,tmp.dep+1,k});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='X'&&tmp.rest>0){q.push({tmp2.x,tmp2.y,tmp.dep+1,tmp.rest-1});vis[tmp2.x][tmp2.y]=1;}
            if(f[tmp2.x][tmp2.y]=='.'){q.push({tmp2.x,tmp2.y,tmp.dep+1,max(tmp.rest-1,0)});vis[tmp2.x][tmp2.y]=1;}
        }
        ///cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.rest<<endl;
    }
    cout<<-1;
}