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

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

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