Walls and Gates

题目：

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 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

分析：

这题目还真的是bfs优于dfs。是个比较规范的flooding的过程。

解法：

class matrixNode {
public:
    int x;
    int y;
    int val;
    matrixNode(int _x, int _y, int _val) : x(_x), y(_y), val(_val) {}
};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.size() == 0 || rooms[0].size() == 0) {
            return;
        }
        int m = rooms.size();
        int n = rooms[0].size();
        queue<matrixNode> Q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    Q.push(matrixNode(i, j, 0) );
                }
            }
        }
        while (!Q.empty() ) {
            matrixNode temp = Q.front();
            Q.pop();
            int x = temp.x;
            int y = temp.y;
            if (x + 1 < m && rooms[x + 1][y] == INT_MAX) {
                rooms[x + 1][y] = temp.val + 1;
                Q.push(matrixNode(x + 1, y, rooms[x + 1][y]) );
            }
            if (x - 1 >= 0 && rooms[x - 1][y] == INT_MAX) {
                rooms[x - 1][y] = temp.val + 1;
                Q.push(matrixNode(x - 1, y, rooms[x - 1][y]) );
            }
            if (y + 1 < n && rooms[x][y + 1] == INT_MAX) {
                rooms[x][y + 1] = temp.val + 1;
                Q.push(matrixNode(x, y + 1, rooms[x][y + 1]) );
            }
            if (y - 1 >= 0 && rooms[x][y - 1] == INT_MAX) {
                rooms[x][y - 1] = temp.val + 1;
                Q.push(matrixNode(x, y - 1, rooms[x][y - 1]) );
            }
        }
    }
};