LCR 107. 01 矩阵 - 力扣LeetCodeLCR 107. 01 矩阵 - 给定一个由 0 和 1 组成的矩阵 mat 请输出一个大小相同的矩阵其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1。 示例 1[https://pic.leetcode.cn/1626667201-NCWmuP-image.png]输入mat [[0,0,0],[0,1,0],[0,0,0]]输出[[0,0,0],[0,1,0],[0,0,0]]示例 2[https://pic.leetcode.cn/1626667205-xFxIeK-image.png]输入mat [[0,0,0],[0,1,0],[1,1,1]]输出[[0,0,0],[0,1,0],[1,2,1]] 提示 * 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 注意本题与主站 542 题相同https://leetcode.cn/problems/01-matrix/ [https://leetcode.cn/problems/01-matrix/]https://leetcode.cn/problems/2bCMpM/description/题目描述给定一个由0和1组成的矩阵mat输出大小相同的矩阵矩阵每一格的值代表原矩阵该位置元素到最近的 0 的距离。 上下左右相邻格子距离为 1。通俗理解如果本身就是 0距离就是 0如果是 1找离它最近的 0算走几步能到达。解题思路把所有的 0 全部当作初始起点一起丢进队列。类比向池塘同时扔下好多石头所有 0波纹向外扩散每个位置第一次被波纹到达就是离最近石头的距离。把所有的 0 全部当作初始起点一起丢进队列。所有0的距离天然等于 0从全部 0 的位置一层一层向外扩散BFS 层序遍历访问到1的时候这个步数就是该点到最近 0 的距离。class Solution { public: int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; vectorvectorint updateMatrix(vectorvectorint mat) { int m mat.size(), n mat[0].size(); vectorvectorint ret(m, vectorint(n, -1)); queuepairint, int q; for (int i 0; i m; i) for (int j 0; j n; j) if (mat[i][j] 0) { q.push({i, j}); ret[i][j] 0; } while (q.size()) { auto [a, b] q.front(); q.pop(); for (int i 0; i 4; i) { int x a dx[i]; int y b dy[i]; if (x 0 x m y 0 y n ret[x][y] -1) { ret[x][y] ret[a][b] 1; q.push({x, y}); } } } return ret; } };