题目描述
设想有个机器人坐在一个网格的左上角，网格 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。
解法
方法一：DFS
我们可以使用深度优先搜索来解决本题。我们从左上角开始，向右或向下移动，直到到达右下角。如果在某一步，我们发现当前位置是障碍物，或者当前位置已经在路径中，那么我们就返回，否则我们将当前位置加入路径中，并且标记当前位置为已经访问过，然后继续向右或向下移动。
如果最终能够到达右下角，那么我们就找到了一条可行的路径，否则说明不存在可行的路径。
时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
def dfs(i, j):
if i >= m or j >= n or obstacleGrid[i][j] == 1:
return False
ans.append([i, j])
obstacleGrid[i][j] = 1
if (i == m - 1 and j == n - 1) or dfs(i + 1, j) or dfs(i, j + 1):
return True
ans.pop()
return False
m, n = len(obstacleGrid), len(obstacleGrid[0])
ans = []
return ans if dfs(0, 0) else []
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private int[][] g;
private int m;
private int n;
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
g = obstacleGrid;
m = g.length;
n = g[0].length;
return dfs(0, 0) ? ans : Collections.emptyList();
}
private boolean dfs(int i, int j) {
if (i >= m || j >= n || g[i][j] == 1) {
return false;
}
ans.add(List.of(i, j));
g[i][j] = 1;
if ((i == m - 1 && j == n - 1) || dfs(i + 1, j) || dfs(i, j + 1)) {
return true;
}
ans.remove(ans.size() - 1);
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> ans;
function<bool(int, int)> dfs = [&](int i, int j) -> bool {
if (i >= m || j >= n || obstacleGrid[i][j] == 1) {
return false;
}
ans.push_back({i, j});
obstacleGrid[i][j] = 1;
if ((i == m - 1 && j == n - 1) || dfs(i + 1, j) || dfs(i, j + 1)) {
return true;
}
ans.pop_back();
return false;
};
return dfs(0, 0) ? ans : vector<vector<int>>();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func pathWithObstacles(obstacleGrid [][]int) [][]int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
ans := [][]int{}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i >= m || j >= n || obstacleGrid[i][j] == 1 {
return false
}
ans = append(ans, []int{i, j})
obstacleGrid[i][j] = 1
if (i == m-1 && j == n-1) || dfs(i+1, j) || dfs(i, j+1) {
return true
}
ans = ans[:len(ans)-1]
return false
}
if dfs(0, 0) {
return ans
}
return [][]int{}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function pathWithObstacles(obstacleGrid: number[][]): number[][] {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
const res = [];
const dfs = (i: number, j: number): boolean => {
if (i === m || j === n || obstacleGrid[i][j] === 1) {
return false;
}
res.push([i, j]);
obstacleGrid[i][j] = 1;
if ((i + 1 === m && j + 1 === n) || dfs(i + 1, j) || dfs(i, j + 1)) {
return true;
}
res.pop();
return false;
};
if (dfs(0, 0)) {
return res;
}
return [];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, path: &mut Vec<Vec<i32>>, i: usize, j: usize) -> bool {
if i == grid.len() || j == grid[0].len() || grid[i][j] == 1 {
return false;
}
path.push(vec![i as i32, j as i32]);
grid[i as usize][j as usize] = 1;
if
(i + 1 == grid.len() && j + 1 == grid[0].len()) ||
Self::dfs(grid, path, i + 1, j) ||
Self::dfs(grid, path, i, j + 1)
{
return true;
}
path.pop();
false
}
pub fn path_with_obstacles(mut obstacle_grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut res = vec![];
if Self::dfs(&mut obstacle_grid, &mut res, 0, 0) {
return res;
}
vec![]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
private var ans = [[Int]]()
private var g: [[Int]] = []
private var m: Int = 0
private var n: Int = 0
func pathWithObstacles(_ obstacleGrid: [[Int]]) -> [[Int]] {
g = obstacleGrid
m = g.count
n = g[0].count
return dfs(0, 0) ? ans : []
}
private func dfs(_ i: Int, _ j: Int) -> Bool {
if i >= m || j >= n || g[i][j] == 1 {
return false
}
ans.append([i, j])
g[i][j] = 1
if (i == m - 1 && j == n - 1) || dfs(i + 1, j) || dfs(i, j + 1) {
return true
}
ans.removeLast()
return false
}
}
|