C++ BFS解决迷宫问题

解题思路:本题相比普通的迷宫问题 多了一个无敌道具和陷阱 所以普通的bool数组没办法判断是否应该走这个格子，所以可以改用int 数组记录当前这个格子走过的最大无敌数值（当无敌时间超过这个vis数组记录的值时才将这个格子压入队列中）

注意事项:

参考代码:

#include<bits/stdc++.h>

#define DZT ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define N 1005

using namespace std;

typedef struct NODE{

    int x,y,step,invi;

}NODE;

typedef pair<int,int> pii;

pii ch[4]={{0,1},{1,0},{-1,0},{0,-1}};

char ma[N][N];

int vis[N][N];//判断是否应该回到这个点 当剩余无敌步数大于vis记录的结果时候 才走

int n,k;

queue<NODE> q;//用于广度优先搜索

bool check(const int& x,const int& y){//判断有没有超出边界 以及是不是墙体

    return x>=1 and x<=n and y>=1 and y<=n and ma[x][y]!='#';

}

int main()

{   DZT;

    cin>>n>>k;

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

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

            cin>>ma[i][j];

        }

    }

    memset(vis,-1,sizeof(vis));

    q.push({1,1,0,0});

    vis[1][1]=0;

    while(!q.empty()){

        auto temp=q.front(); q.pop();

        if(temp.x==n &&temp.y==n){

            cout<<temp.step<<endl;

            return 0;

        }

        for(int i=0;i<4;i++){

            int t_x=ch[i].first; int t_y=ch[i].second;

            t_x+=temp.x;t_y+=temp.y;

            //判读 X % 以及对于普通路

            if(ma[t_x][t_y]=='X'&&temp.invi==0){//没有无敌了 有无敌就正常压入队列

                continue;

            }

            int t_invi=max(0,temp.invi-1);//更新无敌时间

            if(ma[t_x][t_y]=='%'){

                t_invi=k;

            }

            if(check(t_x,t_y)&&t_invi>vis[t_x][t_y]){//判断需不需要回走

                vis[t_x][t_y]=t_invi;

                q.push({t_x,t_y,temp.step+1,t_invi});

            }

        }

    }

    return 0;

}