NC15136. 迷宫
描述
这是一个关于二维迷宫的题目。我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。
本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。
请问，从起点到终点，最少要走几步呢？
输入描述
输入的第一行有两个正整数H, W，分别代表迷宫的长跟宽。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含`'S'`, `'E'`, `'W'`, `'D '`, `'K'`, `'.'`这几种字元。
输出描述
请在一行中输出一个整数代表答案，如果无法从起点走到终点，请输出-1。
示例1
输入:
4 12 WWWWWWWWWWWW WE.W.S..W.KW W..D..W....W WWWWWWWWWWWW
输出:
20
示例2
输入:
6 6 WWWWWW WEWS.W W.WK.W W.WD.W W.W..W WWWWWW
输出:
-1
C++(clang++ 11.0.1) 解法, 执行用时: 9ms, 内存消耗: 1192K, 提交时间: 2022-09-05 17:11:12
#include<bits/stdc++.h>
using namespace std;
int n,m;
char str[505][505];
bool Q[505][505][2];
struct node{int x,y,p,step;};
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
queue<node>q;
int f1(int sx,int sy){
Q[sx][sy][0]=1;
q.push((node){sx,sy,0,0});
while(!q.empty()){
node now=q.front();q.pop();
int x=now.x,y=now.y,p=now.p,step=now.step;
if(str[x][y]=='E')return step;
for(int i=0;i<4;i++){
int X=x+dx[i],Y=y+dy[i],P=p;
if(str[X][Y]=='K')P=1;
if(Q[X][Y][p]||str[X][Y]=='W'||(str[X][Y]=='D'&&!p))continue;
Q[X][Y][p]=1;
q.push((node){X,Y,P,step+1});
}
}
return -1;
}
int main(){
scanf("%d%d",&n,&m);
int sx,sy;
for(int i=1;i<=n;i++){
scanf("%s",str[i]+1);
for(int j=1;j<=m;j++)if(str[i][j]=='S')sx=i,sy=j;
}
printf("%d\n",f1(sx,sy));
return 0;
}