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 };
原文：http://www.cnblogs.com/jcliBlogger/p/4836567.html