C++ BFS 50%

• ``````class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans;
vector<pair<int,int>> direct = {{0,-1},{-1,0},{0,1},{1,0}};
vector<vector<int>> cnt(m,vector<int>(n,0));

int level = 0;

for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j]!=1) continue;
ans = INT_MAX;
vector<vector<int>> onePass(m,vector<int>(n,0));
queue<pair<int,int>> q;
q.push({i,j});
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(auto dir : direct) {
int nx = x+dir.first;
int ny = y+dir.second;
if(nx<0 || ny<0 || nx>m-1 || ny>n-1 || grid[nx][ny]!=level) continue; // only search slot that has been visited previously, otherwise ans = -inf
onePass[nx][ny] = onePass[x][y]+1;
cnt[nx][ny] += onePass[nx][ny];
ans = min(ans,cnt[nx][ny]);
grid[nx][ny]--; // flag visited slot for next round
q.push({nx,ny});
}
}
level --;
}
}

return ans==INT_MAX?-1:ans;
}
};
``````

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