题目

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

解答 & 代码

动态规划

二维的动态规划数组 dp：
- 若 dp[i][j] = -1，代表第 i 行第 j 列的格子无法到达（所有元素初始化为 -1）
- 若 dp[i][j] = 1，代表第 i 行第 j 列的格子可以从其左边一格走过来
- 若 dp[i][j] = 2，代表第 i 行第 j 列的格子可以从其上面一格走过来
状态转移：
- 如果当前格子的上面一格可以到达，并且当前格不是障碍，则 dp[i][j] = 2，代表可以从上面一格走过来
- 如果当前格子的左边一格可以到达，并且当前格不是障碍，则 dp[i][j] = 1，代表可以从左边一格走过来
- 否则不变，dp[i][j] 仍为初始化的 -1，代表不能到达

初始化：

若起点位置不是障碍，则令起点的 dp[0][0] = 1，代表可以从左边的格子走过来（实际上只要让它不是 -1 即可）
初始化第一行：如果左边一格可以到达，并且当前格不是障碍，则 dp[0][j] = 1，代表可以从左边一格走过来

初始化第一列：如果上面一格可以到达，并且当前格不是障碍，则 dp[i][0] = 2，代表可以从上面一格走过来

class Solution {
public:
vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
   vector<vector<int>> path;            // 路径
   if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
       return path;

   int rows = obstacleGrid.size();        // 行数
   int cols = obstacleGrid[0].size();    // 列数

   // 动态规划数组 dp，
   // 若 dp[i][j] = -1，代表第 i 行第 j 列的格子无法到达（所有元素初始化为 -1）
   // 若 dp[i][j] = 1，代表第 i 行第 j 列的格子可以从其左边一格走过来
   // 若 dp[i][j] = 2，代表第 i 行第 j 列的格子可以从其上面一格走过来
   vector<vector<int>> dp(rows, vector<int>(cols, -1));

   // 初始化：如果起点位置不是障碍，则 dp[0][0] = 1（实际上 = 2 也行）
   if(obstacleGrid[0][0] == 0)
       dp[0][0] = 1;
   // 初始化第 0 行
   for(int col = 1; col < cols; ++col)
   {
       if(dp[0][col - 1] != -1 && obstacleGrid[0][col] == 0)
           dp[0][col] = 1;
   }
   // 初始化第 0 列
   for(int row = 1; row < rows; ++row)
   {
       if(dp[row - 1][0] != -1 && obstacleGrid[row][0] == 0)
           dp[row][0] =  2;
   }

   // 状态转移，求 dp 数组的各元素值
   for(int row = 1; row < rows; ++row)
   {
       for(int col = 1; col < cols; ++col)
       {
           if(dp[row - 1][col] != -1 && obstacleGrid[row][col] == 0)
               dp[row][col] = 2;
           if(dp[row][col - 1] != -1 && obstacleGrid[row][col] == 0)
               dp[row][col] = 1;
       }
   }

   // 如果终点不能到达，直接返回空路径
   if(dp[rows - 1][cols - 1] == -1)
       return path;
   // 根据 dp 数组中存储的到达每格的上一格方向，可以从终点走回起点，将一路上的点存储到路径
   int row = rows - 1;
   int col = cols - 1;
   while(row != 0 || col != 0)
   {
       path.push_back({row, col});
       if(dp[row][col] == 1)
           col = col - 1;
       else if(dp[row][col] == 2)
           row = row - 1;
   }
   path.push_back({0, 0});
   // 将路径逆序
   reverse(path.begin(), path.end());
   return path;
}
};

执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 98.91% 的用户内存消耗：8.8 MB, 在所有 C++ 提交中击败了 81.72% 的用户 ```

CodeTop 企业题库

[中等] 程序员面试金典 8.2 迷路的机器人

题目

解答 & 代码