# 16ms C++ solution with BFS

• I improve the StefanPochmann code by computing the distances using one variable instead of a copy of grid.

``` int shortestDistance(vector<vector<int>>& grid) { if (grid.empty()) return -1; int m = grid.size(), n = grid.front().size(), reached = 0, global_min = 0; auto total_dists(grid); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { if (global_min == -1)return -1; global_min = -1; queue<pair<int, int>> q; q.emplace(i, j); int dist = 1, nnsl = 1; // num-nodes-same-level const int ns = 4; const array<pair<int, int>, ns> shifts{{{-1,0}, {1, 0}, {0, -1}, {0,1}}}; while (!q.empty()) { auto cur = q.front(); q.pop(); int cx = cur.first, cy = cur.second; for (int k = 0; k < ns; ++k) { int ax = cur.first + shifts[k].first, ay = cur.second + shifts[k].second; if (ax >= 0 && ay >= 0 && ax <m && ay < n && grid[ax][ay] == reached) { total_dists[ax][ay] += dist; --grid[ax][ay]; if (total_dists[ax][ay] < global_min || global_min == -1) global_min = total_dists[ax][ay]; q.emplace(ax, ay); } } if (--nnsl == 0) { ++dist; nnsl = q.size(); } } --reached; } } } return global_min; } ```

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