C++ LeetCode542矩阵示例详解
短信预约 -IT技能 免费直播动态提醒
LeetCode 542.01 矩阵
力扣题目链接：leetcode.cn/problems/01…
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.mat中至少有一个0
方法一：广度优先搜索
首先遍历原始矩阵，找到所有的0，将其位置入队。
接着在队列不为空时，不断出队一个位置，并判断这个位置的上下左右是否被遍历过。
如果还没有被遍历过，那么就将新的位置入队。并将地图中新的位置的值修改为“出队位置的值 + 1”
原理：
所有的原始的0最终结果都是0。广度优先搜索就是在所有的“0”的位置中，走一步。这一步所到的位置就是“1”步能到达的位置。同理，“1”经过一步到达的位置就是“2”。最先到达的就是步数最少的。
- 时间复杂度O(nm)
- 空间复杂度O(nm)
AC代码
C++
typedef pair<int, int> pii;
const int direcitons[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
queue<pii> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!mat[i][j]) {
visited[i][j] = true;
q.push({i, j});
}
}
}
while (q.size()) {
pii thisNode = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int tx = thisNode.first + direcitons[d][0];
int ty = thisNode.second + direcitons[d][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
if (!visited[tx][ty]) {
visited[tx][ty] = true;
mat[tx][ty] = mat[thisNode.first][thisNode.second] + 1;
q.push({tx, ty});
}
}
}
}
return mat;
}
};以上就是C++ LeetCode542矩阵示例详解的详细内容，更多关于C++ LeetCode542矩阵的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
