2023-5-26 LeetCode每日一题(二进制矩阵中的最短路径)

这篇具有很好参考价值的文章主要介绍了2023-5-26 LeetCode每日一题(二进制矩阵中的最短路径)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2023-05-29每日一题

一、题目编号

1091. 二进制矩阵中的最短路径

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求:

  • 路径途经的所有单元格都的值都是 0 。
  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。

畅通路径的长度 是该路径途经的单元格总数。

四、解题代码

class Solution {
    int dir[8][2] = {
        {-1, 0},
        {1, 0},
        {0, 1},
        {0, -1},
        {1, -1},
        {1, 1},
        {-1, -1},
        {-1, 1},
    };

public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue<int> q;
        if(grid[0][0] == 1){
            return -1;
        }
        q.push(0 * 110 + 0);
        int m = grid.size();
        int n = grid[0].size();
        if(m == 1 && n == 1){
            if(grid[0][0] == 0){
                return 1;
            }
        }
        int hash[12000];
        memset(hash, 0, sizeof(hash));
        int cnt = 0;
        while(!q.empty()){
            ++cnt;
            int len = q.size();
            for(int i = 0; i < len; ++i){
                int node = q.front();
                q.pop();
                int x = node / 110;
                int y = node % 110;
                for(int j = 0; j < 8; ++j){
                    int next_x = x + dir[j][0];
                    int next_y = y + dir[j][1];
                    if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n || hash[next_x * 110 + next_y]){
                        continue;
                    }
                    if(grid[next_x][next_y] == 1){
                        if(next_x == m-1 && next_y == n-1){
                            return -1;
                        }
                        continue;
                    }
                    if(next_x == m-1 && next_y == n-1){
                        return cnt + 1;
                    }
                    hash[next_x * 110 + next_y] = 1;
                    q.push(next_x * 110 + next_y);
                }
            }
        }
    return -1;
    }
};

五、解题思路

(1) 该问题有8个方向,那么这到题目就要利用到平面的8方向遍历,这用一维数组控制也可以,但是习惯上用二维数组来控制。

(2) 使用广度优先搜索来进行遍历,从(0,0)点开始遍历。利用队列+哈希的形式来进行广搜。首先得判断,(0,0)点是否为0和是否只有(0,0)点并且为0。

(3) 广搜在平面的压入队列条件为不越界,哈希未标记,并且为0,并且可以通过提前判断是否到(m-1, n-1)来结束广度优先搜索。文章来源地址https://www.toymoban.com/news/detail-461053.html

到了这里,关于2023-5-26 LeetCode每日一题(二进制矩阵中的最短路径)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ( 位运算 ) 190. 颠倒二进制位 ——【Leetcode每日一题】

    难度:简单 颠倒给定的 32 位无符号整数的二进制位。 提示: 请注意,在某些语言(如 Java )中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是

    2024年02月03日
    浏览(49)
  • (位运算) 1356. 根据数字二进制下 1 的数目排序 ——【Leetcode每日一题】

    难度:简单 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。 请你返回排序后的数组。 示例 1: 输入 :arr = [0,1,2,3,4,5,6,7,8] 输出 :[0,1,2,4,8,3,5,6,7] 解释

    2024年02月12日
    浏览(53)
  • 【每日一题Day218】LC1091 二进制矩阵中的最短路径 | BFS

    你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ,你想要从 1 开到 n ,通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向。 乘客信息用一个下标从 0 开始的二维数组 rides 表示,其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客

    2024年02月08日
    浏览(52)
  • C语言每日一题之整数求二进制1的个数

    今天分享一道题目,用三种方法来求解 二进制1的个数 方法1 我们的十进制除10和取余数就可以得到我们每一位的数字,那我们的二进制也可 以 这是一种方法,另外一种就是我们可以用移位操作符来算 这个方法是不是也是特别妙呢,当然还有更妙的方法,请看!!! 相信看

    2024年02月15日
    浏览(62)
  • C语言每日一题(5):求两个数二进制中不同位的个数

    文章主题:求两个数二进制中不同位的个数🔥 所属专栏: C语言每日一题 📗 作者简介:每天不定时更新C语言的小白一枚,记录分享自己每天的所思所想😄🎶 个人主页: [₽]的个人主页 🏄🌊 最近刚学位操作符以及二进制码的相关知识,于是想出了求两个数二进制中不同

    2024年02月07日
    浏览(152)
  • LeetCode 1253. 重构 2 行二进制矩阵

    力扣题目链接:https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/ 给你一个  2  行 n 列的二进制数组: 矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是  0  就是  1 。 第 0 行的元素之和为  upper 。 第 1 行的元素之和为 lower 。 第 i 列(从 0 开始编号)的元素之和为

    2024年02月11日
    浏览(41)
  • ​LeetCode解法汇总253. 重构 2 行二进制矩阵

    https://github.com/September26/java-algorithms 给你一个  2  行  n  列的二进制数组: 矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是  0  就是  1 。 第  0  行的元素之和为  upper 。 第  1  行的元素之和为  lower 。 第  i  列(从  0  开始编号)的元素之和为  colsum[i] ,

    2024年02月11日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和

    2024年04月26日
    浏览(52)
  • 二进制安装1.26版本k8s(docker)

    v1.24.0 - v1.26.0 之前支持docker,但是需要额外安装cri-docker来充当垫片 由于工作原因作者会同时使用Ubuntu和CentOS,因此本次将两个系统的K8S安装一起记录一下(与CentOS7.9、Ubuntu2004验证) 证书采用cfssl工具制作 使用二进制方式部署3主1从高可用集群 etcd采用二进制部署,复用3个管理

    2024年02月10日
    浏览(60)
  • openEuler 22.09环境二进制安装Kubernetes(k8s) v1.26

    本文档描述了如何在openEuler 22.09上以二进制模式部署高可用Kubernetes集群(适用k8s v1.26版本)。 注意:本文档中的所有操作均使用root权限执行。 1、主机清单 本文档采用5台华为ECS进行部署,基本情况如下表所示。 主机名称 IP地址 说明 软件 k8s-master01 192.168.218.100 master节点 k

    2024年02月07日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包