LeetCode542. 01 矩阵(C++中等题)
创始人
2024-03-05 06:30:03
0

题目

给定一个由 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.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0 

思路

BFS,跟树的遍历不同,图的遍历刚开始可能有多个节点,我们首先需要将为0的节点插入到队列中,将为1的节点值设置为-1,防止重复查找,然后再遍历整个队列就行

代码

class Solution {
public:vector> updateMatrix(vector>& mat) {queue> q;int m = mat.size(), n = mat[0].size();//遍历一遍mat,队列中插入为0的点,并从这些点开始扩散for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++){if(mat[i][j] == 0) q.push({i, j});else mat[i][j] = -1;//如果是1,都赋初值为-1,代表未查找过,防止重复查找}while(q.size()){auto t = q.front();q.pop();int x = t.first, y = t.second;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};for(int i = 0; i < 4; i ++)//上下左右{int a = dx[i] + x, b = dy[i] + y;if(a >= 0 && a < m && b >=0 && b < n && mat[a][b] == -1){mat[a][b] = mat[x][y] + 1;q.push({a, b});}}}return mat;}
};

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...