题目描述

给定一个由 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;
    }
    };

谢谢访问