LC 1210. 穿过迷宫的最少移动次数
题目描述
这是 LeetCode 上的 1210. 穿过迷宫的最少移动次数 ，难度为 困难。
你还记得那条风靡全球的贪吃蛇吗？
我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。
蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。
每次移动，蛇可以这样走：
- 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
- 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
- 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转
90度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
- 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转
90度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
返回蛇抵达目的地所需的最少移动次数。
如果无法到达目的地，请返回 -1。
示例 1：
1
2
3
4
5
6
7
8
9
10
11输入：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：1
2
3
4
5
6
7
8输入：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 <= 100$
- $0 <= grid[i][j] <= 1$
- 蛇保证从空单元格开始出发。
BFS
题目要我们求从特定起点到特定终点的最少步数，由于我们蛇的长度固定为 $2$，因此我们可用三元组 $(x, y, cd)$ 来代表蛇的实际位置。其中 $(x, y)$ 代表蛇尾位置，$cd$ 代表当前蛇的方向状态，$0$ 代表水平状态，$1$ 代表竖直状态。
蛇尾加上方向状态可确定其蛇头位置 ：tx = cd == 0 ? nx : nx + 1、ty = cd == 0 ? ny + 1 : ny。
对四种移动规则所导致三元组变化进行分情况讨论：
- 往右移动：对于蛇尾而言，只有维度 $y$ 进行加一，其余维度不变。三元组变化总结为 $(0, 1, 0)$
- 往下移动：对于蛇尾而言，只有维度 $x$ 进行加一，其余维度不变。三元组变化总结为 $(1, 0, 0)$
- 旋转：对于蛇尾，只有 $cd$ 维度对进行翻转，其余维度不变。三元组变化总结定为 $(0, 0, 1)$
综上，所有移动规则可总结为 int[][] dirs = new int[][]{{1,0,0},{0,1,0},{0,0,1}}。
在进行 BFS 时，通过遍历 dirs 来得到新的三元组：原位置 (x, y, cd) 转换到新位置 (x + dir[0], y + dir[1], cd ^ dir[2])。
在得到新蛇尾位置 $(nx, ny)$ 之后，计算新蛇头的位置 $(tx, ty)$。需要确保整条蛇没有越界，没有碰到障碍物，并且旋转转移时，额外检查 $(x + 1, y + 1)$ 位置是否合法。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
int[][] dirs = new int[][]{{1,0,0},{0,1,0},{0,0,1}};
public int minimumMoves(int[][] g) {
int n = g.length;
Deque<int[]> d = new ArrayDeque<>();
d.addLast(new int[]{0,0,0,0});
boolean[][][] vis = new boolean[n][n][2];
vis[0][0][0] = true;
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1], cd = info[2], step = info[3];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1], nd = cd ^ dir[2]; // 新蛇尾位置和方向
int tx = nd == 0 ? nx : nx + 1, ty = nd == 0 ? ny + 1 : ny; // 新蛇头
if (nx >= n || ny >= n || tx >= n || ty >= n) continue; // 整条蛇不越界
if (g[nx][ny] == 1 || g[tx][ty] == 1) continue; // 没有触及障碍物
if (vis[nx][ny][nd]) continue;
if (cd != nd && g[x + 1][y + 1] == 1) continue; // 旋转时，额外检查多一个位置
if (nx == n - 1 && ny == n - 2 && nd == 0) return step + 1;
d.addLast(new int[]{nx, ny, nd, step + 1});
vis[nx][ny][nd] = true;
}
}
return -1;
}
}
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
int minimumMoves(vector<vector<int>>& g) {
vector<vector<int>> dirs = {{1,0,0}, {0,1,0}, {0,0,1}};
int n = g.size();
queue<vector<int>> d;
d.push({0, 0, 0, 0});
vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(n, vector<bool>(2, false)));
vis[0][0][0] = true;
while (!d.empty()) {
vector<int> info = d.front();
d.pop();
int x = info[0], y = info[1], cd = info[2], step = info[3];
for (vector<int>& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1], nd = cd ^ dir[2];
int tx = nd == 0 ? nx : nx + 1, ty = nd == 0 ? ny + 1 : ny;
if (nx >= n || ny >= n || tx >= n || ty >= n) continue;
if (g[nx][ny] == 1 || g[tx][ty] == 1) continue;
if (vis[nx][ny][nd]) continue;
if (cd != nd && g[x + 1][y + 1] == 1) continue;
if (nx == n - 1 && ny == n - 2 && nd == 0) return step + 1;
d.push({nx, ny, nd, step + 1});
vis[nx][ny][nd] = true;
}
}
return -1;
}
};
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution:
def minimumMoves(self, g: List[List[int]]) -> int:
dirs = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
n = len(g)
d = deque([(0,0,0,0)])
vis = [[[0]*2 for _ in range(n)] for _ in range(n)]
vis[0][0][0] = 1
while d:
x, y, cd, step = d.popleft()
for dir in dirs:
nx, ny, nd = x + dir[0], y + dir[1], cd ^ dir[2]
tx, ty = nx + (nd == 1), ny + (nd == 0)
if nx >= n or ny >= n or tx >= n or ty >= n: continue
if g[nx][ny] == 1 or g[tx][ty] == 1: continue
if vis[nx][ny][nd]: continue
if cd != nd and g[x + 1][y + 1] == 1: continue
if nx == n - 1 and ny == n - 2 and nd == 0: return step + 1
d.append((nx, ny, nd, step + 1))
vis[nx][ny][nd] = 1
return -1
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function minimumMoves(g: number[][]): number {
const n = g.length;
const d: [number, number, number, number][] = [[0,0,0,0]];
const vis: boolean[][][] = Array.from({ length: n }, () => Array.from({ length: n }, () => [false, false]));
vis[0][0][0] = true;
const dirs: [number, number, number][] = [[1,0,0], [0,1,0], [0,0,1]];
while (d.length > 0) {
const [x, y, cd, step] = d.shift()!;
for (const dir of dirs) {
const nx = x + dir[0], ny = y + dir[1], nd = cd ^ dir[2];
const tx = nd === 0 ? nx : nx + 1, ty = nd === 0 ? ny + 1 : ny;
if (nx >= n || ny >= n || tx >= n || ty >= n) continue;
if (g[nx][ny] === 1 || g[tx][ty] === 1) continue
if (vis[nx][ny][nd]) continue;
if (cd !== nd && g[x + 1][y + 1] === 1) continue;
if (nx === n - 1 && ny === n - 2 && nd === 0) return step + 1;
d.push([nx, ny, nd, step + 1]);
vis[nx][ny][nd] = true;
}
}
return -1;
};
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2 \times C)$，其中 $C = 2$ 代表蛇可变状态方向
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1210 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
