Leetcode 542. 01 Matrix(BFS)

最新推荐文章于 2022-03-27 23:16:51 发布

雨狮子

最新推荐文章于 2022-03-27 23:16:51 发布

阅读量467

点赞数

分类专栏： leetcode_Medium 文章标签： leetcode

本文链接：https://blog.csdn.net/CriminalCode/article/details/79060315

版权

leetcode_Medium 专栏收录该内容

17 篇文章

订阅专栏

该博客主要探讨LeetCode中的542题，即如何找到矩阵中每个单元格到最近0的距离。题目提供两个示例输入，并指出矩阵元素数量不超过10,000，且矩阵中至少有一个0。解决方案涉及向上下左右四个方向遍历相邻单元格。" 112437716,10553748,石头扫地机器人T65与T7对比解析,"['智能家居', '扫地机器人', '石头科技', '家电升级', '智能清洁']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

542. 01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

题目链接：https://leetcode.com/problems/01-matrix/description/
题目大意：给定一个只包含数字0，1的二维数组，寻找每个位置的数字与离它最近的0的距离，距离值用一个二维数组表示，0点处距离0点的最近距离为0。
解题思路：BFS查找最近距离，由于没有使用结构体 struct，而是用了C++自带的 pair 容器来纪录节点的位置（ x , y ），没法纪录步长，因此不能用 “通过非零点找0点 ” 的策略，可以反过来，通过0点找非零点，步骤为：
（1）首先把数组中的 0 点处的距离都标记为 0 ，押入队列，然后非零点处的距离都标记为 -1 ；
（2）处理队列中的节点，从 0 点出发，通过BFS搜索非零点，与 0 点相邻的所有非零点的步长都更新为1，即1已经是最短距离，不必再更新，再把距离为 1 的点加入队列，寻找距离为 2 的点，以此类推，直到处理完所有点。

代码：

class Solution {
public:
    vector<vector<int> > updateMatrix(vector<vector<int> >& matrix) {
        int n = matrix.size(); 
        int m = matrix[0].size();
        vector<vector<int> > ans;
        queue <pair<int,int> > q;
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
        ans.resize(n);

        for(int i = 0;i <n;i++){
            ans[i].resize(m);
            for(int j= 0; j< m;j ++){
                if(matrix[i][j] == 0){
                    q.push(make_pair(i,j));
                    ans[i][j] = 0;
                }
                else
                    ans[i][j] = -1;
            }
        }
        
        while(!q.empty()){
            pair<int,int> nq = q.front();
            q.pop();
            int x = nq.first;
            int y = nq.second;
            for(int k = 0; k < 4;k ++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx < 0 || nx >=n || ny < 0 || ny >=m){
                    continue;
                }
                if(ans[nx][ny] == -1){   //找到每个非零点，更新其距离
                    ans[nx][ny] = ans[x][y] + 1;
                    q.push(make_pair(nx,ny));
                }
            }    
        }
        return ans;
    }
    
};