package medium;

public class Unique_Paths_II {

	class Solution {
		public int uniquePathsWithObstacles(int[][] obstacleGrid) {
			if (obstacleGrid == null || obstacleGrid[0] == null) {
				return 0;
			}
			int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
			dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
			for (int i = 1; i < obstacleGrid[0].length; i++) {
				if (obstacleGrid[0][i] == 1) {
					dp[0][i] = 0;
				} else {
					dp[0][i] = dp[0][i - 1];
				}
			}
			for (int i = 1; i < obstacleGrid.length; i++) {
				if (obstacleGrid[i][0] == 1) {
					dp[i][0] = 0;
				} else {
					dp[i][0] = dp[i - 1][0];
				}
			}
			for (int i = 1; i < dp.length; i++) {
				for (int j = 1; j < dp[0].length; j++) {
					if (obstacleGrid[i][j] == 1) {
						dp[i][j] = 0;
					} else {
						dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
					}
				}
			}
			return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
		}
	}

	public static void main(String[] args) {
		int[][] obstacleGrid = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
		System.out.println(new Unique_Paths_II().new Solution().uniquePathsWithObstacles(obstacleGrid));
	}

}
