6ms C++ BFS with brief explanation, beat 92.58%


  • 0
    S

    dis[i][j]: accumulated distance at (i,j)
    grid[i][j]: 1 - building; 2 - obstacle; other negative numbers - times that position has been visited.

    I used grid to mark if an empty position has been visited in the current round. And at last, I only checked dis at those positions where the times of visiting is equal to the total number of buildings (some of the buildings might not be accessible for some empty positions).

    class Solution {
        const vector<int> dir = {0,1,0,-1,0};
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            if(grid.size()==0||grid[0].size()==0) return -1;
            int row = grid.size();
            int col = grid[0].size();
            vector<vector<int>> dis(row, vector<int>(col,0));
            int id = 0;  // the id of current building
    
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    if(grid[i][j]==1){
                        // BFS
                        queue<pair<int,int>> Q;
                        int d = 1; // distance from the current building
                        int currcount = 0;  // number of positions with distance d
                        int nextcount = 0; // number of positions with distance d+1
                        for(int k=0; k<4; k++){
                            int ii = i+dir[k]; int jj = j+dir[k+1];
                            if(ii>=0&&ii<row && jj>=0&&jj<col && grid[ii][jj]==id){
                                grid[ii][jj]--;
                                dis[ii][jj] += d;
                                Q.push(make_pair(ii,jj));
                                currcount++;
                            }
                        }
                        while(!Q.empty()){
                            int curri = Q.front().first;
                            int currj = Q.front().second;
                            Q.pop();
                            currcount--;
                            for(int k=0; k<4; k++){
                                int ii = curri+dir[k]; int jj = currj+dir[k+1];
                                if(ii>=0&&ii<row && jj>=0&&jj<col && grid[ii][jj]==id){
                                    grid[ii][jj]--;
                                    dis[ii][jj] += d+1;
                                    Q.push(make_pair(ii,jj));
                                    nextcount++;
                                }
                            }
                            if(currcount==0){
                                currcount = nextcount;
                                nextcount = 0;
                                d++;
                            }
                        }
                        id--;
                    }
                }
            }
    
            int mindis = INT_MAX;
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    if(grid[i][j]==id){  // only check those positions that can reach all the buildings
                        mindis = min(mindis,dis[i][j]);
                    }
                }
            }
            return mindis==INT_MAX?-1:mindis;
        }
    };
    

Log in to reply
 

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