# C++ Solution using BFS

• ``````class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int ans;
if(!grid.size())
return -1;
int n = grid.size(), m = grid[0].size();
int cnt = 3;
vector<vector<int> > vis(n, vector<int>(m)), reachhousecnt(n, vector<int>(m));
vector<vector<int> > mp(n, vector<int>(m)), tmp(n, vector<int>(m));
ans = INT_MAX;
bool hasempty = false, reachtoAllhouse = false;
int houseTot = 0;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
if(grid[i][j] == 0)
hasempty = true;
if(grid[i][j] == 1){
queue<pair<int,int>> q;
q.push(make_pair(i, j));
tmp[i][j] = mp[i][j] = 0;
++ houseTot;
while(!q.empty()){
pair<int,int> cur = q.front();
q.pop();
for(int k = 0; k < 4; ++ k){
int ntx = cur.first + dir[k][0], nty = cur.second + dir[k][1];
if(ntx >= 0 && ntx < n && nty >= 0 && nty < m && grid[ntx][nty] == 0 && vis[ntx][nty] != cnt){
mp[ntx][nty] += (tmp[cur.first][cur.second] + 1);
tmp[ntx][nty] = tmp[cur.first][cur.second] + 1;
vis[ntx][nty] = cnt;
++ reachhousecnt[ntx][nty];
q.push(make_pair(ntx, nty));
}
}
}
++ cnt;
}
}
}

if(!hasempty)
return -1;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
if(grid[i][j] == 0 && reachhousecnt[i][j] == houseTot){
ans = min(ans, mp[i][j]);
reachtoAllhouse = true;
}
}
}

return ans == INT_MAX?-1:ans;
}
private:
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
};``````

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