LeetCode 题解工作台
将石头分散到网格图的最少移动次数
给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。 每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。 请你返回每个格子恰好有一个石头的 最少移动…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
题目实际上是求一个状态图中从初始状态到目标状态的最短路径，因此可以使用 BFS 求解。初始状态为 `grid`，目标状态为 `[[1, 1, 1], [1, 1, 1], [1, 1, 1]]`，在每次操作中，我们可以将一个单元格大于 的石头移动到相邻的一个不超过 的单元格。如果找到了目标状态，那么就可以返回当前的层数，即为最少移动次数。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。
每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。
请你返回每个格子恰好有一个石头的 最少移动次数 。
示例 1：
输入：grid = [[1,1,0],[1,1,1],[1,2,1]] 输出：3 解释：让每个格子都有一个石头的一个操作序列为： 1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。 2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。 3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。 总共需要 3 次操作让每个格子都有一个石头。 让每个格子都有一个石头的最少操作次数为 3 。
示例 2：
输入：grid = [[1,3,0],[1,0,0],[1,0,3]] 输出：4 解释：让每个格子都有一个石头的一个操作序列为： 1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。 2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。 3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。 4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。 总共需要 4 次操作让每个格子都有一个石头。 让每个格子都有一个石头的最少操作次数为 4 。
提示：
grid.length == grid[i].length == 30 <= grid[i][j] <= 9grid中元素之和为9。
解题思路
方法一：朴素 BFS
题目实际上是求一个状态图中从初始状态到目标状态的最短路径，因此可以使用 BFS 求解。初始状态为 grid，目标状态为 [[1, 1, 1], [1, 1, 1], [1, 1, 1]]，在每次操作中，我们可以将一个单元格大于 的石头移动到相邻的一个不超过 的单元格。如果找到了目标状态，那么就可以返回当前的层数，即为最少移动次数。
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
q = deque([tuple(tuple(row) for row in grid)])
vis = set(q)
ans = 0
dirs = (-1, 0, 1, 0, -1)
while 1:
for _ in range(len(q)):
cur = q.popleft()
if all(x for row in cur for x in row):
return ans
for i in range(3):
for j in range(3):
if cur[i][j] > 1:
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < 3 and 0 <= y < 3 and cur[x][y] < 2:
nxt = [list(row) for row in cur]
nxt[i][j] -= 1
nxt[x][y] += 1
nxt = tuple(tuple(row) for row in nxt)
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
ans += 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluate the candidate's understanding of state transition dynamic programming.
- question_mark
Assess the candidate's ability to efficiently perform grid transformations.
- question_mark
Look for a clear explanation of BFS and how it ensures minimal move calculations.
常见陷阱
外企场景- error
Forgetting to track the optimal state transitions, leading to unnecessary moves.
- error
Overlooking edge cases where certain cells may need more or fewer stones than others.
- error
Misunderstanding the grid's adjacency rules, leading to incorrect stone placement.
进阶变体
外企场景- arrow_right_alt
What if the grid size increases to 4x4? The problem's state transitions will expand, requiring more complex dynamic programming.
- arrow_right_alt
What if there are more than 9 stones? The challenge will include distributing the stones more efficiently across larger grids.
- arrow_right_alt
What if stones are placed randomly in the grid? A solution must account for irregular stone distributions and still aim for the minimum move count.