2 条题解

从小明家和小明位置分别用bfs遍历到每个点的最短距离，然后再遍历所有的钥匙的点，最后我们从钥匙中找到到小明家和小明位置距离之和的最小值即可

#include

using namespace std;

const int N = 2010, INF = 0x3f3f3f3f;

int n, m;

int vis[N][N];

int ret[2][N][N];

char a[N][N];

int xx[4] = {1,-1,0,0};

int yy[4] = {0,0,1,-1};

void bfs(int xxx, int yyy, int d){

queue > q;

q.push(make_pair(xxx,yyy));

vis[xxx][yyy] = 1;

ret[d][xxx][yyy] = 0;

while(!q.empty()){

int tx = q.front().first;

int ty = q.front().second;

q.pop();

for (int i = 0; i < 4; i ++){

int x = tx + xx[i];

int y = ty + yy[i];

if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '#' && !vis[x][y]){

ret[d][x][y] = ret[d][tx][ty] + 1;

vis[x][y] = 1;

q.push(make_pair(x,y));

}

}

}

}

int main(){

queue > q;

cin >> n >> m;

memset(ret,INF, sizeof ret);

memset(vis,0, sizeof vis);

int sx, sy;

int tx, ty;

for (int i = 0; i < n; i ++){

cin >> a[i];

for (int j = 0; j < m; j ++){

if(a[i][j] == 'P'){

q.push(make_pair(i,j));

}else if(a[i][j] == 'S'){

sx = i;

sy = j;

}else if(a[i][j] == 'T'){

tx = i;

ty = j;

}

}

}

bfs(sx, sy, 0);

memset(vis, 0, sizeof vis);

bfs(tx,ty, 1);

int ans = INF;

while(!q.empty()){

int x = q.front().first;

int y = q.front().second;

q.pop();

ans = min(ans, ret[0][x][y]+ret[1][x][y]);

}

cout << ans;

return 0;

}