leetocde 63. Unique Paths II

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.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

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};