C++刷leetcode（面试题 08.02. 迷路的机器人）【深度优先搜索+回溯】
题目描述：设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。
示例 1:
输入:
[
,
,
]
输出: [,,,,]
解释:
输入中标粗的位置即为输出表示的路径，即
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 == 1) return false;
if(i == input.size()-1 && j == input.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.size()-1 && dfs(input, res, i, j+1)) return true;
res.pop_back();
input = 1;
return false;
}
vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int> > res;
dfs(obstacleGrid, res, 0, 0);
return res;
}
};
页:
[1]