一、题目
中等题。
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
二、思路
（1）其实和上一题（【LeetCode286】墙与门（BFS））非常相似，这题的0就相当于286题的门，但是本题是可能存在多个门“堆”在一起（多个0）的情况，首先将0加入队列，从每个0开始一圈圈向1用BFS扩散，可以设置二维数组dis记录距离，和用vis二维数组表示是否遍历过的flag。
（2）加入队列的条件是：新节点木有越界，并且还未遍历过该新节点。
ps：一开始发现只对了几个测试用例，找了好久发现是把dis[newx][newy] = dis[x][y] + 1;写成dis[newy][newy] = dis[x][y] + 1;了，，这种bug应该是要很快定位的，观察错误的样例结果分析（有几个应该是0的格子竟然有大于0的数字）。
三、代码
class Solution { private: vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int row = matrix.size(); int col = matrix[0].size(); vector<vector<int>>vis(row, vector<int>(col)); vector<vector<int>>dis(row, vector<int>(col)); queue<pair<int, int>>q; //先将所有0的坐标入队列 for(int i = 0; i < row; ++i){ for(int j = 0; j < col; ++j){ if(matrix[i][j] == 0){ q.push(make_pair(i, j)); vis[i][j] = 1; } } } 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(matrix, newx, newy) && !vis[newx][newy]){ dis[newx][newy] = dis[x][y] + 1; q.push(make_pair(newx, newy)); vis[newx][newy] = 1; } } } return dis; } bool isarea(vector<vector<int>>& mat, int x, int y){ return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size()); } };
