今日份题目:
给定一个由 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
题目思路
找到距离当前位置最近的0,有两种思路,要么从0开始找1,要么从1开始找0。这道题,我们用从0开始找1的方法,这样距离就直接每次加一就可以了。为了简化思路和运算,我们仿照之前那道两岛间的最短距离的题目,将一片0看作一个岛,然后按层外扩,每层的距离就是上一层的距离加一。看作岛就是需要先标记为到达过并将位置放入队列。两道题目的不同之处在于,两岛间距离的题目只需找出最小距离,而这道题需要找到每个点到最近的0的最小距离,所以需要额外的数组实时记录。
bfs应用在按层外扩上,每次从队列中取出符合条件的格子,然后将四周符合条件的格子放入队列。所谓的条件就是:当前位置确实在矩阵中,并且当前位置没有到达过。
代码
class Solution
{
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix)
{
int n=matrix.size();
int m=matrix[0].size();
//上下左右四个方向
int dirc[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
vector<vector<int>> dist(n,vector<int>(m)); //记录距离
vector<vector<int>> visited(n,vector<int>(m)); //标记到达过
queue<pair<int,int> > p;
//将矩阵中所有的0添加进初始队列中
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(matrix[i][j]==0)
{
p.push({i,j});
visited[i][j]=1; //标记为到达过
dist[i][j]=0;
}
}
}
//bfs
while(!p.empty())
{
auto [x,y]=p.front();
p.pop();
for(int i=0;i<4;i++) //遍历周围四个方向的格子
{
//获取新位置
int nx=x+dirc[i][0];
int ny=y+dirc[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&visited[nx][ny]==0)
{
dist[nx][ny]=dist[x][y]+1;
p.push({nx,ny});
visited[nx][ny]=1; //标记为到达过
}
}
}
return dist;
}
};
提交结果
欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!
更新不易,宝子们点个赞支持下,谢谢!
每天一道leetcode,大家一起在评论区打卡呀!