# 6ms c++ BFS solution beats 97.09%

• tiny improvement from StefanPochmann's BFS search version (great idea on traversing reachable-by-all-past-building only cells, which dramatically reduces search space)

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
if(!grid.size()||!grid[0].size())return -1;
int m=grid.size(),n=grid[0].size();

int dx[]={-1,1,0,0},dy[]={0,0,-1,1},dis,bnum=0;
int vsum[m][n];
for(int i=0;i<m;i++)fill_n(vsum[i],n,0);
int result=INT_MAX;

for(int i=0;i<m;i++)for(int j=0;j<n;j++){
if(grid[i][j]==1){
result=INT_MAX,dis=1;
queue<pair<int,int>>q;
q.push({i,j});
while(!q.empty()){
int cnt=q.size();
for(int i=0;i<cnt;i++){
pair<int,int>n1=q.front();q.pop();
for(int j=0;j<4;j++){
int a=n1.first+dx[j],b=n1.second+dy[j];
if(a<0||a>=m||b<0||b>=n||grid[a][b]!=-bnum)continue;
vsum[a][b]+=dis,grid[a][b]--;
result=min(result,vsum[a][b]);
q.push({a,b});
}
}
dis++;
}
bnum++;
}
}
return result==INT_MAX?-1:result;
}
};
``````

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