Note: This article is available in Chinese only. 本文暂无英文版本。
View original
Follow up for “Unique Paths”:
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.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
1[
2 [0,0,0],
3 [0,1,0],
4 [0,0,0]
5]The total number of unique paths is 2.
题意：从左上到右下的方案数，有些点不能走。
思路：简单dp…1A
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月11日 星期二 18时37分47秒
4File Name :63.cpp
5************************************************ */
6class Solution {
7public:
8 int n,m;
9 void pr(vector<vector<int> > & a)
10 {
11 for ( int i = 0 ; i < n ; i++)
12 for ( int j = 0 ;j < m ; j++)
13 printf("%d%c",a[i][j],j==m-1?'\n':' ');
14 }
15 int uniquePathsWithObstacles(vector<vector<int>>& maze) {
16 n = maze.size();
17 m = maze[0].size();
18 vector<vector<int> >dp(n,vector<int>(m,0));
19 bool sad = false;
20 for ( int i = 0 ; i < n ; i++)
21 {
22 if (maze[i][0]==1) sad = true;
23 if (sad) dp[i][0] = 0 ;
24 else dp[i][0] = 1;
25 }
26 sad = false;
27 for ( int j = 0 ; j < m ; j++)
28 {
29 if (maze[0][j]==1) sad = true;
30 if (sad) dp[0][j] = 0 ;
31 else dp[0][j] = 1;
32 }
33// pr(dp);
34 for ( int i = 1 ; i < n ; i++)
35 {
36 for ( int j = 1 ; j < m ; j++)
37 {
38 if (maze[i][j]==1) dp[i][j]=0;
39 else dp[i][j] = dp[i-1][j] + dp[i][j-1];
40 }
41 }
42// pr(dp);
43 return dp[n-1][m-1];
44 }
45};