英文原文
Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
"off limits" and empty grid are represented by 1 and 0 respectively.
Return a valid path, consisting of row number and column number of grids in the path.
Example 1:
Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: [[0,0],[0,1],[0,2],[1,2],[2,2]]
Note:
r, c <= 100
中文题目
设想有个机器人坐在一个网格的左上角，网格 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。
通过代码
高赞题解
目标：
找到一条从左上角走到右下角路径，如果没有这样的路径返回空数组。
规则：
从左上角走到右下角，每次只能向下走或者向右走。
明确回溯法四要素：
- 结束条件：走到右下角就结束；右下角本身有障碍物，不可能走得到；
- 路径：走到当前位置之前已经走过的路径。
- 选择：每次只能向下走或者向右走。当下方有障碍物时，只能考虑向右走；当右方有障碍物时，只能考虑向下走；当下方和右方都有障碍物时，只能往回走，你从哪个地方进入这个死胡同的就回到哪个地方去。
- 约束条件：除了在“选择中的”约束之外，我们还不能走已经走过的地方。
代码：
以$x,y$表示当前位置，一个与网格同大小的数组$visit$记录走过的地方。
class Solution {
List<List<Integer>> path = new LinkedList<>(); // 记录路径
int r = 0; // 行数
int c = 0; // 列数
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
r = obstacleGrid.length;
if (r == 0) { // 空网格
return path;
}
c = obstacleGrid[0].length;
if (obstacleGrid[r - 1][c - 1] == 1) { // 终点有障碍
return path;
}
boolean[][] visit = new boolean[r][c]; // 记录数组
backtrack(obstacleGrid, 0, 0, visit);
return path;
}
public boolean backtrack(int[][] obstacleGrid, int x, int y, boolean[][] visit) {
// 越界，有障碍，已访问
if (x >= r || y >= c || obstacleGrid[x][y] == 1 || visit[x][y]) {
return false;
}
// 如果不是以上情况，说明这个格子值得探索，做出选择
path.add(Arrays.asList(x, y));
visit[x][y] = true;
// 选择后是否到达终点
if (x == r - 1 && y == c - 1) {
return true;
}
// 选择后没到终点，先尝试向下，再尝试向右，神奇的或运算
if (backtrack(obstacleGrid, x + 1, y, visit) || backtrack(obstacleGrid, x, y + 1, visit)) {
return true;
}
// 既不能向下也不能向右，是个死胡同，撤销选择
path.remove(path.size() - 1);
return false;
}
}算法分析：
以$r,c$分别表示网格的行和列。
- 遍历一次网格的所有格子，每个格子仅访问一次，时间复杂度为$O(r \times c)$.
- 不考虑递归使用栈辅助空间，辅助记录数组$O(r \times c)$，几个变量$O(1)$，$path$链表记录路径$O(r+c-2)=O(r+c)$，因此总的空间复杂度为$O(r \times c)$.
$path$的大小怎么算？
答：对于$r$行$c$列的网格，从左上角出发，每次只能向下或者向右走，要到达右下角，任何路径都要包括$r-1$次向下走，$c-1$次向右走。
如果本文对你有帮助，可以给一个大拇指呀！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 13100 | 36339 | 36.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
