0-1矩阵


题目描述

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例1

输入:

0 0 0
0 1 0
0 0 0

输出:

0 0 0
0 1 0
0 0 0

示例2

输入:

0 0 0
0 1 0
1 1 1

输出:

0 0 0
0 1 0
1 2 1

注意事项

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

分析

  1. 这道题所有为0的点都是起点。

  2. 然后开始BFS遍历,从queue中取出一个数字,遍历其周围四个点,如果越界或者周围点的值小于等于当前值加1,则直接跳过。

  3. 因为周围点的距离更小的话,就没有更新的必要,否则将周围点的值更新为当前值加1,然后把周围点的坐标加入queue

    参考代码

    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
            queue<pair<int, int>> q;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0) q.push({i, j});
                    else matrix[i][j] = INT_MAX;
                }
            }
            while (!q.empty()) {
                auto t = q.front(); q.pop();
                for (auto dir : dirs) {
                    int x = t.first + dir[0], y = t.second + dir[1];
                    if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[t.first][t.second] + 1) continue;
                    matrix[x][y] = matrix[t.first][t.second] + 1;
                    q.push({x, y});
                }
            }
            return matrix;
        }
    };

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
 上一篇
岛屿数量 岛屿数量
题目描述给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
下一篇 
完全平方数 完全平方数
题目描述给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
  目录