Simple C++ DFS solution, using set to mark the visited end points


  • 5

    Use set to marked the end points, preventing duplicate search.
    Use go to the end function to move to the end of this direction.

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            set<vector<int>> visited;
            return helper(maze, start, destination, visited);
        }
        bool helper(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination, set<vector<int>>& visited) {
            if(start == destination) return true;
            if(visited.find(start) != visited.end()) return false;
            visited.insert(start);
            vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for(int i = 0; i < 4; i++) {
                vector<int> res = go2End(maze, start, dirs[i]);
                if(res == destination || helper(maze, res, destination, visited)) return true;
            }
            return false;
        }
        vector<int> go2End(vector<vector<int>>& maze, vector<int>& start, vector<int>& dir) {
            int i = start[0] + dir[0];
            int j = start[1] + dir[1];
            int m = maze.size();
            int n = maze[0].size();
            if(i < 0 || i >= m || j < 0 || j >= n || maze[i][j] == 1) {
                return start;
            }
            vector<int> newStart = {i, j};
            return go2End(maze, newStart, dir);
        }
    };
    

  • 0
    L

    First of all, thank you for sharing your sln!
    I think if you generate the search directions inside the helper function based on your current start location and the destination. It might be faster on average.
    I haven't try sth thats really complex. I just simply replace
    "vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};" with the following code:

    vector<vector<int>> dirs;
    int tpi = destination[0] - start[0];
    int tpj = destination[1] - start[1];
    if(tpi>0)
    {
        dirs.push_back(vector<int>({1,0}));
        if(tpj>0)
        {
            dirs.push_back(vector<int>({0,1}));
            dirs.push_back(vector<int>({-1,0}));
            dirs.push_back(vector<int>({0,-1}));
        }
        else
        {
            dirs.push_back(vector<int>({0,-1}));
            dirs.push_back(vector<int>({-1,0}));
            dirs.push_back(vector<int>({0,1}));           
        }
    }
    else
    {
        dirs.push_back(vector<int>({-1,0}));
        if(tpj>0)
        {
            dirs.push_back(vector<int>({0,1}));
            dirs.push_back(vector<int>({1,0}));
            dirs.push_back(vector<int>({0,-1}));
        }
        else
        {
            dirs.push_back(vector<int>({0,-1}));
            dirs.push_back(vector<int>({1,0}));
            dirs.push_back(vector<int>({0,1}));
        }
    }
    

    and the run time is about 99 ms. Not a big deal, but still improved :). I'm sure there's some other smart way to choose directions.


Log in to reply
 

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