Problem

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

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 2<sup>31</sup> - 1 = 2147483647
   to represent INF as you may assume that the distance to a gate is less than 2147483647.

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

Solution

一次遍历数组中的每一个元素，当发现0时用bfs更新以0为起点周围的元素，如果那个元素不为0, -1, 并且它的值大于这次更新的值，则入队列。否则不入（因为如果它已经小于这次更新的值，说明有其他的0已经更新过它）。

struct qType {
    pair<int, int> node;
    int step;
};
class Solution {
public:
    void bfs(vector<vector<int>>& rooms, int x, int y) {
        int step[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        queue<qType> q;
        pair<int, int> start;
        start.first = x;
        start.second = y;
        qType qNode;
        qNode.node = start;
        qNode.step = 0;
        q.push(qNode);
        int n = rooms.size();
        int m = rooms[0].size();
        while(!q.empty()) {
            qType qNode = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                int newX = qNode.node.first + step[i][0];
                int newY = qNode.node.second + step[i][1];
                if (0 <= newX && newX < n && 0 <= newY && newY < m && 
                rooms[newX][newY] != -1 && rooms[newX][newY] != 0 && 
                rooms[newX][newY] > qNode.step + 1) {
                    rooms[newX][newY] = qNode.step + 1;
                    qType newNode;
                    newNode.node.first = newX;
                    newNode.node.second = newY;
                    newNode.step = qNode.step + 1;
                    q.push(newNode);
                }
        }
        }
    }
    void wallsAndGates(vector<vector<int>>& rooms) {
        for(int i = 0; i < rooms.size(); i++) {
            for(int j = 0; j < rooms[i].size(); j++) {
                if (rooms[i][j] == 0) {
                    bfs(rooms, i, j);
                }
            }
        }
    }
};