lc286-Walls and Gates

發表於   |   分類於   |   0 comments   |  

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:

1
2
3
4
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:

1
2
3
4
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    int m;
    int n;
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        m = rooms.size();
        if (!m) return;
        n = rooms[0].size();
        deque<pair<int,int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!rooms[i][j]) q.push_back(make_pair(i,j));
            }
        }
        bfs(q, rooms);
    }
    void bfs(deque<pair<int,int>>& q, vector<vector<int>>& rooms) {
        while(!q.empty()) {
            pair<int,int>p = q.front();
            q.pop_front();
            int i = p.first;
            int j = p.second;
            if (i > 0 && rooms[i-1][j]>rooms[i][j]+1) {
                rooms[i-1][j]=rooms[i][j]+1;
                q.push_back(make_pair(i-1,j));
            }
            if (i < m-1 && rooms[i+1][j]>rooms[i][j]+1) {
                rooms[i+1][j]=rooms[i][j]+1;
                q.push_back(make_pair(i+1,j));
            }
            if (j > 0 && rooms[i][j-1]>rooms[i][j]+1) {
                rooms[i][j-1]=rooms[i][j]+1;
                q.push_back(make_pair(i,j-1));
            }
            if (j < n-1 && rooms[i][j+1]>rooms[i][j]+1) {
                rooms[i][j+1]=rooms[i][j]+1;
                q.push_back(make_pair(i,j+1));
            }
        }
    }
};