[LeetCode] Walls and Gates

Problem Description:

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

An application of BFS. The key is to apply appropriate pruning. This post shares a very clear solution in Python, which is rewritten in C++ as follows.

 1 class Solution {
 2 public:
 3     void wallsAndGates(vector<vector<int>>& rooms) {
 4         if (rooms.empty()) return;
 5         int m = rooms.size(), n = rooms[0].size();
 6         for (int i = 0; i < m; i++) {
 7             for (int j = 0; j < n; j++) {
 8                 if (!rooms[i][j]) {
 9                     queue<Grid> grids;
10                     grids.push(Grid(i + 1, j, 1));
11                     grids.push(Grid(i - 1, j, 1));
12                     grids.push(Grid(i, j + 1, 1));
13                     grids.push(Grid(i, j - 1, 1));
14                     while (!grids.empty()) {
15                         Grid grid = grids.front();
16                         grids.pop();
17                         int r = grid.r, c = grid.c, d = grid.d;
18                         if (r < 0 || r >= m || c < 0 || c >= n || rooms[r][c] < d)
19                             continue;
20                         rooms[r][c] = d;
21                         grids.push(Grid(r + 1, c, d + 1));
22                         grids.push(Grid(r - 1, c, d + 1));
23                         grids.push(Grid(r, c + 1, d + 1));
24                         grids.push(Grid(r, c - 1, d + 1));
25                     }
26                 }
27             }
28         }
29     }
30 private:
31     struct Grid {
32         int r, c, d;
33         Grid(int _r, int _c, int _d) : r(_r), c(_c), d(_d) {}
34     };
35 };

Stefan posts a nice C++ solution using #define helper functions here, which is rewritten below using private functions.

 1 class Solution {
 2 public:
 3     void wallsAndGates(vector<vector<int>>& rooms) {
 4         int m = rooms.size(), n = m ? rooms[0].size() : 0;
 5         queue<pair<int, int>> q;
 6         for (int i = 0; i < m; i++)
 7             for (int j = 0; j < n; j++)
 8                 if (!rooms[i][j]) q.push({i, j});
 9         for (int d = 1; !q.empty(); d++) {
10             for (int k = q.size(); k; k--) {
11                 int i = q.front().first, j = q.front().second;
12                 q.pop();
13                 add(rooms, q, i - 1, j, m, n, d);
14                 add(rooms, q, i + 1, j, m, n, d);
15                 add(rooms, q, i, j - 1, m, n, d);
16                 add(rooms, q, i, j + 1, m, n, d); 
17             }
18         }
19     }
20 private:
21     void add(vector<vector<int>>& rooms, queue<pair<int, int>>& q, int i, int j, int m, int n, int d) {
22         if (i >= 0 && i < m && j >= 0 && j < n && rooms[i][j] > d) {
23             q.push({i, j});
24             rooms[i][j] = d;
25         }
26     }
27 };

RileCurry_adorable has suggested the following solution, which I find more concise :-)

 1 class Solution {
 2 public:
 3     void wallsAndGates(vector<vector<int>>& rooms) {
 4         if (rooms.empty()) return;
 5         int m = rooms.size(), n = rooms[0].size();
 6         queue<pair<int, int>> q;
 7         vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 8         for (int i = 0; i < m; i++)
 9             for (int j = 0; j < n; j++)
10                 if (!rooms[i][j])
11                     q.push(make_pair(i, j));
12         while (!q.empty()) {
13             int r = q.front().first, c = q.front().second;
14             q.pop();
15             for (auto dir : dirs) {
16                 int x = r + dir.first, y = c + dir.second;
17                 if (x < 0 || y < 0 || x >= m || y >= n || rooms[x][y] <= rooms[r][c] + 1)
18                     continue;
19                 rooms[x][y] = rooms[r][c] + 1;
20                 q.push(make_pair(x, y));
21             }
22         }
23     }
24 };