63. Unique Paths II

LeetCode

这题就是Unique Paths的变种，区别在于增加了一些边界条件：

  • 如果(x, y)有障碍，由于不可达，f(x, y) = 0。
  • 如果(0, 0)有障碍，f(row - 1, column - 1) = 0
  • 如果第0行上有障碍，由于机器人只能向下或向右走，障碍右侧的格子均不可达
  • 如果第0列上有障碍，由于机器人只能向下或向右走，障碍下侧的格子均不可达

// TODO: 补图

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;
        int[][] f = new int[row][column];
        f[0][0] = 1;

        // 1. find the start of invalid row index
        int startOfInvalidRowIndex = row;
        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] == 1 && i < startOfInvalidRowIndex) {
                startOfInvalidRowIndex = i;
            }
            if (i >= startOfInvalidRowIndex) {
                f[i][0] = 0;
            } else {
                f[i][0] = 1;
            }
        }

        // 2. find the start of invalid column index
        int startOfInvalidColumnIndex = column;
        for (int j = 0; j < column; j++) {
            if (obstacleGrid[0][j] == 1 && j < startOfInvalidColumnIndex) {
                startOfInvalidColumnIndex = j;
            }
            if (j >= startOfInvalidColumnIndex) {
                f[0][j] = 0;
            } else {
                f[0][j] = 1;
            }
        }

        // 3. calculate f (set the value of invalid grids to 0)
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }

        return f[row - 1][column - 1];
    }
}