/****************************
   Name:  Unique Paths II 
   Date: 02/01/2016
   Author: Hualin Li
   Description: This is the Unique Paths II in the C++. 还是DP大法
   做题感想：这道题和走楼梯有着异曲同工之妙。解题的诀窍在于列出DP公式如下：
   dp[i][j]=dp[i][j-1]+dp[i-1][j]。同时，要理解一点:如果该路径变成一维的，
   无论是横看的一维还是竖着看的一维，都只有一种走法。
   
   和I差别的是有个障碍物，多了几行程序。大家只要记住，在一维的情况下，dp（i）（0）
   还有路走的两个条件是dp（i-1）（0）还有路走，且dp（i）（0）本身不是障碍。在列dp
   方程的时候，记得加一句判断当前的dp（i）（j）是否是障碍，如果是，则此路不通，就要
   归零，然后继续用dp方程。
   
   PS：第一次在leetcode里面，差一点做到写code调试一气呵成。还是有点小开心。白天调用framework的
   郁闷暂时忘记了一会儿。
   
*****************************/
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    //If the whole stuff is empty
	if(obstacleGrid.empty()||obstacleGrid[0].empty())
		return 0;
    //To get the size of vector
	int m=obstacleGrid.size();
	int n=obstacleGrid[0].size();
	
	int dp[m][n];
	dp[0][0] = (obstacleGrid[0][0] == 0 ? 1 : 0);
	//To initialize the 1-D cases
    for(int i=1;i<m;i++)
    dp[i][0]=(dp[i-1][0]==1 && obstacleGrid[i][0]==0)?1:0;

    for(int j=1;j<n;j++)
	dp[0][j]=(dp[0][j-1]==1 && obstacleGrid[0][j]==0)?1:0;

    //The dp equation is from here
	for(int k=1;k<m;k++)
	{
		for(int l=1;l<n;l++)
		{
			if(obstacleGrid[k][l]==1)
				dp[k][l]=0;
			else
			dp[k][l]=dp[k-1][l]+dp[k][l-1];
		}
	}
	
     return dp[m-1][n-1];
	
    }