标签：tx ty int 迷宫 st push NC15136 else
题目
- 原题地址：迷宫
- 题目编号：NC15136
- 题目类型：BFS
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 262144K，其他语言524288K
1.题目大意
- 从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数
2.题目分析
- 找到k之前，走过的地方变成D
- 找到k之后，走过的地方变成W
3.题目代码
#include <bits/stdc++.h>
using namespace std;
int h, w, k, kk, x, y, st, ans;
char m[502][502];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
struct node{ int x,y,sp,f;};
queue<node> q;
int bfs() {
q.push({k,kk,0,0}), m[k][kk]='D';
int fl = 0;
while(q.size()){
auto z = q.front();
q.pop(), x = z.x, y = z.y, st = z.sp;
for(int i=0;i<4;i++) {
int tx = x + dir[i][0], ty = y + dir[i][1];
if(tx<0||ty<0||tx>=h||ty>=w||m[tx][ty]=='W') continue;
else if(m[tx][ty]=='E') return st+1;
else if(m[tx][ty]=='K'){fl=1,m[tx][ty]='W',q.push({tx,ty,st+1,fl});}
else if(m[tx][ty]=='D'){if(z.f)m[tx][ty]='W',q.push({tx,ty,st+1,fl});}
else if(m[tx][ty]=='.'){if(z.f)m[tx][ty]='W',q.push({tx,ty,st+1,1});
else m[tx][ty]='D',q.push({tx,ty,st+1,0});}
}
}
return -1;
}
int main() {
cin >> h >> w;
for(int i=0;i<h;i++) for(int j=0;j<w;j++){
cin >> m[i][j];if(m[i][j]=='S') k=i,kk=j;
}
cout << bfs() << endl;
}
标签：tx,
ty,
int,
迷宫,
st,
push,
NC15136,
else
From： https://www.cnblogs.com/zhangyi101/p/16657689.html