gold-8-2

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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
            return new ArrayList<>();
        }

        boolean[][] f = new boolean[obstacleGrid.length][obstacleGrid[0].length];

        Queue<Integer> myQ = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        int row = obstacleGrid.length - 1;
        int column = obstacleGrid[0].length - 1;

        if (obstacleGrid[row][column] == 1) {
            return new ArrayList<>();
        }
        myQ.add(row);
        myQ.add(column);

        while (!myQ.isEmpty()) {
            row = myQ.poll();
            column = myQ.poll();
            f[row][column] = true;

            if (row > 0 && obstacleGrid[row - 1][column] == 0 && !visited.contains("" + (row - 1) + "-" + column)) {
                myQ.add(row - 1);
                myQ.add(column);
                visited.add("" + (row - 1) + "-" + column);
            }
            if (column > 0 && obstacleGrid[row][column - 1] == 0 && !visited.contains("" + row + "-" + (column - 1))) {
                myQ.add(row);
                myQ.add(column - 1);
                visited.add("" + row + "-" + (column - 1));
            }
        }

        if (!f[0][0]) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        row = 0;
        column = 0;

        while (!(row == obstacleGrid.length - 1 && column == obstacleGrid[0].length - 1)) {
            List<Integer> one = new ArrayList<>();
            one.add(row);
            one.add(column);
            result.add(one);

            if (row < obstacleGrid.length - 1 && f[row + 1][column]) {
                row++;
            } else {
                column++;
            }
        }

        List<Integer> one = new ArrayList<>();
        one.add(row);
        one.add(column);
        result.add(one);
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)