题解 | 量子网络穿梭

根本不会什么0-1bfs啊，不过还是用了单纯用了bfs通过的，对于传送门，当访问第一个传送门时，等价于访问配对的传送门，那么这个时候把当前访问的节点替换成配对的传送门节点就行了，也就是一个特判，其它就是普通bfs代码

#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> mp;
vector<pair<int, int>> qz;
vector<vector<bool>> vis;
int n, m;
bool check(int x, int y)
{
    return 0 <= x && x < n && 0 <= y && y < m && mp[x][y] != '1' && vis[x][y] == 0;
};
int bfs(int sx, int sy, int ex, int ey)
{
    queue<pair<int, int>> q;
    q.push({sx, sy});
    int ans = 0;
    while (q.size())
    {
        vector<pair<int, int>> v;
        while (q.size())
        {
            v.push_back(q.front());
            q.pop();
        };
        for (pair<int, int> t : v)
        {
            if (mp[t.first][t.second] == '2')
            {
                vis[t.first][t.second] = 1;
                t = t == qz[0] ? qz[1] : qz[0];//传送门替换
            }
            vis[t.first][t.second] = 1;
            if (t.first == ex && t.second == ey)
                return ans;
		  //遍历四个方向
            if (check(t.first + 1, t.second))
            {
                vis[t.first + 1][t.second] = 1;
                q.push({t.first + 1, t.second});
            }
            if (check(t.first - 1, t.second))
            {
                vis[t.first - 1][t.second] = 1;
                q.push({t.first - 1, t.second});
            }
            if (check(t.first, t.second + 1))
            {
                vis[t.first][t.second + 1] = 1;
                q.push({t.first, t.second + 1});
            }
            if (check(t.first, t.second - 1))
            {
                vis[t.first][t.second - 1] = 1;
                q.push({t.first, t.second - 1});
            }
        };
        ans++;
    };
    return -1;
};
int main()
{
    cin >> n >> m;
    mp.assign(n, vector<char>(m, 0));
    vis.assign(n, vector<bool>(m, false));
    int sx, sy;
    int ex, ey;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            char c = s[j];
            if (c == 'S')
                sx = i, sy = j;
            if (c == 'E')
                ex = i, ey = j;
            if (c == '2')
                qz.push_back({i, j});
            mp[i][j] = c;
        };
    }
    cout << bfs(sx, sy, ex, ey);
    return 0;
}
// 64 位输出请用 printf("%lld")

/*

7 1
1
E
0
2
1
2
S
*/