这题是一个大坑。
首先我们想到了BFS，这个题就是一个简单到不能再简单的Maze加上传送门就是了。
但是有一点是传送门不费时啊！！什么鬼。所以我们要先判传送门
为什么呢？我记得有一组测试数据包括了这种情况
这不清真
另外，好像还有一个点是全都是传送门的情况。
这也不清真
先判传送门（并不是判队首元素位于传送门，而是队首坐标移动之后），传送过去之后耗时不加，队列保存传送后的位置，这样就不会产生无限传送死循环的问题。
但是关于情况2怎么办？我们利用BFS的性质，把传送门（传过去之后）打上标记，然后就不用他了。（每一次用都是最早用他）
传送门I hate you
读入的时候记录传送门的相对坐标，像这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
scanf("%s",&mapx[i]); for (int j=0;j<m;j++) { if (mapx[i][j]=='=') { ex=i;ey=j; } else if (mapx[i][j]=='@') { sx=i;sy=j; } else if (mapx[i][j]>='A' && mapx[i][j]<='Z') { if (toit[mapx[i][j]-65][0][0]==-1) { toit[mapx[i][j]-65][0][0]=i; toit[mapx[i][j]-65][0][1]=j; } else toit[mapx[i][j]-65][1][0]=i; toit[mapx[i][j]-65][1][1]=j; } } |
之后碰到传送门直接查表。，顺便记下起点sxsy和重点exey
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<queue> #include<map> #include<algorithm> using namespace std; queue<int>quex,quey; int cachex,cachey; char mapx[400][400]={0}; int sx,sy,ex,ey,n,m; int head=0,tail=1; int timex[100000]={0},toit[50][2][2]; bool checked[400][400]={false}; int wayx[4]={-1,0,1,0},wayy[4]={0,1,0,-1}; int main() { memset(toit,-1,sizeof(toit)); scanf("%d%d",&amp;n,&amp;m); for (int i=0;i<n;i++) { scanf("%s",&amp;mapx[i]); for (int j=0;j<m;j++) { if (mapx[i][j]=='=') { ex=i;ey=j;} else if (mapx[i][j]=='@') { sx=i;sy=j;} else if (mapx[i][j]>='A' &amp;&amp; mapx[i][j]<='Z') { if (toit[mapx[i][j]-65][0][0]==-1) toit[mapx[i][j]-65][0][0]=i; toit[mapx[i][j]-65][0][1]=j; else toit[mapx[i][j]-65][1][0]=i; toit[mapx[i][j]-65][1][1]=j; } } } quex.push(sx); quey.push(sy); timex[1]=0; while (quex.size()>0) { head++; cachex=quex.front(); cachey=quey.front(); if (mapx[cachex][cachey]=='=') { printf("%d\n",timex[head]); return 0; } for (int i=0;i<=3;i++) if (cachex+wayx[i]>=0 &amp;&amp; cachex+wayx[i]<n &amp;&amp; cachey+wayy[i]>=0 &amp;&amp; cachey+wayy[i]<m) { if (mapx[cachex+wayx[i]][cachey+wayy[i]]>='A' &amp;&amp; mapx[cachex+wayx[i]][cachey+wayy[i]]<='Z' &amp;&amp; checked[cachex+wayx[i]][cachey+wayy[i]]==false) { if (cachex+wayx[i]==toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][0] &amp;&amp; cachey+wayy[i]==toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][1]) { tail++; quex.push(toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][1][0]); quey.push(toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][1][1]); timex[tail]=timex[head]+1; checked[cachex+wayx[i]][cachey+wayy[i]]=true; //cout<<"A "<<"X= "<<toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][1][0]<<" Y= "<<toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][1][1]<<" Timex= "<<timex[tail]<<" X= "<<cachex<<" Y= "<<cachey<<endl; } else { tail++; quex.push(toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][0]); quey.push(toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][1]); timex[tail]=timex[head]+1; checked[cachex+wayx[i]][cachey+wayy[i]]=true; //cout<<"B "<<"X= "<<toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][0]<<" Y= "<<toit[mapx[cachex+wayx[i]][cachey+wayy[i]]-65][0][1]<<" Timex= "<<timex[tail]<<" X= "<<cachex<<" Y= "<<cachey<<endl; } } else if (mapx[cachex+wayx[i]][cachey+wayy[i]]!='#' &amp;&amp; checked[cachex+wayx[i]][cachey+wayy[i]]==false) { tail++; quex.push(cachex+wayx[i]); quey.push(cachey+wayy[i]); timex[tail]=timex[head]+1; checked[cachex+wayx[i]][cachey+wayy[i]]=true; //cout<<"X= "<<cachex+wayx[i]<<" Y= "<<cachey+wayy[i]<<" Timex= "<<timex[tail]<<endl; } } quex.pop(); quey.pop(); } return 0; } |
其实这个题处理好了传送门，你会发现，其实不难……（输出调试大法好）
记得用checked数组标记已经访问的点和传送门，要不无限使用传送门
。。。我来踩踩