L 286. Walls and Gates --------M

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

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 

A:

                 就是基本的BFS 

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if(m==0)
            return;
        int n = rooms[0].size();
        vector<pair<int, int>> preLevel;
        for(int i =0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(rooms[i][j]==0){
                    preLevel.push_back(make_pair(i,j));
                }
            }
        }
        vector<pair<int,int>> diff{{1,0},{-1,0},{0,1},{0,-1}};
        int depth = 0;
        while(not preLevel.empty()){
            vector<pair<int, int>> curLevel;
            depth++;
            for(auto &it : preLevel){
                for(auto & d : diff){
                    int x = it.first + d.first;
                    int y = it.second + d.second;
                    if(x>=0 && x < m && y >=0 && y <n && rooms[x][y]==INT_MAX ){
                        rooms[x][y] = depth;
                        curLevel.push_back(make_pair(x,y));
                    }
                }
            }
            preLevel = curLevel;
        }
    }
};