算法题--带有障碍物的二维地图的唯一路径数

image.png

0. 链接

题目链接

1. 题目

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

示意图

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

2. 思路1：动态规划

image.png

对于(i, j)点, 由于robot只能向右或者向下, 所以它只可能由(i - 1, j)或(i, j - 1)格子通过向右或向下一次到达, 得到结论

若dp[i][j]表示到达(i,j)的唯一路径数, 则有

if obstacleGrid[i][j] == 1:
    # 表示(i, j)处有障碍物, 不可抵达
    dp[i][j] = 0
else:
    if i > 1:
        dp[i][j] += dp[i - 1][j]
    if j > 1:
        dp[i][j] += dp[i][j - 1]

初始条件为:

dp[0][0] = 1

原因是因为终点和起点在同一条直线上, 由于robot没法在向下后再向上到达终点, 所以它也只能通过走直线的方式抵达上述终点，即对于这些终点而言，只有1条路径。

3. 代码

# coding:utf8
from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    if i > 0:
                        dp[i][j] += dp[i - 1][j]
                    if j > 0:
                        dp[i][j] += dp[i][j - 1]

        return dp[m - 1][n - 1]


def find_and_print(solution, matrix):
    print('input={}, output={}'.format(matrix,
                                       solution.uniquePathsWithObstacles(matrix)))


solution = Solution()
find_and_print(solution, [[0, 0, 0], [0, 1, 0], [0, 0, 0]])

输出结果

input=[[0, 0, 0], [0, 1, 0], [0, 0, 0]], output=2

4. 结果

image.png