​LeetCode解法汇总1091. 二进制矩阵中的最短路径

news/2024/2/28 1:54:27

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

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

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

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

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

示例 1:

输入:grid = [[0,1],[1,0]]
输出:2

示例 2:

输入:grid = [[0,0,0],[1,1,0],[1,1,0]]
输出:4

示例 3:

输入:grid = [[1,0,0],[1,1,0],[1,1,0]]
输出:-1

提示:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] 为 0 或 1

解题思路:

* 解题思路:
* 从尾节点开始,先找到所有走一步可以达到的节点,放入集合list。
* 然后在从list集合中的节点触发,找到所有可能达到的节点,这些节点就是2步可以达到的,就这样遍历下去。
* 最终遍历到头节点时,流程结束。

代码:

#include <iostream>
#include <map>
#include <list>
#include <vector>
#include <map>
#include "Solution1091.h"using namespace std;
vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};int searchGrid(vector<vector<int>> &from, vector<vector<int>> &grid, int step)
{vector<vector<int>> to;for (vector<int> node : from){int y = node[0];int x = node[1];for (vector<int> direction : directions){int newX = x + direction[1];int newY = y + direction[0];if (newX < 0 || newY < 0 || newX >= grid[0].size() || newY >= grid.size()){continue;}if (grid[newY][newX] != 0){continue;}if (newY == 0 && newX == 0){return step;}grid[newY][newX] = step;to.push_back(vector<int>{newY, newX});}}if (to.size() == 0){return 1;}return searchGrid(to, grid, step - 1);
}int Solution1091::shortestPathBinaryMatrix(vector<vector<int>> &grid)
{if (grid[0][0] == 1 || grid[grid.size() - 1][grid[0].size() - 1] == 1){return -1;}if (grid.size() == 1 && grid[0].size() == 1){return 1;}vector<vector<int>> from;int gridSizeY = grid.size() - 1;int gridSizeX = grid[0].size() - 1;from.push_back(vector<int>{gridSizeY, gridSizeX});int i = searchGrid(from, grid, -1);if (i == 1){return -1;}return i * -1 + 1;
}


http://www.ppmy.cn/news/87960.html

相关文章

【ROS2】install micro_ros

本文参考b站up&#xff1a;“照祥同学”的教程来的&#xff0c;中间一些细节的操作谨以此文作为补充&#xff0c;或者说是我在按照教程走的时候遇到的问题记录。视频链接&#xff1a;第二节&#xff1a;安装micro_ros 的 Arduino 开发环境_哔哩哔哩_bilibili 1. 安装和配置ros…

mybatis多表联查sql用法示例

用到sql变量&#xff0c;sql复用 <sql id"topSearch-common">AND ( CASE WHEN ps.online_time IS NOT NULL AND ps.offline_time IS NULLTHEN NOW() > ps.online_timeWHEN ps.online_time IS NOT NULL AND ps.offline_time IS NOT NULLTHEN NOW() > ps.o…

linux下DD 命令使用(二)—— 筑梦之路

DD命令介绍 dd命令是LINUX下的一个命令行工具&#xff0c;用于数据转换和处理。dd代表“数据复制”&#xff0c;它可以从一个设备或文件中读取数据&#xff0c;然后将数据写入到另一个设备或文件中。dd命令可以用于多种用途&#xff0c;包括以下几个方面&#xff1a; 磁盘备份…

针对UDP协议的攻击与防御

一、UDP协议概述 UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议&#xff09;是TCP/IP协议栈中的一种无连接的传输协议&#xff0c;能够提供面向事务的简单不可靠数据传输服务。 1&#xff0e;UDP的报文格式 UDP的报文格式如图1所示。 图1 UDP报文格式 …

虚拟主机部署ssl证书(https)流程

注意事项&#xff1a; 1、域名要做别名解析指向二级域名 2、证书已经申请完成&#xff0c;其他公司的证书要下载导入到西部数码。 虚拟主机部署教程如下&#xff1a; 部署证书 首先要将域名绑定到主机上&#xff0c;在主机控制面板找到【SSL部署】按钮。 在西部数码申请过证…

2019上半年上午题

2019上半年上午题 a c c c d b b 应用代理网关防火墙 c a 使用数字证书对用户的身份进行认证 d 发送方的私钥签名&#xff0c;发送方公钥确认 d b 职务作品&#xff1a;归公司所有 a b b 从抽象到具体 d 等差数列求和&#xff1a; d 构建节点之间的关系图 然后…

web端oss直传方案之vue+elementUI+OSS实践篇(附各种踩坑)

文章目录 解决思路实践工具类uploadOss.js封装上传组件NewUpload调用上传组件 遇到的问题从oss获取下载链接错误分片上传报错 - ETag配置取消上传STS token 常见问题有效期多个Token是否同时有效 总结 以前的项目上传及下载都是web端上传至服务端&#xff0c;服务器端再上传至O…

C++——图

图是由节点&#xff08;顶点&#xff09;和连接节点的边组成的一种非线性数据结构。它用于表示不同对象之间的关系或网络结构。图可以用于建模和解决许多现实世界中的问题&#xff0c;例如社交网络分析、路线规划、图像处理等。 在图中&#xff0c;节点表示实体或对象&#xf…

80个Python练手小项目;AI开发者的总结与反思;B站免费Stable Diffusion视频教程;五问ChatGPT+医学影像 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f916; 『美团大模型已秘密研发数月』在仅剩一年的窗口期里努力奔跑 5月18日下午&#xff0c;美团内部召开大模型技术分享会&#xff0c;美团…

【图床】SpringBoot上传图片

知识目录 一、写在前面✨二、新建开源仓库✨2.1 新建仓库2.2 将仓库设置为开源2.3 生产私人令牌 三、代码实现&#x1f604;3.1 工具类3.2 上传图片 四、总结撒花&#x1f60a; 一、写在前面✨ 大家好&#xff01;我是初心&#xff0c;很高兴再次和大家见面。 今天跟大家分享…

C++模板初阶(函数模板、类模板)知识点+完整思维导图+实操图+深入细节通俗易懂建议收藏

绪论 思想决定行动&#xff0c;行动养成习惯&#xff0c;习惯形成品质&#xff0c;品质决定命运。——陶行知 本章讲的是c的初阶模板&#xff0c;全文不算代码字数少的可怜&#xff0c;但模板是我们c必须学的一个宝物&#xff0c;他的出现可是c的飞跃性成就&#xff01;下面将主…

无界AI绘画基础教程,和Midjourney以及Stable Diffusion哪个更好用?

本教程收集于:AIGC从入门到精通教程 无界AI绘画基础教程,和Midjourney以及Stable Diffusion哪个更好用? 目录 简单的总结 注册 简单介绍

工作模式(2)

输入捕捉 输入捕捉功能的主要特点&#xff1a; ⚫ 上升沿或下降沿捕捉 ⚫ 脉冲宽度捕捉或脉冲周期捕捉 ⚫ 带清零的捕捉或自由计数捕捉 ⚫ 单次捕捉或连续捕捉 捕捉模式只能工作在16bit级联模式下&#xff0c;从0开始计数。当选择上升沿捕捉周期模式时&#xff0c;电路在检测到…

华为OD机试之最远足迹(Java源码)

最远足迹 题目描述 某探险队负责对地下洞穴进行探险。探险队成员在进行探险任务时&#xff0c;随身携带的记录器会不定期地记录自身的坐标&#xff0c;但在记录的间隙中也会记录其他数据。探索工作结束后&#xff0c;探险队需要获取到某成员在探险过程中相对于探险队总部的最远…

linux centos 安装JDK、tomcat、nginx教程记录

一、安装jdk 1、查看linux系统的jdk位数&#xff08;64/32位&#xff09; 查看本机位数命令&#xff1a; sudo uname --m 2、进入jdk下载官网 Java Downloads | Oracle 现在默认是最新的jdk20 以为我是之前的项目&#xff0c;使用的是jdk1.8_181版本&#xff0c;所以我需要…

apache poi clonesheet方法生成的xls格式的excel打开报:“文件错误:数据可能丢失。”

问题描述 最近在用apache poi生成xls格式的excel的时候&#xff0c;其中有个环节是循环复制第二页模板&#xff0c;然后依次插入需要的数据&#xff0c;之前用3.7版本一直没问题&#xff0c;最近发现打开后&#xff0c;报如下错误 一开始我以为是数据格式问题&#xff0c;然后…

如何在华为OD机试中获得满分?Java实现【打印文件】一文详解!

✅创作者&#xff1a;陈书予 &#x1f389;个人主页&#xff1a;陈书予的个人主页 &#x1f341;陈书予的个人社区&#xff0c;欢迎你的加入: 陈书予的社区 &#x1f31f;专栏地址: Java华为OD机试真题&#xff08;2022&2023) 文章目录 1. 题目描述2. 输入描述3. 输出描述…

【day 09】vue的过渡与动画

Vue 的过渡与动画 基础的过渡 案例 <!-- 第一步 包一个transition标签 --><transition><Song id"song" v-if"bool"></Song></transition>/* 希望组件节点 离开的时候 有过渡效果离开的起点 离开的终点*/.v-leave{/* 离开…

Maven概念及搭建

1.为什么我们要学习 maven? maven 还未出世的时候&#xff0c;我们有很多痛苦的经历 。 痛点 1&#xff1a; jar 包难以寻找 痛点 2&#xff1a; jar 包依赖的问题 痛点 3&#xff1a; jar 不方便管理 痛点 4&#xff1a;项目编译 2.Maven 简介 Maven 是 Apache 软件基金…

SpringBoot统一功能处理的三个常见实例

我们的统一功能处理肯定是通过Spring拦截器处理的撒 Spring拦截器 截器的实现分为以下两个步骤&#xff1a; 1. 创建⾃定义拦截器&#xff0c;实现 HandlerInterceptor 接⼝的 preHandle&#xff08;执⾏具体⽅法之前的预处理&#xff09;⽅ 法。 2. 将⾃定义拦截器加⼊ W…
最新文章