Leetcode weekly contest 156 穿过迷宫的最少移动次数 Minimum Moves to Reach Target with Rotations

目录

1. 解答

你还记得那条风靡全球的贪吃蛇吗？

我们在一个 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：

输入：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 <= 100
• 0 <= grid[i][j] <= 1
• 蛇保证从空单元格开始出发。

解答

广度优先搜索。需要导入 queue 模块。
定义三维数组，mp 记录蛇走过的所有位置，任意位置，只搜索一次。
先取 grid 的行数 xl，列数 yl。
mp 定义为 xl 行，yl 列，每个元素是二元组。初始全为 0。

定义蛇的位置用（x, y, z)三元组表示，是蛇最右、最上的格子的坐标为 x，y，蛇水平时，z 为 0，蛇竖直时，z 为 1。那么蛇最初位置就表示为 (0, 0, 0)，重点位置表示为(xl-1, yl-2, 0)。

再看蛇的位置转换：

1. 当蛇水平时
   1. 向右移动：条件是（x,y+2）没有障碍
   2. 向下移动：条件是（x+1,y）、（x+1,y+1）都没有障碍
   3. 顺时针旋转 90°：条件与 2. 相同
2. 当蛇竖直时
   1. 向右移动：条件是（x,y+1）、（x+1,y+1）都没有障碍
   2. 向下移动：条件是（x+2,y）没有障碍
   3. 逆时针旋转 90°：条件与 1. 相同

AC 代码

import queue
class Solution:

    def minimumMoves(self, grid: List[List[int]]) -> int:
        x = 0
        y = 0
        xl = len(grid)
        yl = len(grid[0])
        mp = [[[0,0] for j in range(yl)] for i in range(xl)]
        q = queue.Queue()
        q.put((0, 0, 0, 0))
        mp[0][0][0] = 1
        while not q.empty():
            x, y, z, s = q.get()
            if z == 0:
                if y + 2 < yl and grid[x][y+2] == 0 and mp[x][y+1][0] == 0:
                    if x == xl - 1 and y + 1 == yl - 2:
                        return s + 1
                    q.put((x, y+1, 0, s+1))
                    mp[x][y+1][0] = 1
                if x + 1 < xl and y + 1 < yl and grid[x+1][y] == 0 and grid[x+1][y+1] == 0:
                    if x+1 == xl - 1 and y == yl - 2:
                        return s + 1
                    if mp[x+1][y][0] == 0:
                        q.put((x+1, y, 0, s+1))
                        mp[x+1][y][0] = 1
                    if mp[x][y][1] == 0:
                        q.put((x, y, 1, s+1))
                        mp[x][y][1] = 1
            if z == 1:
                if x + 2 < xl and grid[x+2][y] == 0 and mp[x+1][y][1] == 0:
                    q.put((x+1, y, 1, s+1))
                    mp[x+1][y][1] = 1
                if x + 1 < xl and y + 1 < yl and grid[x+1][y+1] == 0 and grid[x][y+1] == 0:
                    if mp[x][y+1][1] == 0:
                        q.put((x, y+1, 1, s+1))
                        mp[x][y+1][1] = 1
                    if mp[x][y][0] == 0:
                        q.put((x, y, 0, s+1))
                        mp[x][y][0] = 1
        return -1