Walls and Gates

https://www.lintcode.com/problem/walls-and-gates/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 2^31 - 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, that room should remain filled with INF

Example

Example1

Input:
[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output:
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Explanation:
the 2D grid is:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF
the answer is:
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Example2

Input:
[[0,-1],[2147483647,2147483647]]
Output:
[[0,-1],[1,2]]

Thoughts

由0，-1，INF组成的二维矩阵，-1代表不能通过，每个INF更新成离它最近0的距离。最短距离而且又是『显式』图，用BFS。问『0->1』最短，要从『1->0』做BFS，有两个原因: 1. 一般1的数目要<<0，所需处理的结点更少；2. 如果是只找一个最近的1，从所有的1开始一起遍历，每次遇到的没被标记过的0一定是被最近的1（之一）访问着，这个0就可以被标记以后无需再访问。因此这道题把所有标为0的作为BFS初始点，做BFS。

Code

class Solution {
public:
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    void wallsAndGates(vector<vector<int>> &rooms) {
        const int M = rooms.size(), N = M == 0 ? 0 : rooms[0].size();
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<vector<int>> q;
        vector<vector<bool>> visited(M, vector<bool>(N, false)); 
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (rooms[i][j] != 0) continue;
                q.push({i, j});
            }
        }

        int step = 0;
        while (!q.empty()) {
            ++step;
            for (int i = q.size() - 1; i >= 0; --i) {
                const auto &t = q.front();
                for (const auto &dir : dirs) {
                    const auto x = t[0] + dir[0], y = t[1] + dir[1];
                    if (x >= 0 && x < M && y >= 0 && y < N && rooms[x][y] == INT_MAX) {
                        q.push({x, y});
                        rooms[x][y] = step;
                    }
               }
               q.pop();
           }
        }
    }
};

Analysis

做题耗时15min 时间复杂度O(MN).