当前位置: 首页 > news >正文

LeetCode 0542. 01 矩阵

【LetMeFly】542.01 矩阵

力扣题目链接:https://leetcode.cn/problems/01-matrix/

给定一个由 01 组成的矩阵 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,将其位置入队。

接着在队列不为空时,不断出队一个位置,并判断这个位置的上下左右是否被遍历过。

如果还没有被遍历过,那么就将新的位置入队。并将地图中新的位置的值修改为“出队位置的值 + 1”

原理:

所有的原始的0最终结果都是0。广度优先搜索就是在所有的“0”的位置中,走一步。这一步所到的位置就是“1”步能到达的位置。同理,“1”经过一步到达的位置就是“2”。最先到达的就是步数最少的。

  • 时间复杂度 O ( n m ) O(nm) O(nm)
  • 空间复杂度 O ( n m ) O(nm) O(nm)

AC代码

C++

typedef pair<int, int> pii;
const int direcitons[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pii> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!mat[i][j]) {
                    visited[i][j] = true;
                    q.push({i, j});
                }
            }
        }
        while (q.size()) {
            pii thisNode = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = thisNode.first + direcitons[d][0];
                int ty = thisNode.second + direcitons[d][1];
                if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                    if (!visited[tx][ty]) {
                        visited[tx][ty] = true;
                        mat[tx][ty] = mat[thisNode.first][thisNode.second] + 1;
                        q.push({tx, ty});
                    }
                }
            }
        }
        return mat;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/128175163

相关文章:

  • Spire.PDF for .NET【文档操作】演示:如何在 C# 中切换 PDF 层的可见性
  • 探寻大模型回答9.9和9.11犯错的根本原因
  • MySQL 进阶(三)【SQL 优化】
  • 宝塔安装RabbitMq教程
  • 最大文件句柄数
  • Java中使用代理IP的詳細教程
  • Angular 中的响应式表单:监听变化
  • SpringCloud-Docker原理解析
  • 【VSCode】SSH Remote 通过跳板机连开发机提示“bash行1 powershell未找到命令”
  • 从Unity到Three.js(outline 模型描边功能)
  • NetBIOS解密:从历史到现代网络中的角色与挑战
  • Android 剪切板相关
  • 【C++智能指针】智能指针的发展和循环引用的原理和解决
  • 央企招聘:正式编制!八险三金!各项福利!中国邮政招人啦!
  • 欧拉公式 Euler‘s Formula
  • 0.安装和配置
  • redis我记不住的那些命令(六)
  • Spring - @PostConstruct 源码解析
  • JS 正则表达式常用方法
  • 2-分类问题 SVM 核函数
  • [附源码]计算机毕业设计校园订餐管理系统Springboot程序
  • GitLab CI/CD系列教程(一)
  • html当当书网站 html网上在线书城 html在线小说书籍网页 当当书城网页设计
  • [附源码]JAVA毕业设计课程网站设计(系统+LW)
  • Spring Boot TestEntityManager
  • 【@property的参数copy Objective-C语言】
  • 八股文之设计原则
  • C++图书管理系统(管理员-读者)
  • 高可用方案组件,Keepalived详解
  • MOSFET 和 IGBT 栅极驱动器电路的基本原理学习笔记(一)MOSFET技术
  • Ansible
  • 年产2万吨山楂酒工厂的设计-陈酿工段及车间的设计(lunwen+任务书+cad图纸)