C++ BFS version, Easy to understand


  • 0
    Y
    class Solution {
    private:
        std::string getHash(int left, int right) {
            ostringstream oss;
            oss << left << '-' << right;
            return oss.str();
        }
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            static vector<pair<int,int>> directions = {{1,0},{0,1},{-1,0},{0,-1}};
            if (maze.empty()) return false;
            const int row_size(maze.size()), col_size(maze[0].size());
            unordered_set<std::string> visited;
            queue<pair<int, int>> nodes;
            nodes.push(make_pair(start[0], start[1]));
            visited.insert(getHash(start[0], start[1]));
            
            while (!nodes.empty()) {
                int x = nodes.front().first, y = nodes.front().second;
                nodes.pop();
                if (x == destination[0] && y == destination[1]) return true;
                for (const pair<int, int> &dir : directions) {
                    int xx(x), yy(y);
                    
                    // Begin rolling
                    while (xx >= 0 && xx < row_size 
                        && yy >= 0 && yy < col_size 
                        && maze[xx][yy] == 0) {
                        xx += dir.first;
                        yy += dir.second;
                    }
                    
                    // Crossed border, go one step back
                    xx -= dir.first;
                    yy -= dir.second;
                        
                    if (visited.count(getHash(xx, yy)) == 0) {
                        visited.insert(getHash(xx, yy));
                        nodes.push(make_pair(xx, yy));
                    }    
                }
                
            }
            
            return false;
        }
    };
    

Log in to reply
 

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