有一个 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;
}