难度: Medium
Submission
运行时间: 80 ms
内存: 22.4 MB
from collections import deque
from typing import List
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右、左、下、上
# 找到起始位置'*'
start_row, start_col = -1, -1
for i in range(m):
for j in range(n):
if grid[i][j] == '*':
start_row, start_col = i, j
break
if start_row != -1:
break
# 使用队列进行BFS
queue = deque([(start_row, start_col)])
visited = [[False] * n for _ in range(m)] # 记录节点是否已被访问过
visited[start_row][start_col] = True
steps = 0 # 记录步数
while queue:
size = len(queue) # 当前层节点数量
for _ in range(size):
row, col = queue.popleft() # 出队列
if grid[row][col] == '#': # 找到食物，返回步数
return steps
for dx, dy in directions: # 探索四个方向的邻近节点
new_row, new_col = row + dx, col + dy
if 0 <= new_row < m and 0 <= new_col < n and not visited[new_row][new_col] and grid[new_row][new_col] != 'X':
queue.append((new_row, new_col)) # 入队列
visited[new_row][new_col] = True # 标记为已访问过
steps += 1 # 完成一层搜索，步数+1
# 没有找到食物路径的情况
return -1
Explain
这个题解使用广度优先搜索（BFS）算法来解决问题。首先遍历网格，找到起始位置'*'的坐标。然后使用队列进行BFS，每次从队列中取出一个节点，探索其四个方向的相邻节点。如果找到食物'#'，则返回当前的步数；如果未找到食物，则将未访问过且不是障碍物'X'的相邻节点加入队列，并标记为已访问。当队列为空时，表示无法到达食物，返回-1。
时间复杂度: O(mn)
空间复杂度: O(mn)
from collections import deque
from typing import List
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右、左、下、上
# 找到起始位置'*'
start_row, start_col = -1, -1
for i in range(m):
for j in range(n):
if grid[i][j] == '*':
start_row, start_col = i, j
break
if start_row != -1:
break
# 使用队列进行BFS
queue = deque([(start_row, start_col)]) # 初始化队列，将起始位置加入队列
visited = [[False] * n for _ in range(m)] # 记录节点是否已被访问过
visited[start_row][start_col] = True # 标记起始位置为已访问
steps = 0 # 记录步数
while queue:
size = len(queue) # 当前层节点数量
for _ in range(size):
row, col = queue.popleft() # 出队列，获取当前节点坐标
if grid[row][col] == '#': # 找到食物，返回步数
return steps
for dx, dy in directions: # 探索四个方向的邻近节点
new_row, new_col = row + dx, col + dy
# 检查新节点是否在网格范围内、未被访问过且不是障碍物
if 0 <= new_row < m and 0 <= new_col < n and not visited[new_row][new_col] and grid[new_row][new_col] != 'X':
queue.append((new_row, new_col)) # 将新节点加入队列
visited[new_row][new_col] = True # 标记新节点为已访问
steps += 1 # 完成一层搜索，步数+1
# 没有找到食物路径的情况
return -1
Explore
在广度优先搜索（BFS）中，队列用来确保首先探索所有距离起始点等距离的节点，然后再移向更远的节点。这保证了搜索的层级结构，即逐层向外扩展，这对于寻找最短路径是非常重要的。如果使用栈，则会变成深度优先搜索（DFS），这可能会导致首先探索远离起始点的路径，不适于最短路径的发现。而优先队列（用于实现最小优先队列的结构）通常用于最佳优先搜索（如A*搜索），这需要额外的逻辑来处理优先级（如距离评估），对于简单的最短路径问题，使用优先队列会增加不必要的复杂性和计算开销。
如果起始位置 '*' 不存在于网格中，代码在初始化队列时因找不到起始位置将导致 start_row 和 start_col 保持为 -1，这将在后续的队列操作中产生错误。为了处理这种情况，可以在完成起始位置的搜索后检查 start_row 和 start_col 是否被正确设置。如果它们仍为初始值 -1，函数应该返回 -1 或抛出一个异常，表明没有有效的起始点。
在BFS实现中，为了防止重复访问节点，使用了一个二维数组 `visited` 来跟踪每个节点的访问状态。每当一个节点被取出队列进行处理时，都会检查 `visited` 数组；如果该节点已被标记为访问过，就不会再次将其加入队列。当节点首次被发现时，会立即在 `visited` 数组中将其标记为已访问，这确保了每个节点只被处理一次。
虽然可以通过优先探索估计更接近目标的方向来优化搜索路径，但这样做实质上是在使用一种启发式搜索（如A*算法），而不是纯粹的BFS。这种优化通常涉及到计算启发式函数（如欧几里得距离或曼哈顿距离），以决定探索的优先级。这样做可以减少探索的节点总数，从而提高效率，但同时也增加了每次节点扩展的计算复杂性。对于特定类型的问题，这种方法可能更有效，但对于简单的最短路径搜索，纯粹的BFS由于其实现的简单性和可预测的性能通常更受欢迎。