这道题是Unique Path的续集。
题意:输入一个二维数组,这个二维数组的元素如果是0,表示对应网格处没有障碍,可以正常向下或向右移动;如果这个数字是1,表示对应网格处有个障碍,机器人?将不能通过。
思路:
(1)首先我们考虑一下特殊情况。如果第一个网格或最后一个网格对应的数字为1,那么意味着是不可达的,因此直接返回0即可。
(2)排除掉这两种情况后,我们还是先生成一个二维数组 dp,dp[i][j]表示走到图中第 i 行第 j 列个网格点共有多少种走法。首先考虑第一行。如果某个位置的 obstacle[0][j] = 1
,那么这个网格点以及它右面和它下面的其他网格点都无法到达,因此我们需要一个标记 flag 来表示是否遇到了 obstacle = 1的情况。如果 flag = true
,那么dp[0][j] = 1
。只有当 flag != true && obstacle[0][j] != 1
时,有 dp[0][j] = 1
。第一列也是类似的。
(3)然后考虑第 i 行第 j 列的网格点。对于 dp[i][j] 来说,如果 obstacle[i][j] = 0
,那么 dp[i][j] = dp[i-1][j] + dp[i][j-1]
;如果obstacle[i][j] = 1
,那么 dp[i][j] = 0
。这就是该题的状态转移方程。
代码如下:
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int> > dp(m,vector<int>(n)); bool flag = false; if(obstacleGrid[0][0] == 1) { return 0; } for(int i = 0; i < m; i++) { if (obstacleGrid[i][0] != 1 && !flag) { dp[i][0] = 1; } else { if (obstacleGrid[i][0] == 1) { flag = true; dp[i][0] = 0; } else if (flag) { dp[i][1] = 0; } } } flag = false; for(int i = 1; i < n; i++) { if (obstacleGrid[0][i] != 1 && !flag) { dp[0][i] = 1; } else { if (obstacleGrid[0][i] == 1) { flag = true; dp[0][i] = 0; } else if (flag) { dp[0][i] = 0; } } } for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = obstacleGrid[i][j] != 1 ? dp[i-1][j] + dp[i][j-1] : 0; } } return dp[m-1][n-1] = obstacleGrid[m-1][n-1] != 1?dp[m-1][n-1]:0; } }; |