题目描述
link
思路
如果没有传送门的话，这就是一个 BFS 板子题，但是传送门该如何处理呢？
大概就是更新四方向的时候，加上一个是否为传送门的判断，是传送门的话就传过去
细节0
参考文献
传送门可以多次经过，例如
##=## ##.## ##A## #@.## ##### ##A.# #####细节1
传送操作不能连续使用，即，传送一次之后，必须通过非传送方式移动至少一步才能再次进行传送。
看下面这个例子：
12345 1 ##=## 2 ##.## 3 ##B## 4 #AB## 5 ##.A# 6 ###@#从( 5 , 4 ) (5,4)(5,4)传送到( 4 , 2 ) (4,2)(4,2)之后，不能再回到( 5 , 4 ) (5,4)(5,4)，但是可以先走一步到( 4 , 3 ) (4,3)(4,3)，然后再传送
代码
#include<iostream>#include<cstdio>#include<vector>#include<queue>usingstd::queue;usingstd::vector;usingstd::pair;structnode{intx,y,cnt;};constintdx[]={-1,0,1,0};constintdy[]={0,-1,0,1};constintN=305;intn,m;charc[N][N];intsx,sy,ex,ey;vector<pair<int,int>>doors[26];//每个字母对应的两个传送门坐标boolvis[N][N];pair<int,int>getdoor(intx,inty){//传送过去后的坐标autopii=doors[c[x][y]-'A'][0];if(pii==std::make_pair(x,y))returndoors[c[x][y]-'A'][1];returnpii;}intbfs(){queue<node>q;q.push({sx,sy,0});vis[sx][sy]=true;while(q.size()){node ff=q.front();q.pop();if(ff.x==ex&&ff.y==ey)returnff.cnt;for(inti=0;i<4;i++){intxx=ff.x+dx[i],yy=ff.y+dy[i];if(xx<1||xx>n||yy<1||yy>m||c[xx][yy]=='#'||vis[xx][yy])continue;if(isupper(c[xx][yy])){autopii=getdoor(xx,yy);intxxx=pii.first,yyy=pii.second;q.push({xxx,yyy,ff.cnt+1+0});//+1是到传送门，+0是传送}else{vis[xx][yy]=true;q.push({xx,yy,ff.cnt+1});}}}return-1;}intmain(){scanf("%d%d\n",&n,&m);for(inti=1;i<=n;i++){scanf("%s",c[i]+1);for(intj=1;j<=m;j++){if(c[i][j]=='@'){sx=i;sy=j;}elseif(c[i][j]=='='){ex=i;ey=j;}elseif(isupper(c[i][j]))doors[c[i][j]-'A'].emplace_back(i,j);}}printf("%d",bfs());return0;}
