力扣面试题 08.02. 迷路的机器人

本文主要是介绍力扣面试题 08.02. 迷路的机器人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

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

示例

输入:
[
[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列（右下角）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/robot-in-a-grid-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：回溯+剪枝

1、机器人只能向下或者向右走。指定directions数组来控制方向移动。
2、走过的路设为1，避免重复走和走不通的情况。

Java实现

class Solution {List<List<Integer>> res = new ArrayList<>();int[] directions = new int[]{1, 0, 1};int row, col;public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {row = obstacleGrid.length;col = obstacleGrid[0].length;List<List<Integer>> track = new ArrayList<>();track_back(obstacleGrid, track, 0, 0);return res;}public void track_back(int[][] obstacleGrid, List<List<Integer>> track, int m, int n) {if (m >= row || m < 0 || n >= col || n < 0 || obstacleGrid[m][n] == 1) return;track.add(Arrays.asList(m, n));obstacleGrid[m][n] = 1;//走到右下角if (m == row - 1 && n == col - 1) {res.addAll(track);return;}for (int i = 0; i < directions.length - 1; i++) {track_back(obstacleGrid, track, m + directions[i], n + directions[i + 1]);}track.remove(track.size() - 1);}
}