C++ BFS solution


  • 0
    F

    BFS can tell us which position can be arrived.
    When we do the BFS, we update the distance at the same time.
    If other paths give us shorter distance, we visit that position one more time.

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            int rows=(int)maze.size(); 
            int cols=(int)maze[0].size(); 
            vector<vector<int>> maze_2 (rows, vector<int> (cols, 0)); 
            
            for(int i=0; i<rows; i++) {
                for(int j=0; j<cols; j++) {
                    if(maze[i][j]==1)
                        maze_2[i][j]=-1;
                    else
                        maze_2[i][j]=INT_MAX; 
                }
            }
            
            queue<vector<int>> my_queue;
            my_queue.push(start);
            maze_2[start[0]][start[1]]=0;
            
            while(my_queue.size()!=0) {
                vector<int> now=my_queue.front(); 
                my_queue.pop(); 
                
                int dis=maze_2[now[0]][now[1]];
                
                // up
                int tr=now[0]; 
                int tc=now[1];
                int step=0; 
                while(tr>0 && maze[tr-1][tc]!=1) {
                    tr--; 
                    step++; 
                }
                if(dis+step<maze_2[tr][tc]) {
                    maze_2[tr][tc]=dis+step; 
                    my_queue.push({tr, tc}); 
                }
                 
                // down
                tr=now[0]; tc=now[1]; step=0; 
                while(tr<rows-1 && maze[tr+1][tc]!=1) {
                    tr++; 
                    step++; 
                }
                if(dis+step<maze_2[tr][tc]) {
                    maze_2[tr][tc]=dis+step; 
                    my_queue.push({tr, tc}); 
                }
                
                // left
                tr=now[0]; tc=now[1]; step=0; 
                while(tc>0 && maze[tr][tc-1]!=1) {
                    tc--; 
                    step++; 
                }
                if(dis+step<maze_2[tr][tc]) {
                    maze_2[tr][tc]=dis+step; 
                    my_queue.push({tr, tc}); 
                }
                
                // right
                tr=now[0]; tc=now[1]; step=0; 
                while(tc<cols-1 && maze[tr][tc+1]!=1) {
                    tc++; 
                    step++; 
                }
                if(dis+step<maze_2[tr][tc]) {
                    maze_2[tr][tc]=dis+step; 
                    my_queue.push({tr, tc}); 
                }
            }
            
            if(maze_2[destination[0]][destination[1]]==INT_MAX)
                return -1; 
            return maze_2[destination[0]][destination[1]]; 
        }
    };

Log in to reply
 

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