63.UniquePathsII

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

题目： 63. Unique Paths II

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

解题思路

这道题是62. Unique Path的升级版，相对于62. Unique Path来说，只是多了障碍的情况。所以其实解法和62. Unique Path类似（参考 https://my.oschina.net/JiamingMai/blog/4348177 ），只是唯一不同的是，将有障碍的地方的h()都设为0，例如假设(i, j)这个位置有障碍物，那么h(i, j)=0，表示(i, j)这个位置到达右下角的可行路径数为0，即到达不了右下角。

值得注意的是，有一种特殊情况：右下角有障碍物。例如输入的数组为[[1]]，这个时候应该返回0，所以要排除这种右下角有障碍物的情况，当右下角有障碍物时，应该直接返回0，因为无论如何永远无法到达右下角。

时间复杂度

与62. Unique Path一样，都为O(mn)，具体分析过程参考 https://my.oschina.net/JiamingMai/blog/4348177

最终实现

Java 实现

// Input: [[1]]
// Expected: 0
public class Solution {
    private int h[][];
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (null == obstacleGrid || obstacleGrid.length <= 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // initialize the two-dimension array h
        h = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                h[i][j] = obstacleGrid[i][j] != 1 ? -1 : 0;
            }
        }
        // return 0 because the right-bottom position is blocked
        if (h[m-1][n-1] == 0) {
            return 0;
        }
        // set the right-bottom position to 1
        h[m-1][n-1] = 1;
        return calcH(0, 0);
    }
    private int calcH(int i, int j) {
        int m = h.length;
        int n = h[0].length;
        if (i >= m || j >= n) {
            return 0;
        }
        if (h[i][j] != -1) {
            return h[i][j];
        }
        h[i][j] = calcH(i + 1, j) + calcH(i, j + 1);
        return h[i][j];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int m = 1;
        int n = 1;
        int[][] obstacleGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                obstacleGrid[i][j] = 0;
            }
        }
        obstacleGrid[0][0] = 1;
        int res = solution.uniquePathsWithObstacles(obstacleGrid);
        System.out.println(res);
    }
}

 

以上是 63.UniquePathsII 的全部内容， 来源链接： utcz.com/z/518185.html

回到顶部