题解 | #不同路径的数目(二)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param obstacleGrid int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    public int uniquePathsWithObstacles(ArrayList<ArrayList<Integer>> obstacleGrid) {
        // write code here
        int m = obstacleGrid.size();
        int n = obstacleGrid.get(0).size();

        if (1 == m && 1 == n && obstacleGrid.get(0).get(0) == 0) {
            return 0;
        }

        int[][] paths = new int[m][n];
        paths[0][0] = 1;
        for (int currentY = 1; currentY < n; currentY++) {
            if (obstacleGrid.get(0).get(currentY) == 0) {
                break;
            }
            paths[0][currentY] = 1;
        }
        for (int currentX = 1; currentX < m; currentX++) {
            if (obstacleGrid.get(currentX).get(0) == 0) {
                break;
            }
            paths[currentX][0] = 1;
        }
        for (int currentX = 1; currentX < m; currentX++) {
            for (int currentY = 1; currentY < n; currentY++) {
                if (obstacleGrid.get(currentX).get(currentY) == 0) {
                    paths[currentX][currentY] = 0;
                } else {
                    paths[currentX][currentY] = paths[currentX - 1][currentY] + paths[currentX][currentY - 1];
                }
            }
        }
        return paths[m - 1][n - 1];
    }
}