20ms C++ solution with early pruning


  • 1
    Z

    Use a 2D vector visited to preform early pruning.
    Avoid visiting those lands which are:

    1. already visited in the searching of current building; (visited[i][j] > cnt)
    2. can't be reached by previous buildings; (visited[i][j] < cnt)

    (cnt means the number of buildings that can reach this land)

    This actually saves a lot of time.

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            if(grid.size()==0) return 0;
            int m=grid.size(), n=grid[0].size(), cnt=0, minDistance=INT_MAX;
            int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
            vector<vector<int>> visited(m, vector<int>(n, 0));
            for(int i=0; i<m; i++){ //modify the grid
                for(int j=0; j<n; j++){
                    if(grid[i][j]==2) grid[i][j]=-2;
                    if(grid[i][j]==1) grid[i][j]=-1;
                }
            }
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(grid[i][j]==-1){ 
                       queue<pair<pair<int, int>, int>> q;  //  ((x, y), step)
                       q.push(make_pair(make_pair(i, j),0)); 
                       while(!q.empty()){
                          auto cur=q.front();
                          q.pop();
                          for(int k=0; k<4; k++){ //push neighbor
                             int x=cur.first.first+dx[k];
                             int y=cur.first.second+dy[k];
                             if(x<0||x>=m||y<0||y>=n||grid[x][y]<0||visited[x][y]!=cnt) continue; //early pruning
                             visited[x][y]++;
                             grid[x][y]+=cur.second+1;
                             q.push(make_pair(make_pair(x, y), cur.second+1));
                         }
                       }
                       cnt++;
                    }
                }
            }
            for(int i=0; i<m; i++){  //find the minDistance
                for(int j=0; j<n; j++){
                    if(visited[i][j]==cnt){
                        minDistance=min(minDistance, grid[i][j]);
                    }
                }
            }
            return minDistance==INT_MAX? (-1): minDistance;
        }
    };

Log in to reply
 

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