Hard
题目描述
在一个 n×n 的网格中，有一条蛇占据两个格子，从左上角的 (0, 0) 和 (0, 1) 开始移动。网格中用 0 表示空格子，用 1 表示被阻塞的格子。蛇想要到达右下角的 (n-1, n-2) 和 (n-1, n-1)。
在一次移动中，蛇可以：
- 向右移动一格：如果那里没有被阻塞的格子。这种移动保持蛇的水平/垂直位置不变。
- 向下移动一格：如果那里没有被阻塞的格子。这种移动保持蛇的水平/垂直位置不变。
- 顺时针旋转：如果蛇处于水平位置且其下方的两个格子都是空的。在这种情况下，蛇从
(r, c)和(r, c+1)移动到(r, c)和(r+1, c)。 - 逆时针旋转：如果蛇处于垂直位置且其右侧的两个格子都是空的。在这种情况下，蛇从
(r, c)和(r+1, c)移动到(r, c)和(r, c+1)。
返回到达目标位置的最少移动次数。如果无法到达目标，返回 -1。
示例 1：
输入：grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
输出：11
示例 2：
输入：grid = [[0,0,1,1,1,1],
[0,0,0,0,1,1],
[1,1,0,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,0]]
输出：9
提示：
2 <= n <= 1000 <= grid[i][j] <= 1- 保证蛇从空格子开始
解题思路
这是一个典型的最短路径问题，可以使用广度优先搜索（BFS）来解决。
思路分析
蛇的状态可以用三个参数描述：
- 蛇头位置
(row, col) - 蛇尾位置（通过方向确定）
- 蛇的方向（水平 or 垂直）
我们可以用一个三元组 (row, col, direction) 表示蛇的状态，其中 direction = 0 表示水平（蛇尾在右边），direction = 1 表示垂直（蛇尾在下方）。
BFS 搜索策略
从初始状态 (0, 0, 0) 开始，每次尝试四种操作：
- 向右移动：
(r, c)→(r, c+1) - 向下移动：
(r, c)→(r+1, c) - 顺时针旋转：水平 → 垂直
- 逆时针旋转：垂直 → 水平
对于每种操作，需要检查：
- 目标位置是否在网格范围内
- 蛇身占据的所有格子是否为空（值为0）
- 旋转时需要额外检查旋转所需的空间
状态验证
- 向右/向下移动：检查新的蛇头和蛇尾位置是否都为空
- 顺时针旋转（水平→垂直）：检查旋转后的蛇尾位置和旋转过程中的对角位置是否为空
- 逆时针旋转（垂直→水平）：检查旋转后的蛇尾位置和旋转过程中的对角位置是否为空
使用 visited 集合避免重复访问相同状态，当到达目标状态 (n-1, n-2, 0) 时返回步数。
代码实现
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
int n = grid.size();
queue<tuple<int, int, int, int>> q; // row, col, direction, steps
set<tuple<int, int, int>> visited;
q.push({0, 0, 0, 0}); // start at (0,0) horizontal, 0 steps
visited.insert({0, 0, 0});
while (!q.empty()) {
auto [r, c, dir, steps] = q.front();
q.pop();
// Check if reached target
if (r == n-1 && c == n-2 && dir == 0) {
return steps;
}
// Try all possible moves
vector<tuple<int, int, int>> nextStates;
if (dir == 0) { // horizontal
// Move right
if (c + 2 < n && grid[r][c+2] == 0) {
nextStates.push_back({r, c+1, 0});
}
// Move down
if (r + 1 < n && grid[r+1][c] == 0 && grid[r+1][c+1] == 0) {
nextStates.push_back({r+1, c, 0});
}
// Rotate clockwise (horizontal to vertical)
if (r + 1 < n && grid[r+1][c] == 0 && grid[r+1][c+1] == 0) {
nextStates.push_back({r, c, 1});
}
} else { // vertical
// Move right
if (c + 1 < n && grid[r][c+1] == 0 && grid[r+1][c+1] == 0) {
nextStates.push_back({r, c+1, 1});
}
// Move down
if (r + 2 < n && grid[r+2][c] == 0) {
nextStates.push_back({r+1, c, 1});
}
// Rotate counterclockwise (vertical to horizontal)
if (c + 1 < n && grid[r][c+1] == 0 && grid[r+1][c+1] == 0) {
nextStates.push_back({r, c, 0});
}
}
for (auto [nr, nc, ndir] : nextStates) {
if (visited.find({nr, nc, ndir}) == visited.end()) {
visited.insert({nr, nc, ndir});
q.push({nr, nc, ndir, steps + 1});
}
}
}
return -1;
}
};
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
n = len(grid)
queue = deque([(0, 0, 0, 0)]) # row, col, direction, steps
visited = set([(0, 0, 0)])
while queue:
r, c, direction, steps = queue.popleft()
# Check if reached target
if r == n-1 and c == n-2 and direction == 0:
return steps
next_states = []
if direction == 0: # horizontal
# Move right
if c + 2 < n and grid[r][c+2] == 0:
next_states.append((r, c+1, 0))
# Move down
if r + 1 < n and grid[r+1][c] == 0 and grid[r+1][c+1] == 0:
next_states.append((r+1, c, 0))
# Rotate clockwise (horizontal to vertical)
if r + 1 < n and grid[r+1][c] == 0 and grid[r+1][c+1] == 0:
next_states.append((r, c, 1))
else: # vertical
# Move right
if c + 1 < n and grid[r][c+1] == 0 and grid[r+1][c+1] == 0:
next_states.append((r, c+1, 1))
# Move down
if r + 2 < n and grid[r+2][c] == 0:
next_states.append((r+1, c, 1))
# Rotate counterclockwise (vertical to horizontal)
if c + 1 < n and grid[r][c+1] == 0 and grid[r+1][c+1] == 0:
next_states.append((r, c, 0))
for nr, nc, ndir in next_states:
if (nr, nc, ndir) not in visited:
visited.add((nr, nc, ndir))
queue.append((nr, nc, ndir, steps + 1))
return -1
public class Solution {
public int MinimumMoves(int[][] grid) {
int n = grid.Length;
var queue = new Queue<(int r, int c, int dir, int steps)>();
var visited = new HashSet<(int, int, int)>();
queue.Enqueue((0, 0, 0, 0)); // start at (0,0) horizontal, 0 steps
visited.Add((0, 0, 0));
while (queue.Count > 0) {
var (r, c, dir, steps) = queue.Dequeue();
// Check if reached target
if (r == n-1 && c == n-2 && dir == 0) {
return steps;
}
var nextStates = new List<(int, int, int)>();
if (dir == 0) { // horizontal
// Move right
if (c + 2 < n && grid[r][c+2] == 0) {
nextStates.Add((r, c+1, 0));
}
// Move down
if (r + 1 < n && grid[r+1][c] == 0 && grid[r+1][c+1] == 0) {
nextStates.Add((r+1, c, 0));
}
// Rotate clockwise (horizontal to vertical)
if (r + 1 < n && grid[r+1][c] == 0 && grid[r+1][c+1] == 0) {
nextStates.Add((r, c, 1));
}
} else { // vertical
// Move right
if (c + 1 < n && grid[r][c+1] == 0 && grid[r+1][c+1] == 0) {
nextStates.Add((r, c+1, 1));
}
// Move down
if (r + 2 < n && grid[r+2][c] == 0) {
nextStates.Add((r+1, c, 1));
}
// Rotate counterclockwise (vertical to horizontal)
if (c + 1 < n && grid[r][c+1] == 0 && grid[r+1][c+1] == 0) {
nextStates.Add((r, c, 0));
}
}
foreach (var (nr, nc, ndir) in nextStates) {
if (!visited.Contains((nr, nc, ndir))) {
visited.Add((nr, nc, ndir));
queue.Enqueue((nr, nc, ndir, steps + 1));
}
}
}
return -1;
}
}
var minimumMoves = function(grid) {
const n = grid.length;
const target = `${n-1},${n-2},${n-1},${n-1}`;
const queue = [[0, 0, 0, 1, 0]]; // [r1, c1, r2, c2, moves]
const visited = new Set();
visited.add("0,0,0,1");
while (queue.length > 0) {
const [r1, c1, r2, c2, moves] = queue.shift();
const state = `${r1},${c1},${r2},${c2}`;
if (state === target) {
return moves;
}
// Move right
if (c1 + 1 < n && c2 + 1 < n && grid[r1][c1 + 1] === 0 && grid[r2][c2 + 1] === 0) {
const newState = `${r1},${c1 + 1},${r2},${c2 + 1}`;
if (!visited.has(newState)) {
visited.add(newState);
queue.push([r1, c1 + 1, r2, c2 + 1, moves + 1]);
}
}
// Move down
if (r1 + 1 < n && r2 + 1 < n && grid[r1 + 1][c1] === 0 && grid[r2 + 1][c2] === 0) {
const newState = `${r1 + 1},${c1},${r2 + 1},${c2}`;
if (!visited.has(newState)) {
visited.add(newState);
queue.push([r1 + 1, c1, r2 + 1, c2, moves + 1]);
}
}
// Rotate clockwise (horizontal to vertical)
if (r1 === r2 && r1 + 1 < n && grid[r1 + 1][c1] === 0 && grid[r2 + 1][c2] === 0) {
const newState = `${r1},${c1},${r1 + 1},${c1}`;
if (!visited.has(newState)) {
visited.add(newState);
queue.push([r1, c1, r1 + 1, c1, moves + 1]);
}
}
// Rotate counterclockwise (vertical to horizontal)
if (c1 === c2 && c1 + 1 < n && grid[r1][c1 + 1] === 0 && grid[r2][c2 + 1] === 0) {
const newState = `${r1},${c1},${r1},${c1 + 1}`;
if (!visited.has(newState)) {
visited.add(newState);
queue.push([r1, c1, r1, c1 + 1, moves + 1]);
}
}
}
return -1;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²) - 每个状态最多被访问一次， |