#yyds干货盘点# LeetCode程序员面试金典：迷路的机器人

题目：

设想有个机器人坐在一个网格的左上角，网格 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列（右下角）

代码实现：

class Solution {

    static List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        result.clear();
        if (obstacleGrid[0][0] == 1) return result;
        dfs(obstacleGrid, obstacleGrid.length-1, obstacleGrid[0].length-1);
        return result;
    }

    public boolean dfs(int[][] obstacleGrid, int i, int j) {
        if (i==0 && j==0) {
            add(i, j);
            return true;
        }

        if (obstacleGrid[i][j] > 0) return false;
        obstacleGrid[i][j] = 2;
        if (i>0 && dfs(obstacleGrid, i-1, j)) {
            add(i, j);
            return true;
        }
        if (j>0 && dfs(obstacleGrid, i, j-1)) {
            add(i, j);
            return true;
        }
        //不取消标记
        //obstacleGrid[i][j] = 2;
        return false;
    }

    public void add(int i, int j){
        List<Integer> list = new ArrayList<>();
        list.add(i);
        list.add(j);
        result.add(list);
    }
}