upc 走迷宫 bfsDaNIelLAk的博客-

走迷宫
时间限制: 1 Sec 内存限制: 128 MB

题目描述
邪恶的Pcf把KeineDuck关在了一个迷宫中！KeineDuck必须找到一条通往出口的道路。
方便起见，我们将迷宫描述成了一个n行m列的网格，网格中每个格子都有一个特殊的字符：
• #表示这是一堵墙，不能通过。
• @:KeineDuck当前位置。
• =:迷宫的出口。
• 字母A 字母Z:传送装置，它们总是成对出现的。若KeineDuck走到其中一个传送装置上，她会立马传送到另一个传送装置。
假设KeineDuck每次移动都会消耗一单位的时间，现在，她想知道，最少要多少时间才能走到出口。
输入
第一行两个整数n，m，表示行数和列数。
接下来n行，每行m个字符，具体内容参考题目描述。
输出
一个整数，表示最少的时间。
特别地，若没有任何一条到达出口的路径，输出-1。
样例输入 Copy
5 6
###=##
#.W.##
#.####
#.@W##

样例输出 Copy
3
提示
样例解释
KeineDuck先向左移动一步，传送到另一个W上。
KeineDuck再向右移动一步、向上移动一步，达到终点。
总共使用了3s。
对于10%的数据，n=m=2。
对于另外40%的数据，没有传送装置。
对于另外20%的数据，只有一对传送装置。
对于100%的数据，最多有26对传送装置，n,m≤300。

题意就是给你个矩阵，让后求从起点到终点的最短距离。
看起来很简单。。一开始没想那么多，先WA一发。让后仔细想了想传送门可能用两次，但是传统的 bfs 路径标记后每个点只能遍历一次。所以就想把能到的传送门距离预处理出来，做一个多源bfs，处理方法很繁琐，细节很多，写了很长时间，需要俩bfs，而且跑到91就跑不动TLE了，所以还需要换一个。那现在想想是否可以不对路径标记，而直接记录到达每个点的距离，让后把能 扩展状态 的条件改成 当当前步数小于以前到达这个点的步数，那就可以更新这个点到其他点的距离了。好像有点像dijkstra？
其实也没有那么难，是我想麻烦了，代码还是很简单的。。

#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #define X first #define Y second using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=310,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6; int n,m; int ex,ey,cnt[N][N]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; char mp[N][N]; vector<PII>v[N]; struct Node { int x,y; int step; }; bool check(int x,int y) { if(mp[x][y]=='#'||x<1||x>n||y<1||y>m) return true; return false; } void bfs(int x,int y) {  queue<Node>q;  q.push({x,y,0}); while(q.size()) {   Node t=q.front();   q.pop(); int s=t.step+1; if(cnt[ex][ey]!=INF) return; for(int i=0;i<4;i++) { int dx=t.x+dir[i][0]; int dy=t.y+dir[i][1]; if(check(dx,dy)) continue; if(isalpha(mp[dx][dy]))//传送到相应位置  { char ch=mp[dx][dy]; int x1=v[ch][0].X,y1=v[ch][0].Y; int x2=v[ch][1].X,y2=v[ch][1].Y; if(dx==x1&&dy==y1)      dx=x2,dy=y2; else dx=x1,dy=y1; } if(s<cnt[dx][dy]) {     cnt[dx][dy]=s;     q.push({dx,dy,s}); } } } } int main() { // ios::sync_with_stdio(false); // cin.tie(0); memset(cnt,0x3f,sizeof cnt); int x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",mp[i]+1); for(int j=1;j<=m;j++) if(mp[i][j]=='@')     x=i,y=j; else if(mp[i][j]=='=')     ex=i,ey=j; else if(mp[i][j]!='.'&&mp[i][j]!='#')     v[mp[i][j]].push_back({i,j}); } bfs(x,y); if(cnt[ex][ey]==INF) puts("-1"); else printf("%dn",cnt[ex][ey]); return 0; }