题目大意

一个迷宫中，四面都是墙（W），起点(S)、终点(E)、钥匙(K)、门(D)各只出现一次，寻找最短路径

难点

在寻找最短路径的同时如果会遇到钥匙再走会经过门的最短路，否则continue(直接不走门)，等到遇到钥匙再走门

学会的技巧

不仅可以用dist来标记是否走过某个点和记录路径长度，还可以写结构体来记录，并且利用三维vis数组就可以很方便记录行到当前点时是否有钥匙

#include<bits/stdc++.h>
using namespace std;
int h,w;
int sx,sy,ex,ey;
char g[510][510];
bool vis[510][510][2];//利用三维数组不仅能判断某点是否走过 还能判断是否携带钥匙
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};


struct Node{
    int x,y;
    int step; //记录路径长度 无需另外的变量记录
    int key; //记录是否有钥匙
};


int bfs(){
    queue<Node>q;
    q.push({sx,sy,0,0});
    vis[sx][sy][0]=1;
    while(!q.empty()){
        Node cur=q.front();
        q.pop();
        if(cur.x==ex&&cur.y==ey) return cur.step;
        for(int i=0;i<4;++i){
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            int KeyPoint=cur.key;
            int step=cur.step;
            if(nx<0||nx>=h||ny<0||ny>=w||g[nx][ny]=='W') continue;
            if(g[nx][ny]=='K') KeyPoint=1;
            if(g[nx][ny]=='D'&&KeyPoint==0) continue;
            if(!vis[nx][ny][KeyPoint]){
                q.push({nx,ny,step+1,KeyPoint});
                vis[nx][ny][KeyPoint]=1;
            }
        }
    }
    return -1;
}


int main(){
    cin>>h>>w;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            cin>>g[i][j];
            if(g[i][j]=='S'){
                sx=i;
                sy=j;
            }
            else if(g[i][j]=='E'){
                ex=i;
                ey=j;
            }
        }
    }
    cout<<bfs()<<endl;
    return 0;
}