Unique Paths II

  • tags: [DP_Matrix]

Question

  1. Follow up for "Unique Paths":
  3. Now consider if some obstacles are added to the grids.
  4. How many unique paths would there be?
  6. An obstacle and empty space is marked as 1 and 0 respectively in the grid.
  7. Note
  8. m and n will be at most 100.
  10. Example
  11. For example,
  12. There is one obstacle in the middle of a 3x3 grid as illustrated below.
  14. [
  15.   [0,0,0],
  16.   [0,1,0],
  17.   [0,0,0]
  18. ]
  19. The total number of unique paths is 2.

题解

在上题的基础上加了obstacal这么一个限制条件，那么也就意味着凡是遇到障碍点，其路径数马上变为0，需要注意的是初始化环节和上题有较大不同。首先来看看错误的初始化实现。

C++ initialization error

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param obstacleGrid: A list of lists of integers
  5.      * @return: An integer
  6.      */
  7.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
  8.         if(obstacleGrid.empty() || obstacleGrid[0].empty()) {
  9.             return 0;
  10.         }
  12.         const int M = obstacleGrid.size();
  13.         const int N = obstacleGrid[0].size();
  15.         vector<vector<int> > ret(M, vector<int>(N, 0));
  17.         for (int i = 0; i != M; ++i) {
  18.             if (0 == obstacleGrid[i][0]) {
  19.                 ret[i][0] = 1;
  20.             }
  21.         }
  22.         for (int i = 0; i != N; ++i) {
  23.             if (0 == obstacleGrid[0][i]) {
  24.                 ret[0][i] = 1;
  25.             }
  26.         }
  28.         for (int i = 1; i != M; ++i) {
  29.             for (int j = 1; j != N; ++j) {
  30.                 if (obstacleGrid[i][j]) {
  31.                     ret[i][j] = 0;
  32.                 } else {
  33.                     ret[i][j] = ret[i -1][j] + ret[i][j - 1];
  34.                 }
  35.             }
  36.         }
  38.         return ret[M - 1][N - 1];
  39.     }
  40. };

源码分析

错误之处在于初始化第0行和第0列时，未考虑到若第0行/列有一个坐标出现障碍物，则当前行/列后的元素路径数均为0！

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param obstacleGrid: A list of lists of integers
  5.      * @return: An integer
  6.      */
  7.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
  8.         if(obstacleGrid.empty() || obstacleGrid[0].empty()) {
  9.             return 0;
  10.         }
  12.         const int M = obstacleGrid.size();
  13.         const int N = obstacleGrid[0].size();
  15.         vector<vector<int> > ret(M, vector<int>(N, 0));
  17.         for (int i = 0; i != M; ++i) {
  18.             if (obstacleGrid[i][0]) {
  19.                 break;
  20.             } else {
  21.                 ret[i][0] = 1;
  22.             }
  23.         }
  24.         for (int i = 0; i != N; ++i) {
  25.             if (obstacleGrid[0][i]) {
  26.                 break;
  27.             } else {
  28.                 ret[0][i] = 1;
  29.             }
  30.         }
  32.         for (int i = 1; i != M; ++i) {
  33.             for (int j = 1; j != N; ++j) {
  34.                 if (obstacleGrid[i][j]) {
  35.                     ret[i][j] = 0;
  36.                 } else {
  37.                     ret[i][j] = ret[i -1][j] + ret[i][j - 1];
  38.                 }
  39.             }
  40.         }
  42.         return ret[M - 1][N - 1];
  43.     }
  44. };

源码分析

  1. 异常处理
  2. 初始化二维矩阵(全0阵)，尤其注意遇到障碍物时应break跳出当前循环
  3. 递推路径数
  4. 返回ret[M - 1][N - 1]