【LeetCode542】01矩阵（BFS）

【LeetCode542】01矩阵（BFS） 一、题目

中等题。

提示：

m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[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>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    vector> updateMatrix(vector>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector>vis(row, vector(col));
        vector>dis(row, vector(col));
        queue>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()){
            paira = 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>& mat, int x, int y){
        return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size());
    }
};