If you think it is not easy to understand why the distance needs not be updated, consider the following code, where I use level to represent the distance. Suppose we have two gates a and b can connect to the same i,j. When the a and b connect to (i, j) at the same level, then level will be the final result. But when a connect to (i, j) in a level larger than b connect to (i, j), then b's level is not the result, this means that you don't need to consider these grid (i, j) once you find the result.

class Solution { public: void wallsAndGates(vector<vector<int>>& rooms) { // solution 1, BFS, O(mn) time if(rooms.empty()) return; int m = rooms.size(), n = rooms[0].size(); queue<pair<int, int>> q; // index of 0, or connected to 0 for(int i=0; i<rooms.size(); ++i){ for(int j=0; j<rooms[i].size(); ++j){ if(rooms[i][j]==0) q.push({i, j}); } } int level = 0; while(!q.empty()){ int q_size = q.size(); ++level; for(int k=0; k<q_size; ++k){ int i = q.front().first; int j = q.front().second; q.pop(); if(i+1<m && rooms[i+1][j]==INT_MAX){ rooms[i+1][j] = level; q.push({i+1, j}); } if(i-1>=0 && rooms[i-1][j]==INT_MAX){ rooms[i-1][j] = level; q.push({i-1, j}); } if(j+1<n && rooms[i][j+1]==INT_MAX){ rooms[i][j+1] = level; q.push({i, j+1}); } if(j-1>=0 && rooms[i][j-1]==INT_MAX){ rooms[i][j-1] = level; q.push({i, j-1}); } } } /* // solution 2, DFS, DFS is not as efficient as BFS if(rooms.empty()) return; int m = rooms.size(), n = rooms[0].size(); for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(rooms[i][j]==0) dfs(i, j, m, n, rooms, 1); } } */ } void dfs(int i, int j, int m, int n, vector<vector<int>>& rooms, int level){ if(i+1<m && rooms[i+1][j]>level){ rooms[i+1][j] = level; dfs(i+1, j, m, n, rooms, level+1); } if(i-1>=0 && rooms[i-1][j]>level){ rooms[i-1][j] = level; dfs(i-1, j, m, n, rooms, level+1); } if(j+1<n && rooms[i][j+1]>level){ rooms[i][j+1] = level; dfs(i, j+1, m, n, rooms, level+1); } if(j-1>=0 && rooms[i][j-1]>level){ rooms[i][j-1] = level; dfs(i, j-1, m, n, rooms, level+1); } } };Walls and Gates