穿过迷宫的最少移动次数

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：

输入：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
蛇保证从空单元格开始出发。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumMoves(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 20 ms, 内存消耗: 6.8 MB, 提交时间: 2023-02-05 10:22:24

func minimumMoves(grid [][]int) int {
    n := len(grid)
    dist := make([][][2]int, n)
    for i := range dist {
        dist[i] = make([][2]int, n)
        for j := range dist[i] {
            dist[i][j] = [2]int{-1, -1}
        }
    }
    dist[0][0][0] = 0
    queue := [][3]int{{0, 0, 0}}

    for len(queue) > 0 {
        arr := queue[0]
        queue = queue[1:]
        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 = append(queue, [3]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 = append(queue, [3]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 = append(queue, [3]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 = append(queue, [3]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 = append(queue, [3]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 = append(queue, [3]int{x, y, 0})
            }
        }
    }

    return dist[n-1][n-2][0]
}

python3 解法, 执行用时: 120 ms, 内存消耗: 16.9 MB, 提交时间: 2023-02-05 10:22:01

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dist = {(0, 0, 0): 0}
        q = deque([(0, 0, 0)])

        while q:
            x, y, status = q.popleft()
            if status == 0:
                # 向右移动一个单元格
                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:
                    dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1
                    q.append((x, y + 1, 0))
                
                # 向下移动一个单元格
                if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:
                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1
                    q.append((x + 1, y, 0))
                
                # 顺时针旋转 90 度
                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:
                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1
                    q.append((x, y, 1))
            else:
                # 向右移动一个单元格
                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:
                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1
                    q.append((x, y + 1, 1))
                
                # 向下移动一个单元格
                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:
                    dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1
                    q.append((x + 1, y, 1))
                
                # 逆时针旋转 90 度
                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:
                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1
                    q.append((x, y, 0))

        return dist.get((n - 1, n - 2, 0), -1)

golang 解法, 执行用时: 20 ms, 内存消耗: 6.7 MB, 提交时间: 2023-02-05 10:20:40

type tuple struct{ x, y, s int }
var dirs = []tuple{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

func minimumMoves(g [][]int) int {
    n := len(g)
    vis := make([][][2]bool, n)
    for i := range vis {
        vis[i] = make([][2]bool, n)
    }
    vis[0][0][0] = true // 初始位置
    q := []tuple{{}}
    for step := 1; len(q) > 0; step++ {
        tmp := q
        q = nil
        for _, t := range tmp {
            for _, d := range dirs {
                x, y, s := t.x+d.x, t.y+d.y, t.s^d.s
                x2, y2 := x+s, y+(s^1) // 蛇头
                if x2 < n && y2 < n && !vis[x][y][s] &&
                    g[x][y] == 0 && g[x2][y2] == 0 && (d.s == 0 || g[x+1][y+1] == 0) {
                    if x == n-1 && y == n-2 { // 此时蛇头一定在 (n-1,n-1)
                        return step
                    }
                    vis[x][y][s] = true
                    q = append(q, tuple{x, y, s})
                }
            }
        }
    }
    return -1
}

cpp 解法, 执行用时: 24 ms, 内存消耗: 15.7 MB, 提交时间: 2023-02-05 10:20:27

class Solution {
    static constexpr int DIRS[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
public:
    int minimumMoves(vector<vector<int>> &g) {
        int n = g.size();
        bool vis[n][n][2]; memset(vis, 0, sizeof(vis));
        vis[0][0][0] = true;
        vector<tuple<int, int, int>> q = {{0, 0, 0}}; // 初始位置
        for (int step = 1; !q.empty(); ++step) {
            vector<tuple<int, int, int>> nxt;
            for (const auto &[X, Y, S] : q) {
                for (const auto &d : DIRS) {
                    int x = X + d[0], y = Y + d[1], s = S ^ 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;
                        nxt.emplace_back(x, y, s);
                    }
                }
            }
            q = move(nxt);
        }
        return -1;
    }
};

java 解法, 执行用时: 13 ms, 内存消耗: 41.8 MB, 提交时间: 2023-02-05 10:20:13

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;
    }
}

python3 解法, 执行用时: 132 ms, 内存消耗: 16.7 MB, 提交时间: 2023-02-05 10:19:56

class Solution:
    def minimumMoves(self, g: List[List[int]]) -> int:
        step, n = 1, len(g)
        vis = {(0, 0, 0)}
        q = [(0, 0, 0)]  # 初始位置，最后一个0表示水平状态，1表示竖直状态
        while q:
            tmp = q
            q = []
            for X, Y, S in tmp:
                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):  # 直接把移动后的位置算出来
                    x, y, s = t
                    x2, y2 = x + s, y + (s ^ 1)  # 蛇头
                    if x2 < n and y2 < n and t not in vis and \
                       g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):
                        if x == n - 1 and y == n - 2:  # 此时蛇头一定在 (n-1,n-1)
                            return step
                        vis.add(t)
                        q.append(t)
            step += 1
        return -1

上一题

下一题

详情