# 20ms C++ solution with early pruning

• 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;
}
};``````

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