leetcode-542:01 矩阵

简介: leetcode-542: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]]

解题

方法一:BFS

参考链接

首先要确定是BFS还是DFS,由于是遇到最近的path,因此,一旦遇到一个近的0,就可以得出path,那么要选用BFS。

将mat中每个0都加入queue中,每个层的遍历,都使得path++,mat中非0的值,首次访问就被修改p,因为要求最近的,也就是使用BFS的关键所在。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<int>> res(m,vector<int>(n,0));
        vector<vector<int>> dirs={{1,0},{-1,0},{0,1},{0,-1}};
        queue<pair<int,int>> q;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0) q.push({i,j});
                else res[i][j]=-1;
            }
        }
        int path=1;
        while(!q.empty()){
            int l=q.size();
            for(int i=0;i<l;i++){
                auto [x,y]=q.front();
                q.pop();
                for(vector<int>& dir:dirs){
                    int nx=x+dir[0];
                    int ny=y+dir[1];
                    if(nx<0||nx>=m||ny<0||ny>=n) continue;
                    if(res[nx][ny]==-1){
                        res[nx][ny]=path;
                        q.push({nx,ny});
                    }
                }
            }
            path++;
        }
        return res; 
    }
};

方法二:动态规划

参考链接

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0) dp[i][j]=0;
                else dp[i][j]=1e5;
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i-1>=0){
                    dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
                }
                if(j-1>=0){
                    dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
                }
            }
        }
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(i+1<m){
                    dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
                }
                if(j+1<n){
                    dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
                }
            }
        }
        return dp;
    }
};


相关文章
|
6月前
|
算法
力扣240 搜索二维矩阵II
力扣240 搜索二维矩阵II
|
6月前
|
算法 测试技术 C#
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
|
6月前
leetcode-329:矩阵中的最长递增路径
leetcode-329:矩阵中的最长递增路径
50 0
|
3月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
1月前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
15 0
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
51 6
|
3月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
41 4
|
3月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
32 0
【Leetcode刷题Python】73. 矩阵置零
|
5月前
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
33 2
|
5月前
|
存储 数据采集 算法
LeetCode题目73:矩阵置零
LeetCode题目73:矩阵置零