广搜之回家

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
/*先从起点出发搜钥匙，再从家出发搜钥匙。
代码不是我敲的。
*/
const int kMax = 2000 + 10;
const int kInf = 1e9;

struct node {
    int x, y, deep;
    node(int _x, int _y, int _deep) : x(_x), y(_y), deep(_deep) {}
};

int n, m;
char table[kMax][kMax];
bool vis[kMax][kMax];
int dist[kMax][kMax];
queue<node> q;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int solve() {
    while(!q.empty()) {
        node t = q.front(); q.pop();
        if(table[t.x][t.y] == 'P') {//如果取得钥匙
            dist[t.x][t.y] = t.deep;//起点到钥匙的距离
        }
        for(int i = 0;i < 4;++ i) {//尝试上下左右
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m &&
              !vis[x][y] && table[x][y] != '#') {
                q.push({x, y, t.deep + 1});
                vis[x][y] = true;
            }
        }
    }
    memset(vis, false, sizeof(vis));//重置标记
    for(int i = 0;i < n && q.empty();++ i) {//回到家就退出
        for(int j = 0;j < m;++ j) {
            if(table[i][j] == 'T') {
                q.push({i, j, 0});//压入家的坐标作为起点
                vis[i][j] = true;
                break;
            }
        }
    }
    int res = kInf;
    while(!q.empty()) {
        node t = q.front(); q.pop();
        if(table[t.x][t.y] == 'P') {//找到钥匙，如果从家出发能找到钥匙，那么从起点出发也必能找到钥匙。
            res = min(res, dist[t.x][t.y] + t.deep);
        }
        for(int i = 0;i < 4;++ i) {//尝试上下左右
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m &&
              !vis[x][y] && table[x][y] != '#') {
                q.push({x, y, t.deep + 1});
                vis[x][y] = true;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n;++ i) {
        scanf("%s", &table[i]);//按行输入
        if(q.empty()) {
            for(int j = 0;j < m;++ j) {
                if(table[i][j] == 'S') {//压入起点
                    q.push({i, j, 0});
                    vis[i][j] = true;
                    break;
                }
            }
        }
    }
    printf("%d\n", solve());
    return 0;
}