C++ dfs


  • 0
    B

    class Solution {
    public:
    bool result=false;
    int m,n;
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    m=maze.size(),n=maze.size()?maze[0].size():0;
    vector<vector<vector<bool>>> choose(m,vector<vector<bool>>(n,vector<bool>(4,true)));
    dfs(maze,start[0],start[1],destination,choose);
    return result;
    }

    void dfs(vector<vector<int>> &maze,int i,int j, vector<int>& destination,vector<vector<vector<bool>>> &choose)
    {
        if(i==destination[0] && j==destination[1])result=true;
        if(result)return;
        int k;
        for(k=0;k<4;k++)
        {
            if(choose[i][j][k])
            {
                choose[i][j][k]=false;
                int x=i+dir[k],y=j+dir[k+1];
                if(x>=0 && y>=0 && x<m && y< n && maze[x][y]==0)
                {
                    while(x>=0 && y>=0 && x<m && y< n && maze[x][y]==0)
                    {
                        x+=dir[k];y+=dir[k+1];
                    }
                    dfs(maze,x-dir[k],y-dir[k+1],destination,choose);
                    
                }
            }
            
        }
        return;
    }
    int dir[5]={0,1,0,-1,0};
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.