题解 | #迷宫#

使用int visit[505][505][2];来实现分类讨论（当拿到钥匙之后就清零此路径的检查数组）
我的方法就是自己想的一个思路：
将分类讨论简化了 争对与这道题的简化 可能其他题就不行了
我认为首先肯定需要检查是否走过（visit数组），而且需要bfs的框架
分析：
如果不设置检查机制肯定不行（如果压根就不能出去那么就会一直循环） 如果老方法设置也不行（比如必须要钥匙，但钥匙在出口反方向那就不能返回了）
我们分析会知道如果拿到钥匙，我们把检查是否走过全部清零不就可以找到出口了嘛！（但这会影响不拿钥匙的检查呀） 所以我就用两个检查数组解决（一个是不走钥匙这条路 一个是拿到钥匙之后）

#include <iostream>
#include <queue>
using namespace std;
char place[505][505];
int visit[505][505][2];
struct Step{
    int x,y,steps;
    bool has_key;//是否有钥匙
    //构造函数
    Step(int xx,int yy,int ss,bool hh):x(xx),y(yy),steps(ss),has_key(hh){}
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<Step> q;
int main()
{
    int H,W,x,y;
    cin>>H>>W;
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++){
            cin>>place[i][j];
            if(place[i][j]=='S'){
                x=i;y=j;
            }
        }
    q.push(Step(x,y,0,false));
    visit[x][y][0]=1;
    while(!q.empty()){
        Step s=q.front();
        int step=s.steps+1;
        if(place[s.x][s.y]=='E'){
            cout<<s.steps<<endl;
            return 0;
        }
        for(int i=0;i<4;i++){
            int tox=s.x+dx[i];
            int toy=s.y+dy[i];
            if(place[tox][toy]=='W')continue;
            if(s.has_key){
                if(visit[tox][toy][1]==1)continue;
            }else{
                if(visit[tox][toy][0]==1)continue;
            }
            if(place[tox][toy]=='D'){
                if(s.has_key){
                    q.push(Step(tox,toy,step,s.has_key));
                    visit[tox][toy][1]=1;
                }
                continue;
            }
            if(place[tox][toy]=='K'){
                q.push(Step(tox,toy,step,true));
                visit[tox][toy][0]=1;
                visit[tox][toy][1]=1;
                continue;
            }
            q.push(Step(tox,toy,step,s.has_key));
            if(s.has_key){
                visit[tox][toy][1]=1;
            }else{
                visit[tox][toy][0]=1;
            }
        }
        q.pop();
    }
    cout<<"-1"<<endl;
    return 0;
}