README.md

1730. 获取食物的最短路径

English Version

题目描述

你现在很饿，想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。

给定一个 m x n 的字符矩阵 grid ，包含下列不同类型的格子：

• '*' 是你的位置。矩阵中有且只有一个 '*' 格子。
• '#' 是食物。矩阵中可能存在多个食物。
• 'O' 是空地，你可以穿过这些格子。
• 'X' 是障碍，你不可以穿过这些格子。

返回你到任意食物的最短路径的长度。如果不存在你到任意食物的路径，返回 -1。

 

示例 1:

输入： grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
输出： 3
解释： 要拿到食物，你需要走 3 步。

Example 2:

输入： grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
输出： -1
解释： 你不可能拿到食物。

示例 3:

输入: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
输出: 6
解释: 这里有多个食物。拿到下边的食物仅需走 6 步。

示例 4:

输入: grid = [["O","*"],["#","O"]]
输出: 2

示例 5:

输入: grid = [["X","*"],["#","X"]]
输出: -1

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[row][col] 是 '*'、 'X'、 'O' 或 '#' 。
• grid 中有且只有一个 '*' 。

解法

BFS。

Python3

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        def pos():
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == '*':
                        return i, j

        m, n = len(grid), len(grid[0])
        q = deque([pos()])
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q), 0, -1):
                i, j = q.popleft()
                for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n:
                        if grid[x][y] == '#':
                            return ans
                        if grid[x][y] == 'O':
                            grid[x][y] = 'X'
                            q.append((x, y))
        return -1

Java

class Solution {
    public int getFood(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<int[]> q = new LinkedList<>();
        q.offer(pos(grid));
        int ans = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!q.isEmpty()) {
            ++ans;
            for (int i = q.size(); i > 0; --i) {
                int[] p = q.poll();
                for (int j = 0; j < 4; ++j) {
                    int x = p[0] + dirs[j];
                    int y = p[1] + dirs[j + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (grid[x][y] == '#') {
                            return ans;
                        }
                        if (grid[x][y] == 'O') {
                            grid[x][y] = 'X';
                            q.offer(new int[]{x, y});
                        }
                    }
                }
            }
        }
        return -1;
    }

    private int[] pos(char[][] grid) {
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == '*') {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

C++

typedef pair<int, int> pii;

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pii> q{{pos(grid)}};
        int ans = 0;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        while (!q.empty())
        {
            ++ans;
            for (int i = q.size(); i > 0; --i)
            {
                pii p = q.front();
                q.pop();
                for (int j = 0; j < 4; ++j)
                {
                    int x = p.first + dirs[j];
                    int y = p.second + dirs[j + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n)
                    {
                        if (grid[x][y] == '#') return ans;
                        if (grid[x][y] == 'O')
                        {
                            grid[x][y] = 'X';
                            q.push({x, y});
                        }
                    }
                }
            }
        }
        return -1;
    }

    pii pos(vector<vector<char>>& grid) {
        for (int i = 0; i < grid.size(); ++i)
            for (int j = 0; j < grid[0].size(); ++j)
                if (grid[i][j] == '*')
                    return {i, j};
        return {};
    }
};

Go

func getFood(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	pos := func() []int {
		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				if grid[i][j] == '*' {
					return []int{i, j}
				}
			}
		}
		return []int{}
	}
	q := [][]int{pos()}
	dirs := []int{-1, 0, 1, 0, -1}
	ans := 0
	for len(q) > 0 {
		ans++
		for i := len(q); i > 0; i-- {
			p := q[0]
			q = q[1:]
			for j := 0; j < 4; j++ {
				x, y := p[0]+dirs[j], p[1]+dirs[j+1]
				if x >= 0 && x < m && y >= 0 && y < n {
					if grid[x][y] == '#' {
						return ans
					}
					if grid[x][y] == 'O' {
						grid[x][y] = 'X'
						q = append(q, []int{x, y})
					}
				}
			}
		}
	}
	return -1
}

...