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 value231 - 1 = 2147483647to representINFas 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 INFINF INF INF -1INF -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. shares a very clear solution in Python, which is rewritten in C++ as follows.
1 class Solution { 2 public: 3 void wallsAndGates(vector >& 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 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 , which is rewritten below using private functions.
1 class Solution { 2 public: 3 void wallsAndGates(vector >& rooms) { 4 int m = rooms.size(), n = m ? rooms[0].size() : 0; 5 queue > 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 >& rooms, queue >& 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 }; has suggested the following solution, which I find more concise :-)
1 class Solution { 2 public: 3 void wallsAndGates(vector >& rooms) { 4 if (rooms.empty()) return; 5 int m = rooms.size(), n = rooms[0].size(); 6 queue > q; 7 vector > 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 };