|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 设想有个机器人坐在一个网格的左上角,网格 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。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/robot-in-a-grid-lcci
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- bool dfs(vector<vector<int> > &input, vector<vector<int> >&res, int i, int j){
- if(input[i][j] == 1) return false;
- if(i == input.size()-1 && j == input[0].size()-1){
- res.push_back({i, j});
- return true;
- }
- res.push_back({i, j});
- if(i+1 <= input.size()-1 &&dfs(input, res, i+1, j)) return true;
- if(j + 1 <= input[0].size()-1 && dfs(input, res, i, j+1)) return true;
- res.pop_back();
- input[i][j] = 1;
- return false;
- }
- vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
- vector<vector<int> > res;
- dfs(obstacleGrid, res, 0, 0);
- return res;
- }
- };
复制代码 |
|