# 24ms C++ solution

• Here is the modified version, with dist matrix eliminated;

``````int shortestDistance(vector<vector<int>> grid) {
int m = grid.size(), n = grid[0].size();
auto total = grid;
int walk = 0, mindist = INT_MAX, delta[] = {0, 1, 0, -1, 0};
int buildings = 0;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
if (grid[i][j] == 2) {
total[i][j] = INT_MAX;
}
if (grid[i][j] == 1) {
int cur_dist = 1;
buildings++;
total[i][j] = INT_MAX;
vector<pair<int, int>> q;
q.emplace_back(i, j);
while (q.size()) {
vector<pair<int, int>> next_q;
for (auto ij: q) {
for (int d = 0; d < 4; ++d) {
int i = ij.first + delta[d];
int j = ij.second + delta[d+1];
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == walk) {
grid[i][j]--;
total[i][j] += cur_dist;
next_q.emplace_back(i, j);
}
}
}
q.swap(next_q);
cur_dist++;
}
walk--;
}
}
}
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (buildings + grid[i][j] == 0)
mindist = min(mindist, total[i][j]);
}
}
return mindist == INT_MAX ? -1 : mindist;
}``````

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