一、题目
给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：
-1 表示墙或是障碍物
0 表示一扇门
INF 无限表示一个空的房间。然后，我们用 2 31 2^{31}2
31
- 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
你要给每个空房间位上填上该房间到 最近门的距离，如果无法到达门，则填 INF 即可。
样例1：
输入： [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] 输出： [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]] 解释： 2D网络为： INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF 答案为： 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
二、思路
（1）先将所有门入队，从所有门开始BFS，入队的是点坐标，可以用pair结构。
（2）入队时更新距离，而不是出队时，防止重复入队。
（3）更新的条件是rooms[newx][newy] > rooms[x][y] + 1，这里的rooms[x][y] + 1在本轮次（从该当前门开始BFS）遍历中本该属于该节点的树高度，如果这个高度（路径）更小自然就要更新了。
三、代码
class Solution { private: vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public: void wallsAndGates(vector<vector<int>>& rooms) { if(rooms.empty()){ return; } int row = rooms.size(); int col = rooms[0].size(); queue<pair<int, int>> q; //先将所有门入队 for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(rooms[i][j] == 0){ q.push(make_pair(i, j)); } } } while(!q.empty()){ pair<int, int>a = q.front(); int x = a.first, y = a.second; q.pop(); for(auto dir: directions){ int newx = x + dir.first, newy = y + dir.second; if(isarea(rooms, newx, newy) && rooms[newx][newy] > rooms[x][y] + 1){ q.push(make_pair(newx, newy)); rooms[newx][newy] = rooms[x][y] + 1; } } } } bool isarea(vector<vector<int>>&rooms, int x, int y){ return (x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size()); } };
