题解 | #逃离迷宫#

我们分成两条路，一条路没有钥匙，一条路有钥匙 来表示状态，让这两条路BFS 不需要考虑多把钥匙的情况，拿到任意一把钥匙就可以

#include <bits/stdc++.h>

using namespace std;

#define  int long long

char mp[501][501];
int dist[501][501][2];
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0};
int n,m;
int ex,ey;
int tx,ty;
bool vis[501][501][2];
struct node{
    int x;
    int y;
    int road;
};

bool inmp(int x,int y){
    return x>0&&x<=n&&y>0&&y<=m&& mp[x][y] != '#';
}

int bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof(dist));
    queue<node> q;
    q.push({sx, sy, 0});
    dist[sx][sy][0] = 0;

    while (!q.empty()) {
        node cur = q.front();
        q.pop();

        if (cur.x == ex && cur.y == ey && cur.road) {
            return dist[cur.x][cur.y][cur.road];
        }

        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + xx[i];
            int ny = cur.y + yy[i];
            int nroad = cur.road;

            if (!inmp(nx, ny)) continue;
            if (mp[nx][ny] == 'E' && !nroad) continue;  // 不能穿过终点

            if (mp[nx][ny] == 'K') {
                nroad = 1;
            }

            if (dist[nx][ny][nroad] == -1) {
                dist[nx][ny][nroad] = dist[cur.x][cur.y][cur.road] + 1;
                q.push({nx, ny, nroad});
            }
        }
    }

    return -1;
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        cin>>n>>m;
        for (int i = 1; i <=n ; ++i) {
            for (int j = 1; j <=m ; ++j) {
                cin>>mp[i][j];
                if(mp[i][j]=='E'){
                    ex=i,ey=j;
                }else if(mp[i][j]=='P'){
                    tx=i,ty=j;
                }
            }
        }
        int result = bfs(tx, ty, ex, ey);
        if (result == -1) {
            cout << "No solution\n";
        } else {
            cout << result << '\n';
        }

    }

    return 0;
}