# Share my CPP BFS solution~

• ``````#define MP make_pair
#define MT make_tuple
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int N = grid.size();
if (N <= 0) return 0;
int M = grid[0].size();
if (M <= 0) return 0;
int checkcnt = 0;
vector<vector<int> > dis(N, vector<int>(M, 0));
vector<vector<int> > cnt(N, vector<int>(M, 0));
int ans = INT_MAX;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
if (grid[i][j] == 1) {
checkcnt++;
queue<tuple<int, int, int> > Q;
map<pair<int, int>, bool> vis;
vis[MP(i, j)] = true;
Q.push(MT(i, j, 0));
while (!Q.empty()) {
int cx = get<0>(Q.front()), cy = get<1>(Q.front()), cs = get<2>(Q.front()); Q.pop();
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k], ny = cy + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (vis[MP(nx, ny)]) continue;
if (grid[nx][ny] != 0) continue;
vis[MP(nx, ny)] = true;
cnt[nx][ny]++;
Q.push(MT(nx, ny, cs + 1));
dis[nx][ny] += cs + 1;
}
}
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (grid[i][j] == 0 && cnt[i][j] == checkcnt) {
ans = min(ans, dis[i][j]);
}
return (ans == INT_MAX ? -1 : ans);
}
};``````

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