获取食物的最短路径 图解题解

这道题到底在问什么

输入

[[X,X,X],[X,*,#],[X,X,X]]

输出

1（右边就是食物）

最优解：一步一步想明白

1. 3记住「队头取格 → 扩四邻 → 空地入队、食物即止」，第一次到食物就是最短。下面每帧扩一个格。
2. 4起点 *（紫，正在处理）入队即标记已访问，步数 0。食物 # 在右下角，开始一圈圈往外扩。
3. 5队头取出 (0,0)（紫，步数 0），看四邻：新空地邻居 (1,0)、(0,1) 入队即标蓝（已访问），步数记 1。
4. 6队头取出 (1,0)（紫，步数 1），看四邻：新空地邻居 (2,0) 入队即标蓝（已访问），步数记 2。
5. 7队头取出 (0,1)（紫，步数 1），看四邻：新空地邻居 (0,2) 入队即标蓝（已访问），步数记 2。
6. 8队头取出 (2,0)（紫，步数 2），看四邻：新空地邻居 (3,0) 入队即标蓝（已访问），步数记 3。
7. 9队头取出 (0,2)（紫，步数 2），看四邻：新空地邻居 (1,2)、(0,3) 入队即标蓝（已访问），步数记 3。
8. 10队头取出 (3,0)（紫，步数 3），看四邻：新空地邻居 (4,0) 入队即标蓝（已访问），步数记 4。
9. 11队头取出 (1,2)（紫，步数 3），看四邻：新空地邻居 (2,2) 入队即标蓝（已访问），步数记 4。
10. 12队头取出 (0,3)（紫，步数 3），看四邻：四邻无新格，跳过。
11. 13队头取出 (4,0)（紫，步数 4），看四邻：新空地邻居 (4,1) 入队即标蓝（已访问），步数记 5。
12. 14队头取出 (2,2)（紫，步数 4），看四邻：新空地邻居 (2,3) 入队即标蓝（已访问），步数记 5。
13. 15队头取出 (4,1)（紫，步数 5），看四邻：新空地邻居 (4,2) 入队即标蓝（已访问），步数记 6。
14. 16队头取出 (2,3)（紫，步数 5），看四邻：新空地邻居 (2,4) 入队即标蓝（已访问），步数记 6。
15. 17队头取出 (4,2)（紫，步数 6），看四邻：新空地邻居 (4,3) 入队即标蓝（已访问），步数记 7。
16. 18队头取出 (2,4)（紫，步数 6），看四邻：新空地邻居 (3,4)、(1,4) 入队即标蓝（已访问），步数记 7。
17. 19队头取出 (4,3)（紫，步数 7），看四邻：新空地邻居 (4,4) 入队即标蓝（已访问），步数记 8。
18. 20队头取出 (3,4)（紫，步数 7），看四邻：四邻无新格，跳过。
19. 21队头取出 (1,4)（紫，步数 7），看四邻：新空地邻居 (1,5) 入队即标蓝（已访问），步数记 8。
20. 22队头取出 (4,4)（紫，步数 8），看四邻：新空地邻居 (4,5) 入队即标蓝（已访问），步数记 9。
21. 23队头取出 (1,5)（紫，步数 8），看四邻：新空地邻居 (0,5)、(1,6) 入队即标蓝（已访问），步数记 9。
22. 24从 (4,5) 看四邻碰到食物 #，返回 9 + 1 = 10 步。逐层扩展，首次到达即最短。
23. 25顺着「从谁来的」回溯，绿色这条就是最短路，从起点到食物共 10 步。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return -1
        m, n = len(grid), len(grid[0])
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '*':
                    q.append((i, j, 0))
                    grid[i][j] = 'X'
        while q:
            i, j, d = q.popleft()
            for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != 'X':
                    if grid[ni][nj] == '#':
                        return d + 1
                    grid[ni][nj] = 'X'
                    q.append((ni, nj, d + 1))
        return -1

#include <vector>
#include <queue>
#include <tuple>
using namespace std;

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return -1;
        int m = grid.size(), n = grid[0].size();
        queue<tuple<int,int,int>> q;
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == '*') { q.push({i,j,0}); grid[i][j] = 'X'; }
        int dirs[5] = {1,0,-1,0,1};
        while (!q.empty()) {
            auto [i,j,d] = q.front(); q.pop();
            for (int k = 0; k < 4; ++k) {
                int ni = i + dirs[k], nj = j + dirs[k+1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] != 'X') {
                    if (grid[ni][nj] == '#') return d + 1;
                    grid[ni][nj] = 'X';
                    q.push({ni,nj,d+1});
                }
            }
        }
        return -1;
    }
};

import java.util.*;

class Solution {
    public int getFood(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == '*') { q.offer(new int[]{i,j,0}); grid[i][j] = 'X'; }
        int[] dirs = {1,0,-1,0,1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int ni = cur[0] + dirs[k], nj = cur[1] + dirs[k+1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] != 'X') {
                    if (grid[ni][nj] == '#') return cur[2] + 1;
                    grid[ni][nj] = 'X';
                    q.offer(new int[]{ni,nj,cur[2]+1});
                }
            }
        }
        return -1;
    }
}

复杂度

面试官可能追问