题解思路（按做题啵啵啵流程）

一、看到“最少走几步”
先想到： BFS 最短路

因为：每走一步代价都一样

所以：第一次到终点,一定是最短步数

二、普通 BFS 够不够？

普通 BFS 状态：(x,y) 表示：人在什么位置
但这题有：钥匙 K,门 D. 有没有钥匙会影响后面能不能走
所以：同一个位置可能有不同意义

例如：
(3,5,没钥匙)
(3,5,有钥匙)

未来能走的路不同。因此：必须把“钥匙状态”加入 BFS。
三、状态设计

        我们定义：x,y -> 当前位置
                          step -> 已经走了几步

                          key -> 有没有钥匙

即为：
struct Node{
int x,y,step,key;

};

四、vis 为什么三维

同一个点，可能有两种状态，所以用vis[x][y][k]

例如：

vis[x][y][0] （没钥匙来过）

vis[x][y][1] （有钥匙来过）

五、BFS 转移流程

每次从队列取出当前状态：

当前位置
当前步数
是否有钥匙

然后：
1. 枚举四个方向：上下左右
2. 墙不能走
3. 门的判断
        如果：
            下一格是 D
            并且没有钥匙

则不能进入。

4. 判断是否拿到钥匙

        如果到K：则下一状态变成有钥匙
5. 判重
        如果：这个状态以前出现过，就不需要再搜索。
6. 入队
        新的状态进入队列继续 BFS。

六、代码

#include<bits/stdc++.h>
using namespace std;
const int N=505;
char g[N][N]; // 地图
int h,w; // 地图高度和宽度
int sx,sy; // 起点坐标
// vis[x][y][k]
// k=0 表示没拿钥匙到达这里
// k=1 表示拿了钥匙到达这里
bool vis[N][N][2];
// 四个方向
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
// BFS队列中的状态
struct Node{
int x,y; // 当前坐标
int step; // 走了多少步
int key; // 是否拿到钥匙
};
void bfs(){
queue<Node> q;
// 从起点开始
q.push({sx,sy,0,0});
// 起点且没钥匙的状态标记已访问
vis[sx][sy][0]=1;
while(!q.empty()){
auto t=q.front();
q.pop();
int x=t.x;
int y=t.y;
int step=t.step;
int key=t.key;
// 到达终点
if(g[x][y]=='E'){
cout<<step;
return;
}
// 枚举四个方向
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
// 墙不能走
if(g[nx][ny]=='W') continue;
// 门D必须有钥匙才能进
if(g[nx][ny]=='D' && key==0) continue;
// 默认钥匙状态不变
int nkey=key;
// 如果遇到钥匙K
// 更新成已经拿到钥匙
if(g[nx][ny]=='K') nkey=1;
// 这个状态访问过
if(vis[nx][ny][nkey]) continue;
// 标记访问
vis[nx][ny][nkey]=1;
// 加入队列
q.push({nx,ny,step+1,nkey});
}
}
// 无法到达终点
cout<<-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;
}
}
}
bfs();
}

题解 | #迷宫#

题解思路（按做题啵啵啵流程）