给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/01-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
直白想法,每个点开启bfs找到0就停止搜索,返回距离,更新矩阵,但是超时
class Solution {
int r,c;
vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
queue<pair<int,int>> q;
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int i, j, dis;
r = matrix.size(), c = matrix[0].size();
for(i = 0; i < r; ++i)
{
for(j = 0; j < c; ++j)
{
if(matrix[i][j] != 0)
{
vector<vector<bool>> visited(r,vector<bool> (c,false));
matrix[i][j] = bfs(i,j,matrix,visited);
}
}
}
return matrix;
}
int bfs(int i, int j, vector<vector<int>> &matrix, vector<vector<bool>> &visited)
{
while(!q.empty())
q.pop();
visited[i][j] = true;
q.push({i,j});
int xf,yf,x,y,n,k,distance = 0;
while(!q.empty())
{
n = q.size();
while(n--)
{
xf = q.front().first;
yf = q.front().second;
q.pop();
for(k = 0; k < 4; ++k)
{
x = xf+dir[k][0];
y = yf+dir[k][1];
if((x>=0 && x<r)&&(y>=0 && y<c) && !visited[x][y])
{
if(matrix[x][y] != 0)
{
q.push({x,y});
visited[x][y] = true;
}
else
return distance+1;
}
}
}
++distance;
}
return distance;
}
};
换个思路:
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int i, j, dis = 0, r, c, n, xf, yf, x, y, k;
r = matrix.size(), c = matrix[0].size();
vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
vector<vector<bool>> visited(r,vector<bool>(c,false));
queue<pair<int,int>> q;
for(i = 0; i < r; ++i)
{
for(j = 0; j < c; ++j)
{
if(matrix[i][j] == 0)
q.push({i, j});
}
}
while(!q.empty())
{
n = q.size();
++dis;
while(n--)
{
xf = q.front().first;
yf = q.front().second;
q.pop();
for(k = 0; k < 4; ++k)
{
x = xf+dir[k][0];
y = yf+dir[k][1];
if(x>=0 && x<r && y>=0 && y<c
&& !visited[x][y] && matrix[x][y] != 0)
{
q.push({x,y});
visited[x][y] = true;
matrix[x][y] = dis;
}
}
}
}
return matrix;
}
};
表示该位置到0的最短距离
直接置为0
遍历2次
,上面的邻居+1
,左边的邻居+1
,下面的邻居+1
,右边的邻居+1
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix)
{
int r = matrix.size(), c = matrix[0].size(), i, j;
if (r == 0)
return matrix;
vector<vector<int>> dist(r, vector<int>(c, INT_MAX-100000));//防止溢出
//边界上的1元素距离外面无穷大
//考虑左边和上边方向
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
if (matrix[i][j] == 0)
dist[i][j] = 0;
else
{
if (i > 0)
dist[i][j] = min(dist[i][j], dist[i-1][j]+1);
if (j > 0)
dist[i][j] = min(dist[i][j], dist[i][j-1]+1);
}
}
}
//考虑右边和下边方向
for (i = r-1; i >= 0; i--)
{
for (j = c-1; j >= 0; j--)
{
if (i < r-1)
dist[i][j] = min(dist[i][j], dist[i+1][j]+1);
if (j < c-1)
dist[i][j] = min(dist[i][j], dist[i][j+1]+1);
}
}
return dist;
}
};