题目链接：http://acm.csust.edu.cn/problem/3023
Description
“他的邪恶乃是一个传奇。他是亡灵天灾的君王，是符文圣剑霜之哀伤的主人，是艾泽拉斯世界一切自由族类的大敌。
巫妖王是无与伦比的强大力量与极端冷酷的化身，他比寒冰更加寒冷的灵魂已经被他的宏大计划彻底吞噬。
在这个计划中，他将毁灭世界上的全部生灵。
巫妖王-阿尔萨斯已经启动了可能导致艾泽拉斯所有生灵毁灭的计划，他的天灾军团和驱役亡灵的强大力量将横扫整个世界。
我们可以将艾泽拉斯视为n∗m的矩阵，其中
S：寒冰王座，起点
T：暴风城，终点
*：平原，天灾军团可以到达的地方
#：沼泽，天灾军团无法到达的地方
在地图上存在着k个传送门，借助传送门，可以瞬间（不花费时间地）从传送门的任一端到达另一端
天灾军团每小时可以向其周围4个方向移动一格（上下左右），为了保证天灾军团随时保持最高战斗力，巫妖王命令军队每行军8小时，就原地休息1小时。
现在巫妖王率领他的天灾军团从S出发，问最快多久可以到达T？
Input
第1行两个整数n,m (1≤n,m≤1000，且n,m不同时等于1)
第2~n+1行每行含有m个字符，其中：
第n+2行有一个整数k（0≤k≤10）
随后k行，每行包含4个整数x1,y1,x2,y2表示传送门两端的坐标(x1,y1),(x2,y2)
（1≤x1,x2≤n，1≤y1,y2≤m）
（注意，传送门也可以直接存在于S和T之间,同一个传送门的两端可能在同一个位置，但是一个地点不可能有多个传送门的一端）
Output
输出仅一行，表示巫妖王到达暴风城的最短时间，如果无法到达，则输出-1−1
Sample Input 1
4 8 S***###T *####*** *##****# **#*##** 1 1 4 4 8
Sample Output 1
8
Sample Input 2
4 8 S#***#*T *#*#*#*# *#*#*#*# ***#***# 0
Sample Output 2
21
也是比较裸的bfs，就是有些地方比较坑，也属于较简单的题目，本来传送门是一对多的，只不过后来为了照顾各位萌新改成一对一了。
我们可以先忽略休息时间，最后做个除法加上就好了。 这里需要注意的是传送门只能一对一，所以我们可以比较方便地使用结构体套map作为地图，用map记录传送门的对应关系，注意是双向的。
然后跑一遍bfs，在bfs中判断一下合法的队首是否存在传送门，然后在判断入队就好了。最后注意特判传送门直接从起点到达终点的情况。
这里给出原来传送门的一对多的情况的AC代码：
#include <bits/stdc++.h> using namespace std; #define ok(x,y,n,m) (x>=1 && x<=n && y>=1 && y<=m) const int mac=1e3+10; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; char s[mac][mac]; struct node { int x,y,t; }; struct Map { vector<int>x,y; int t; }; Map mp[mac][mac]; bool vis[mac][mac]; int bfs(int sx,int sy,int fx,int fy,int n,int m) { queue<node>q; q.push(node{sx,sy,0}); while (!q.empty()){ node now=q.front(); int x=now.x,y=now.y,t=now.t; q.pop(); if (vis[x][y]) continue; vis[x][y]=1; if (mp[x][y].t==1){//代表坐标x,y有传送门 for (int i=0; i<mp[x][y].x.size(); i++){//遍历该位置传送门所能到达的地方 int xx=mp[x][y].x[i],yy=mp[x][y].y[i]; if (s[xx][yy]!='#') { if (xx==fx && yy==fy) return t; if (!vis[xx][yy]) q.push(node{xx,yy,t}); } } } for (int i=0; i<4; i++){ int xx=x+dx[i],yy=y+dy[i]; if (!ok(xx,yy,n,m)) continue; if (vis[xx][yy]) continue; if (s[xx][yy]=='#') continue; if (xx==fx && yy==fy) return t; q.push(node{xx,yy,t+1}); } } return -1; } int main() { int n,m; scanf ("%d%d",&n,&m); int sx,sy,fx,fy; for (int i=1; i<=n; i++){ scanf ("%s",s[i]+1); for (int j=1; j<=m; j++){ if (s[i][j]=='S') sx=i,sy=j; else if (s[i][j]=='T') fx=i,fy=j; } } int x; scanf ("%d",&x); for (int i=1; i<=x; i++){ int x1,y1,x2,y2; scanf ("%d%d%d%d",&x1,&y1,&x2,&y2); mp[x1][y1].t=1; mp[x2][y2].t=1; mp[x1][y1].x.push_back(x2); mp[x1][y1].y.push_back(y2); mp[x2][y2].x.push_back(x1); mp[x2][y2].y.push_back(y1); } for (int i=0; i<mp[sx][sy].x.size(); i++){ int x=mp[sx][sy].x[i],y=mp[sx][sy].y[i]; if (x==fx && y==fy) { printf ("0 "); return 0; } } int ans=bfs(sx,sy,fx,fy,n,m);//注意返回的是到达T的前一刻时间 if (ans==-1) { printf ("-1 "); return 0; } ans+=ans/8; printf ("%d ",ans+1); return 0; }