面试题 08.02. 迷路的机器人

题目

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动， 但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。

图片

网格中的障碍物和空位置分别用 1 和 0 来表示。

返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。

示例1:
输入:

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]

解释:
输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）

说明：r和 c 的值均不超过 100。

题解

public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
    int rows = obstacleGrid.length, columns = obstacleGrid[0].length;

    // dp记录可从起点可到达的点
    boolean[][] dp = new boolean[rows][columns];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            // 记录每个格子是否连通
            dp[i][j] = obstacleGrid[i][j] != 1 && (i - 1 < 0 || dp[i - 1][j] || j - 1 < 0 || dp[i][j - 1]);
        }
    }

    List<List<Integer>> result = new ArrayList<>();
    // 如果终点不可达 直接返回结果
    if (!dp[rows - 1][columns - 1]) {
        return result;
    }


    // 记录访问过的点 不重复走
    boolean[][] visited = new boolean[rows][columns];
    BiFunction<Integer, Integer, Boolean> backtrack = new BiFunction<Integer, Integer, Boolean>() {
        @Override
        public Boolean apply(Integer row, Integer column) {
            // 越界或者路障
            if (row >= rows || column >= columns || !dp[row][column] || visited[row][column]) {
                return false;
            }

            result.add(Arrays.asList(row, column));
            visited[row][column] = true;
            // 终点
            if (row == rows - 1 && column == columns - 1) {
                return true;
            }

            // 向下
            if (this.apply(row + 1, column)) {
                return true;
            }

            // 向右
            if (this.apply(row, column + 1)) {
                return true;
            }

            // 回溯
            result.remove(result.size() - 1);

            return false;
        }
    };

    backtrack.apply(0, 0);

    return result;
}