286. Walls and Gates

BFS solution. We can push all the gates into a queue first, and then start from the gate in the queue to traverse across the entire map by BFS. For each position in the queue, we check its neighbors. We only want to update its neighbor when it is "nearer" to its neighbor. "Nearer" means the distance store in the neighbor is larger than rooms[i][j]+1. The challenge here is how to know a position has been visited before. Since we increase distance by 1 for neighbors, so the trick we do here to check if the distance stored in the neighbor is less than current position plus one.

1:  class Solution {  
2:  public:  
3:    void wallsAndGates(vector<vector<int>>& rooms) {  
4:      int row = rooms.size();  
5:      if (row == 0) return;  
6:      int col = rooms[0].size();  
7:      vector<pair<int, int>> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};  
8:      queue<pair<int, int>> reach;  
9:      for (int i = 0; i < row; i++) {  
10:        for (int j = 0; j < col; j++) {  
11:          if (rooms[i][j] == 0) {  
12:            reach.push(make_pair(i, j));  
13:          }  
14:        }  
15:      }  
16:      while (!reach.empty()) {  
17:        int i1 = reach.front().first;  
18:        int j1 = reach.front().second;  
19:        reach.pop();  
20:        for (int k = 0; k < dir.size(); k++) {  
21:          int i2 = i1 + dir[k].first;  
22:          int j2 = j1 + dir[k].second;  
23:          if (i2 < 0 || j2 < 0 || i2 == row || j2 == col || rooms[i2][j2] <= rooms[i1][j1]+1) continue;  
24:          rooms[i2][j2] = rooms[i1][j1] + 1;  
25:          reach.push(make_pair(i2, j2));  
26:        }  
27:      }  
28:    }  
29:  };  

When I revisited this problem, I used BFS as following but it turns out much slower than the way I did in this post. Then I rechecked the implementation and realized that the solution in this post actually performs multi-end BFS which reduced the running time to O(2n*n). The way I did runs O(k*n*n) where k is the number of gates.

1:  class Solution {  
2:  public:  
3:    void wallsAndGates(vector<vector<int>>& rooms) {  
4:      int rows = rooms.size();  
5:      if (rows == 0) return;  
6:      int cols = rooms[0].size();  
7:      queue<pair<int,int>> q;  
8:      vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};  
9:      for (int i = 0; i < rows; i++) {  
10:        for (int j = 0; j < cols; j++) {  
11:          if (rooms[i][j] == 0) {  
12:            q.push(make_pair(i, j));  
13:            while (!q.empty()) {  
14:              int n = q.size();  
15:              for (int k = 0; k < n; k++) {  
16:                int x = q.front().first;  
17:                int y = q.front().second;  
18:                q.pop();  
19:                for (int d = 0; d < dir.size(); d++) {  
20:                  int xx = x + dir[d].first;  
21:                  int yy = y + dir[d].second;  
22:                  if (xx<0 || xx==rows || yy<0 || yy==cols || rooms[xx][yy]==-1 || rooms[x][y]+1>=rooms[xx][yy]) continue;  
23:                  rooms[xx][yy] = rooms[x][y] + 1;  
24:                  q.push(make_pair(xx, yy));  
25:                }  
26:              }  
27:            }  
28:          }  
29:        }  
30:      }  
31:    }  
32:  };