01 矩阵

题目链接

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

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

示例:

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

思路

解法一：

题目求解最近距离，求最小，最近等问题很容易想到BFS，本题是一道比较经典的使用BFS求解的题。

  1. 定义两个 vector 数组，一个用于标记是否访问过，另外一个用于存储结果；
  2. 首先标记 0 的元素，将其放到队列中，并将其标记为 1，因为他们的初始距离为 0;
  3. 从队列中依次取出元素，扩展并判断元素是否满足条件（在边界内且之前未被访问）；
  4. 若满足条件，则长度加 1, 放到队列中;
  5. 循环直至队列为空。
class Solution
{
public:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //定义上下左右四个方向
    vector<vector<int>> updateMatrix(vector<vector<int>> &mat)
    {
        int m = mat.size();
        int n = mat[0].size();

        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> visited(m, vector<int>(n));

        queue<pair<int, int>> q;

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (mat[i][j] == 0)
                {
                    q.emplace(i, j);
                    visited[i][j] = 1;
                }
            }
        }

        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d)
            {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    visited[ni][nj] = 1;
                }
            }
        }
        return dist;
    }
};