# 50 lines Concise and easy understand c++ solution BFS

• ``````class Solution {
private:
vector<pair<int, int>> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
int shortestDistance(vector<vector<int>>& grid) {
if(grid.size() == 0 || grid[0].size() == 0) return -1;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> visitedCount(grid.size(), vector<int>(grid[0].size(), 0));
vector<pair<int, int>> buildings;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) buildings.push_back(make_pair(i, j));
grid[i][j] *= -1;
}
}
for(int i = 0; i < buildings.size(); i++) {
bfs(buildings[i], grid, visitedCount);
}
int result = INT_MAX;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] > 0 && visitedCount[i][j] == buildings.size()) {
result = min(grid[i][j], result);
}
}
}
return result == INT_MAX ? -1 : result;
}

void bfs(pair<int, int> b, vector<vector<int>>& grid, vector<vector<int>>& visitedCount) {
vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size(), -1));
queue<pair<int, int>> que;
que.push(b);
dis[b.first][b.second] = 0;
visitedCount[b.first][b.second]++;
while(!que.empty()) {
pair<int, int> s = que.front();
que.pop();
for(int i = 0; i < 4; i++) {
int x = s.first + dir[i].first;
int y = s.second + dir[i].second;
if(x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size()) {
if(grid[x][y] >= 0 && dis[x][y] < 0) {
dis[x][y] = dis[s.first][s.second] + 1;
visitedCount[x][y]++;
grid[x][y] += dis[x][y];
que.push(make_pair(x, y));
}
}
}
}
}
};
``````

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