LeetCode 面试题 08.02. 迷路的机器人

一、题目

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

  点击此处跳转题目。

二、C# 题解

  可以使用回溯解，这里用动态规划好些。使用 path 记录当前位置是否能到达终点，因此从终点开始向起点方向进行判断，当前 path[i, j] 的值为 obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1])，即当前无障碍物且后方有可到达路径。对于边界情况需要优先特殊处理，以免数组越界。

public class Solution {
    public IList<IList<int>> PathWithObstacles(int[][] obstacleGrid) {
        int r = obstacleGrid.Length, c = obstacleGrid[0].Length;
        IList<IList<int>> ans = new List<IList<int>>();
        bool[,] path = new bool[r, c]; // 记录可到达路径

        if (obstacleGrid[r - 1][c - 1] == 1) return ans; // 如果终点有障碍物，直接返回空

        /* 动态规划求解可到达路径 */
        path[r - 1, c - 1] = true;
        // 最右方边界判断
        for (int j = c - 2; j >= 0; j--)
            if (path[r - 1, j + 1] && obstacleGrid[r - 1][j] == 0)
                path[r - 1, j] = true;
        // 最下方边界判断
        for (int i = r - 2; i >= 0; i--)
            if (path[i + 1, c - 1] && obstacleGrid[i][c - 1] == 0)
                path[i, c - 1] = true;
        // 中间判断
        for (int i = r - 2; i >= 0; i--)
        for (int j = c - 2; j >= 0; j--)
            if (obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1]))
                path[i, j] = true;

        if (!path[0, 0]) return ans; // 如果起点没有可到达路径，返回空

        /* 求解一条可到达路径 */
        int x = 0, y = 0;
        while (x != r - 1 || y != c - 1) {
            ans.Add(new List<int> { x, y });      // 添加路径
            if (y + 1 < c && path[x, y + 1]) y++; // 优先向右走
            else x++;                             // 右方堵住则向下走
        }
        ans.Add(new List<int> { r - 1, c - 1 });  // 添加终点

        return ans;
    }
}
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
27
28
29
30
31
32
33
34
35
36
37
38

• 时间：132 ms，击败 100.00% 使用 C# 的用户
• 内存：42.62 MB，击败 100.00% 使用 C# 的用户