LeetCode | Unique Path 2

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.

Note: m and n will be at most 100.

思路：只不过与上面一个区别就是有一个障碍点，在这个障碍点上 dp[i][j] = 0;

int Unique_path(int m,int n,int first,int second)
{
	vector<vector<int> > dp(m+1);
	int i,j;
	for(i=0;i<dp.size();i++)
		dp[i].assign(n+1,0);
	dp[0][0] =1;
	for(i=0;i<dp.size();i++)
	{
		for(j=0;j<dp[0].size();j++)
		{
			if(i!=0 || j!=0)
			{
				if(i == first && j == second)
					dp[i][j] =0;
				else
				{
				if(i==0)
					dp[i][j] = dp[i][j-1];
				else if(j == 0) 
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = dp[i][j-1] + dp[i-1][j];	
				}
				
			}
			
		}
	}			
	return dp[m][n];
}
int main()
{
	cout<<Unique_path(3,7,2,3)<<endl;	
	return 0;
}

LeetCode | Unique Path 2

原文：http://blog.csdn.net/yusiguyuan/article/details/44652539