计蒜客 程序设计：迷宫（坑多）
有一个 n \times mn×m 的迷宫，其中 . 表示空地， *表示障碍物。除此之外，有 qq 个单向传送门：如果进入格子 (a_i,b_i)(ai,bi) ，那么会被立即传送到 (c_i,d_i)(ci,di) 。保证每个点至多是一个传送门的入口。
如果传送门最终传送到障碍物上，那么将会卡在障碍物上不能移动。
在传送门内部传送的花费是 00，在空地上每次可以往周围四个格子移动，花费是 11。
现在我们想知道从 (1,1)(1,1) 走到 (x,y)(x,y) 的最短距离。如果无法到达终点，输出 “No solution”（不含引号）。只要经过终点就算到达，即如果终点上有传送门也没有关系。
输入格式
第一行两个整数 n , mn,m ，表示地图大小。
接下来 nn 行，每行 mm 个字符，表示地图。
接下来一行一个整数 qq ，表示传送门个数。
接下来 qq 行，每行四个整数 a_i,b_i,c_i,d_iai,bi,ci,di 。
最后一行两个整数 x,yx,y 表示目的地。
输出格式
一个整数表示最短距离。
数据范围
对于 20\%20% 的数据： 0 < n, m \leq 50, 0 \leq q \leq 100<n,m≤50,0≤q≤10
对于 50\%50% 的数据： 0 < n, m \leq 200, 0 \leq q \leq 300<n,m≤200,0≤q≤30
对于 80\%80% 的数据： 0 < n, m \leq 500, 0 \leq q \leq 700<n,m≤500,0≤q≤70
对于 100\%100% 的数据： 0 < n, m \leq 1000, 0 \leq q \leq 1000<n,m≤1000,0≤q≤100
样例输入复制
3 4 ..*. ..*. ..*. 2 2 2 2 4 3 1 1 4 3 4
样例输出复制
3
普通bfs，坑：
（1）一个格子至多是一个传送门的入口，有可能连环传送
（2）当传送到一个已被访问的格子时break
（3）（1，1）也有可能有传送门，先传送再入队！
（4）传送到障碍物上时不入队
真就卡了我半天多
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
struct node
{
int x, y;
node() {};
node(int xx, int yy):x(xx), y(yy) {}
bool operator < (const node &a)const
{
if(x != a.x)
return x > a.x;
else
return y > a.y;
}
};
bool g[N][N], vis[N][N];
int n, m, q, step[N][N], tx, ty, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
map<node, node>mp;
bool bfs()
{
memset(step, 0, sizeof(step));
memset(vis, 0, sizeof(vis));
if(g[1][1] || tx > n || tx < 1 || ty > m || ty < 1)
return 0;
int fx = 1, fy = 1;
while(mp.count(node(fx, fy)))
{
node tmp = mp[node(fx, fy)];
fx = tmp.x;
fy = tmp.y;
if(vis[fx][fy])
return 0;
vis[fx][fy] = 1;
if(fx == tx && fy == ty)
return 1;
if(g[fx][fy])
return 0;
}
queue<node>q;
q.push(node(fx, fy));
while(q.size())
{
node tmp = q.front();
q.pop();
if(tmp.x == tx && tmp.y == ty)
return 1;
for(int i = 0; i < 4; ++i)
{
int fx = tmp.x + dir[i][0];
int fy = tmp.y + dir[i][1];
if(fx >= 1 && fx <= n && fy >= 1 && fy <= m && !vis[fx][fy] && !g[fx][fy]) ///移动到一点 未访问过且能走
{
step[fx][fy] = step[tmp.x][tmp.y] + 1; ///更新步数
vis[fx][fy] = 1; ///该点访问了
if(fx == tx && fy == ty) ///如果是终点 返回
return 1;
bool flag = 0;
while(mp.count(node(fx, fy))) ///传送门
{
node cur = node(fx, fy);
fx = mp[cur].x;
fy = mp[cur].y;
if(vis[fx][fy]) ///当前位置被访问过了，不需要入队，不需要更新步数
{
flag = 1;
break;
}
step[fx][fy] = step[tmp.x][tmp.y] + 1; ///当前位置未被访问，更新步数，有可能是.也可能是*
vis[fx][fy] = 1;
if(fx == tx && fy == ty) ///
return 1;
if(g[fx][fy]) ///是个障碍物 不能动了
break;
}
if(!flag && !g[fx][fy])
q.push(node(fx, fy));
}
}
}
return 0;
}
int main()
{
char ch;
while(~scanf("%d%d", &n, &m))
{
mp.clear();
memset(g, 0, sizeof(g));
for(int i = 1; i <= n; ++i)
{
getchar();
for(int j = 1; j <= m; ++j)
{
scanf("%c", &ch);
if(ch == '*')
g[i][j] = 1;
}
}
scanf("%d", &q);
int a, b, c, d;
for(int i = 1; i <= q; ++i)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
mp[node(a, b)] = node(c, d);
}
scanf("%d%d", &tx, &ty);
if(bfs())
cout<<step[tx][ty]<<'\n';
else
cout<<"No solution"<<'\n';
}
return 0;
}
