地圖 n×m (≤200)，Y、M 為兩人起點，@ 為 KFC，# 障礙，. 道路。雙方同速（每步 11 分鐘），找一個 KFC 使雙方步數之和最小，輸出總時間。
Y 為起點 BFS，記錄每個 @ 的距離 distYM 為起點 BFS，記錄每個 @ 的距離 distM@，取 min(distY + distM) × 11時間複雜度 O(n×m)，空間 O(n×m)。
#include#include #include #define MAXN 210 #define INF 0x3f3f3f3f char map[MAXN][MAXN]; int distY[MAXN][MAXN], distM[MAXN][MAXN]; int n, m; struct Node { int x, y, d; } q[MAXN*MAXN]; int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1}; void bfs(int sx, int sy, int dist[][MAXN]) { int head = 0, tail = 0; q[tail++] = (struct Node){sx, sy, 0}; dist[sx][sy] = 0; while (head < tail) { struct Node cur = q[head++]; for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i], ny = cur.y + dy[i]; if (nx<0 || nx>=n || ny<0 || ny>=m) continue; if (map[nx][ny] == '#') continue; if (dist[nx][ny] != INF) continue; dist[nx][ny] = cur.d + 1; q[tail++] = (struct Node){nx, ny, cur.d + 1}; } } } int main() { while (scanf("%d %d", &n, &m) == 2) { int yx=-1, yy=-1, mx=-1, my=-1; for (int i = 0; i < n; i++) { scanf("%s", map[i]); for (int j = 0; j < m; j++) { if (map[i][j] == 'Y') { yx=i; yy=j; } if (map[i][j] == 'M') { mx=i; my=j; } } } memset(distY, 0x3f, sizeof(distY)); memset(distM, 0x3f, sizeof(distM)); bfs(yx, yy, distY); bfs(mx, my, distM); int ans = INF; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '@' && distY[i][j]!=INF && distM[i][j]!=INF) ans = ans < distY[i][j]+distM[i][j] ? ans : distY[i][j]+distM[i][j]; printf("%d\n", ans * 11); } return 0; }
Input: 4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...# Output: 66 88 66
| 技術 | 說明 |
|---|---|
| 靜態隊列 | 避免 malloc 開銷，MAXN*MAXN 足夠 |
| 0x3f 初始化 | memset(dist, 0x3f, ...) 快速置 INF (≈1e9) |
| 雙 BFS 獨立 | 互不干擾，最後彙總 |
| 步數轉時間 | 題目每步 11 分鐘，最終乘 11 |
若只需「任意一人到最近 KFC」，可將 Y、M 同時入隊初始化 dist=0，一次 BFS 完成。
雙 BFS 解決雙源點會合最短路徑是圖論基礎模板。關鍵在於分別計算單源最短路、彙總取最小，代碼簡潔、複雜度最優，廣泛適用於網格地圖、迷宮、多人會合等場景。
