穿过迷宫的最少移动次数【LC1210】
你还记得那条风靡全球的贪吃蛇吗?
我们在一个 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。
- 思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1
。当status=0 时,需要考虑「向右移动」「向下移动」「顺时针旋转」三种情况
- 「向右移动」:需要保证 (x,y+2) 是空的单元格;
- 「向下移动」:需要保证(x+1,y) 和(x+1,y+1) 均是空的单元格;
- 「顺时针旋转」:需要保证(x+1,y)和(x+1,y+1) 均是空的单元格。
。当 status=1 时,需要考虑「向右移动」「向下移动」「逆时针旋转」三种情况。
- 「向右移动」:需要保证(x,y+1) 和(x+1,y+1) 均是空的单元格;
- 「向下移动」:需要保证(x+2,y) 是空的单元格;
- 「逆时针旋转」:需要保证(x,y+1) 和(x+1,y+1)均是空的单元格。
广度优先搜索方法的正确性在于:我们一定不会到达同一个位置两次及以上,因为这样必定不是最少的移动次数。
学习
- 实现
。dist数组的含义
- dist[x][y][0]表示当蛇尾坐标为(x,y),当蛇为水平时,达到这个位置的最短距离
- dist[x][y][0]表示当蛇尾坐标为(x,y),当蛇为垂直时,达到这个位置的最短距离
class Solution { public int minimumMoves(int[][] grid) { int n = grid.length; int[][][] dist = new int[n][n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Arrays.fill(dist[i][j], -1); } } dist[0][0][0] = 0; Queue<int[]> queue = new ArrayDeque<int[]>(); queue.offer(new int[]{0, 0, 0}); while (!queue.isEmpty()) { int[] arr = queue.poll(); int x = arr[0], y = arr[1], status = arr[2]; if (status == 0) { // 向右移动一个单元格 if (y + 2 < n && dist[x][y + 1][0] == -1 && grid[x][y + 2] == 0) { dist[x][y + 1][0] = dist[x][y][0] + 1; queue.offer(new int[]{x, y + 1, 0}); } // 向下移动一个单元格 if (x + 1 < n && dist[x + 1][y][0] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) { dist[x + 1][y][0] = dist[x][y][0] + 1; queue.offer(new int[]{x + 1, y, 0}); } // 顺时针旋转 90 度 if (x + 1 < n && y + 1 < n && dist[x][y][1] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) { dist[x][y][1] = dist[x][y][0] + 1; queue.offer(new int[]{x, y, 1}); } } else { // 向右移动一个单元格 if (y + 1 < n && dist[x][y + 1][1] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) { dist[x][y + 1][1] = dist[x][y][1] + 1; queue.offer(new int[]{x, y + 1, 1}); } // 向下移动一个单元格 if (x + 2 < n && dist[x + 1][y][1] == -1 && grid[x + 2][y] == 0) { dist[x + 1][y][1] = dist[x][y][1] + 1; queue.offer(new int[]{x + 1, y, 1}); } // 逆时针旋转 90 度 if (x + 1 < n && y + 1 < n && dist[x][y][0] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) { dist[x][y][0] = dist[x][y][1] + 1; queue.offer(new int[]{x, y, 0}); } } } return dist[n - 1][n - 2][0]; } } 作者:力扣官方题解 链接:https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/solutions/2091767/chuan-guo-mi-gong-de-zui-shao-yi-dong-ci-pmnh/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
。复杂度
- 时间复杂度:O ( n 2 )
- 空间复杂度:O ( n 2 )
- 优化:使用一份代码表示6种移动方式
。无论是水平状态还是竖直状态,蛇尾的状态变化为:
- 向下移动:x 增加 1,y和 s 不变。用三元组 (1,0,0) 表示
- 向右移动:y增加 1,x 和 s 不变。用三元组 (0,1,0) 表示
- 旋转:s切换,即 0变为 1,1 变为 0;x 和 y不变。用三元组 (0,0,1) 表示
。蛇头的状态变化为
- 如果s=0,蛇头在(x,y+1);如果 s=1,蛇头在(x+1,y)。也可以合并为一个公式表示蛇头:
(x+s,y+(s⊕1))
。实现时把这 3个三元组存到数组dirs中,遍历dirs,用同一份代码处理不同的移动,移动时需要判断:
- 移动后蛇身不能出界
- 移动后蛇身不能在障碍物上
- 对于旋转,还需要保证 (x+1,y+1)没有障碍物
class Solution { private static int[][] DIRS = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; public int minimumMoves(int[][] g) { int n = g.length; var vis = new boolean[n][n][2]; var q = new ArrayList<int[]>(); vis[0][0][0] = true; q.add(new int[]{0, 0, 0}); // 初始位置 for (int step = 1; !q.isEmpty(); ++step) { var tmp = q; q = new ArrayList<>(); for (var t : tmp) { for (var d : DIRS) { int x = t[0] + d[0], y = t[1] + d[1], s = t[2] ^ d[2]; int x2 = x + s, y2 = y + (s ^ 1); // 蛇头 if (x2 < n && y2 < n && !vis[x][y][s] && g[x][y] == 0 && g[x2][y2] == 0 && (d[2] == 0 || g[x + 1][y + 1] == 0)) { if (x == n - 1 && y == n - 2) return step; // 此时蛇头一定在 (n-1,n-1) vis[x][y][s] = true; q.add(new int[]{x, y, s}); } } } } return -1; } } 作者:灵茶山艾府 链接:https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/solutions/2093126/huan-zai-if-elseyi-ge-xun-huan-chu-li-li-tw8b/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
。复杂度
- 时间复杂度:O ( n 2 )
- 空间复杂度:O ( n 2 )