分别以两个人的家作为起点,bfs求得到每个KFC最短距离。然后枚举每个KFC,求得时间之和的最小值即可。
此题不符合实际情况之处: 通过了一个KFC再去另一个KFC可以吗? 出题人都没好好想过吗?
AC代码
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn = 200 + 5; int d[2][maxn][maxn]; const int dx[] = {1,-1,0,0}; const int dy[] = {0,0,-1,1}; struct node{ int x, y; node(){ } node(int x, int y):x(x), y(y){ } }; int n, m; char G[maxn][maxn]; bool in(int x , int y){ if(x < 0 || y < 0 || x >= n || y >= m) return false; return true; } void bfs(int x, int y, int c){ queue<node>q; d[c][x][y] = 0; q.push(node(x, y)); while(!q.empty()){ node p = q.front(); q.pop(); x = p.x, y = p.y; for(int i = 0; i < 4; ++i){ int px = x + dx[i], py = y + dy[i]; if(!in(px, py) || G[px][py] == '#' || d[c][px][py] != -1) continue; d[c][px][py] = d[c][x][y] + 1; //if(G[px][py] != 'Y' && G[px][py] != 'M' && G[px][py] != '@') q.push(node(px, py)); } } } int main(){ while(scanf("%d%d", &n, &m) == 2){ memset(d, -1, sizeof(d)); for(int i = 0; i < n; ++i) scanf("%s", G[i]); for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j){ if(G[i][j] == 'Y') bfs(i, j, 0); else if(G[i][j] == 'M') bfs(i, j, 1); } int ans = 1 << 30; for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j){ if(G[i][j] == '@' && d[1][i][j] != -1 && d[0][i][j] != -1){ ans = min(ans, d[0][i][j] + d[1][i][j]); } } printf("%d\n", ans * 11); } return 0; }
如有不当之处欢迎指出!