2018年 蓝桥杯 国赛 迷宫与陷阱

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,k; 
char g[N][N];
bool st[N][N][12]; //表示(a,b)点在无敌值为k的时候是否走过 

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

struct node
{
    int x,y; //(x,y)表示坐标
    int k,step; //k表示走到(x,y)这个点时的无敌值,step表示步数   
};

int bfs() //有特殊情况的bfs 
{
    queue<node> q;
    q.push({1,1,0,0}); //从左上角开始走 

    memset(st,0,sizeof st);
    st[1][1][0]=true; 

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        if(t.x==n && t.y==n) return t.step; //到达终点返回答案 

        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a>=1&&a<=n&&b>=1&&b<=n&&g[a][b]!='#')
            {
                //如果是无敌道具且未获得无敌状态 
                if(g[a][b]=='%' && st[a][b][k]==false)
                {
                    st[a][b][k]=true; //标记获得无敌状态 
                    q.push({a,b,k,t.step+1}); //无敌值为k,步数加一 
                }

                //如果是陷阱或普通格,处于无敌状态并且未走过 
                else if((g[a][b]=='X' || g[a][b]=='.') && t.k && st[a][b][t.k-1]==false)
                {
                    st[a][b][t.k-1]=true; //标记已走过 
                    q.push({a,b,t.k-1,t.step+1}); //无敌值减一,步数加一 
                }

                //如果是普通格,无敌值为0且为未走过 
                else if(g[a][b]=='.' && t.k==0 && st[a][b][0]==false)
                {
                    st[a][b][0]=true; //标记已走过 
                    q.push({a,b,0,t.step+1}); //无敌值为0,步数加一 
                }
            }
        }
    }
    return -1; //无法到达终点 
}

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];

        cout<<bfs()<<endl;

    return 0;
}