网格路径问题

发表于 | 分类于

本文旨在探讨LeetCode题目中的网格路径问题，这些问题通常涉及到动态规划或者是广度优先搜索。

网格中的最短路径LeetCode 1293

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        if m == 1 and n == 1:
            return 0
        if k >= m + n - 3:
            return m + n - 2
        visited = {(0, 0, k)}
        q = deque([(0, 0, k, 0)])
        while q:
            x, y, k, steps = q.popleft()
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    if grid[nx][ny] == 1 and k > 0 and (nx, ny, k-1) not in visited:
                        visited.add((nx, ny, k-1))
                        q.append((nx, ny, k-1, steps+1))
                    elif grid[nx][ny] == 0 and (nx, ny, k) not in visited:
                        if nx == m - 1 and ny == n - 1:
                            return steps + 1
                        visited.add((nx, ny, k))
                        q.append((nx, ny, k, steps+1))
        return -1

利用广度优先算法，分别利用visited记录走过的路径，利用q记录当前所在位置以及状态。另外，需要确定程序结束的边界条件。

不同路径Ileetcode 62

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

不同路径IIleetcode 63

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        if obstacleGrid[i][0] == 1:
            break
        dp[i][0] = 1
    for j in range(n):
        if obstacleGrid[0][j] == 1:
            break 
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            elif obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

主要思路是动态规划算法，假设$dp[i][j]$代表到达（i,j）位置路径数量，如果（i，j）位置有障碍，则到达不了$dp[i][j]=0$。如果（i，j）位置没有障碍，那么$dp[i][j]=dp[i-1][j]+dp[i][j-]$

不同路径IIIleetcode 980

在二维网格 grid 上，有 4 种类型的方格：
1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

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
28
29
30
31
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.res = 0
        self.empty = 1
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    x, y = (i, j)
                elif grid[i][j] == 2:
                    self.end = (i, j)
                elif grid[i][j] == 0:
                    self.empty += 1
        self.dfs(grid, x, y)
        return self.res

    def dfs(self, grid, x, y):
        if not (0 <= x < len(grid) and 0 <= y < len(grid[0])) or grid[x][y] == -1:
            return
        if (x, y) == self.end:
            if self.empty == 0:
                self.res += 1
            return
        grid[x][y] = -1
        self.empty -= 1
        self.dfs(grid, x + 1, y)
        self.dfs(grid, x - 1, y)
        self.dfs(grid, x, y + 1)
        self.dfs(grid, x, y - 1)
        grid[x][y] = 0
        self.empty += 1

网格路径最大和leetcode 47

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

使用动态规划方法，转移方程为$dp[i][j]=max(dp[i-1][j], dp[i][j-1])$

单词搜索leetcode 79

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            tmp, board[i][j] = board[i][j], '/'
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False
非常感谢各位老板投喂！