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

题目描述链接：https://leetcode-cn.com/problems/robot-in-a-grid-lcci/

解题思路：思路一：DFS,这为一道基本的DFS问题，利用DFS解题的常规思路求解即可。但需要注意的是回溯问题，再回溯的时候由于每个被访问判定失败的节点之后

肯定也不能继续访问成功，所以不需改变vis数组的值，只需将路径中的节点去除掉即可。

LeetCode C++解题代码如下：

class Solution {
public:
    vector<vector<int>>res;
    bool vis[105][105];
    bool flag;
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==0)
            dfs(0,0,obstacleGrid,res);
        if(flag)
           return res;
        vector<vector<int>>empty;
        return empty;
    }
    void dfs(int i,int j,vector<vector<int>>& obstacleGrid,vector<vector<int>>&res){
        if(flag==1){
            return ;
        }
       
        int h=obstacleGrid.size();
        int w=obstacleGrid[0].size();
        vector<int>temp;
        temp.push_back(i);
        temp.push_back(j);
        res.push_back(temp);
        vis[i][j]=1;
        if(i==h-1&&j==w-1){
            flag=1;
            return ;
        }
        if(j+1<w&&obstacleGrid[i][j+1]==0&&vis[i][j+1]==0)
           dfs(i,j+1,obstacleGrid,res);
        if(i+1<h&&obstacleGrid[i+1][j]==0&&vis[i+1][j]==0)
           dfs(i+1,j,obstacleGrid,res);
        if(flag!=1){
           res.pop_back();
        }
        return ;
    }
};