8-line concise C++ DFS solution with global index (with comments)

  • 1

    When converting local 2D index (i,j) to global 1-D index i*n+j, it is convenient to keep the record of visited cells unordered_set<int> visited.

        int m, n; // maze dimension
        unordered_set<int> visited; // global index of visited cells(i,j) = i*n+j
        bool hasPath(vector<vector<int>>& maze, const vector<int>& s/*start*/, vector<int>& e/*end*/) {
            if(s == e) return true;
            if (visited.empty()) m = maze.size(), n = maze[0].size();
            if(!visited.insert(s[0]*n+s[1]).second) return false; // if already visited
            for(int d:{1, -1, n, -n}) { // global index of each directional vector
              int i=s[0], j=s[1]; 
              while(i*(i-m+1)<=0 && j*(j-n+1)<=0 && !maze[i][j]) i+=d/n, j+=d%n; // go straight
              if(hasPath(maze, {i-=d/n,j-=d%n}, e)) return true; // start from new location (i,j)
            return false;

Log in to reply

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