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

图论17(Leetcode864.获取所有钥匙的最短路径)

用二进制表示获得的钥匙,假设n=钥匙个数

000000000代表没有钥匙,0000000001代表有idx为1的钥匙,0000000011代表有idx=1,2的钥匙

(这方法巧妙又复杂..

代码:

class Solution {static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};public int shortestPathAllKeys(String[] grid) {int m = grid.length, n = grid[0].length();int startx = 0,starty = 0;Map<Character, Integer> keyToIndex = new HashMap<>();//存钥匙的字母和对应的idx序号for(int i=0;i<grid.length;i++){for(int j=0;j<grid[i].length();j++){if(grid[i].charAt(j)=='@'){startx = i;starty = j;}else if(Character.isLowerCase(grid[i].charAt(j))){if(!keyToIndex.containsKey(grid[i].charAt(j))){int idx = keyToIndex.size();keyToIndex.put(grid[i].charAt(j), idx);}                    }}}Queue<int[]> queue = new ArrayDeque<int[]>();int[][][] dist = new int[m][n][1<<keyToIndex.size()];//第三维是2的size次方 列举钥匙的所有可能for(int i=0;i<m;i++){for(int j=0;j<n;j++){Arrays.fill(dist[i][j],-1);}} queue.offer(new int[]{startx,starty,0});dist[startx][starty][0] = 0;while(!queue.isEmpty()){int[] arr = queue.poll();int x = arr[0],y = arr[1],mask = arr[2];//mask是钥匙的排列for(int i=0;i<4;i++){int nx = x + dirs[i][0];int ny = y + dirs[i][1];if(nx>=0 && nx<m && ny>=0 && ny<n &&grid[nx].charAt(ny)!='#'){if(grid[nx].charAt(ny)=='.'||grid[nx].charAt(ny)=='@'){if(dist[nx][ny][mask] == -1){dist[nx][ny][mask] = dist[x][y][mask]+1;queue.offer(new int[]{nx,ny,mask});}}else if(Character.isLowerCase(grid[nx].charAt(ny))){int idx = keyToIndex.get(grid[nx].charAt(ny));if(dist[nx][ny][mask|(1<<idx)] == -1){dist[nx][ny][mask|(1<<idx)] = dist[x][y][mask]+1;if((mask|(1<<idx))==(1<<keyToIndex.size())-1){return dist[nx][ny][mask|(1<<idx)];}queue.offer(new int[]{nx,ny,mask|(1<<idx)});}}else{int idx = keyToIndex.get(Character.toLowerCase(grid[nx].charAt(ny)));if((mask&(1<<idx))!=0&&dist[nx][ny][mask]==-1){dist[nx][ny][mask] = dist[x][y][mask]+1;queue.offer(new int[]{nx,ny,mask});}}}}}  return -1;     }
}

相关文章:

图论17(Leetcode864.获取所有钥匙的最短路径)

用二进制表示获得的钥匙&#xff0c;假设n钥匙个数 000000000代表没有钥匙&#xff0c;0000000001代表有idx为1的钥匙&#xff0c;0000000011代表有idx1&#xff0c;2的钥匙 &#xff08;这方法巧妙又复杂.. 代码&#xff1a; class Solution {static int[][] dirs {{-1,0}…...

vue 脚手架 入门 记录

vue 脚手架 入门 记录 以管理员身份运行PowerShell执行&#xff1a;get-ExecutionPolicy&#xff0c;回复Restricted&#xff0c;表示状态是禁止的 3.执行&#xff1a;set-ExecutionPolicy RemoteSigned 4.选择Y 注意&#xff1a;一定要以管理员的身份运行PowerShell&#xff…...

汽车租赁系统演示租车小程序H5开发

一款适合汽车租赁业务的程序系统&#xff0c;支持在线支付、一键续租、在线签名。 为了方便用户端方便租车和查看已租车辆的信息和费用&#xff0c;支持上门取车和到店取车两种模式&#xff0c;支持待付款、待取车、待还车、订单管理、已完成、全部订单等订单状态查看和处理功…...

【MySQL】 MySQL 更新数据机制

MySQL 更新数据机制 一、问题描述 假设我们有这样一张表&#xff0c;且包含一条记录&#xff1a; CREATE TABLE mytest ( id int(11) NOT NULL, c1 int(11) DEFAULT NULL, c2 int(11) DEFAULT NULL, c3 int(11) DEFAULT NULL, PRIMARY KEY (id), KEY c1 (c1), KEY c2 (c2) 包…...

批次管理在MES管理系统中有哪些应用

在制造企业中&#xff0c;批次管理是一项至关重要的管理方法&#xff0c;它贯穿于企业的整个生产过程中。特别是在流程制造行业中&#xff0c;如药品、食品等行业&#xff0c;批次管理显得尤为重要。这些行业的产品通常需要进行严格的质量控制和追踪&#xff0c;以便在问题发生…...

python命名规范

一、概述 以前写python代码没有个代码&#xff0c;写出的代码一点也不规范 二、命名规范 2.1类的命名规范 总是使用首字母大写单词串。如MyClass、ClassName。内部类可以使用额外的前导下划线。 2.2函数和方法的命名规范 小写下划线&#xff0c;如method_name。 2.3函数…...

Redis学习笔记--002

Redis的JAVA客户端 文章目录 Redis的JAVA客户端一、Redis的Java客户端的种类二、Jedis2.1、使用步骤2.2、Jedis连接池 三、[SpringDataRedis](https://spring.io/projects/spring-data-redis)3.1、介绍3.2、RedisTemplate3.3、SpringDataRedis使用步骤3.4、SpringDataRedis的序…...

Visual Stdio 2019 win10 64bit下 无法找到 资源编译器DLL,请确认路径是否正确,和无法下载 win10SDK_10.0

上面的2个原因 第一个原因是因为安装时候&#xff0c;漏掉勾选 vistual stdio sdk 和 windows 通用c运行时 其中的一项目 第2个原因是没有安装 sdk...

设计模式:中介者模式(C++实现)

在中介者模式中&#xff0c;中介者对象负责协调多个对象之间的交互&#xff0c;将对象之间的耦合度降低。 #include <iostream> #include <string> #include <vector>class Colleague;// 中介者接口 class Mediator { public:virtual void sendMessage(Coll…...

Python常用函数

最近跑实验&#xff0c;记录一些常用的 Python 函数&#xff0c;便于自己复习和学习&#xff0c;仅用来学习。 1.Python 中的 os.path.join() 参考该文章 深度了解 在 Python 中&#xff0c;处理文件和目录路径是常见的任务。为了简化路径的拼接和操作&#xff0c;Python 提供…...

进程与线程的记忆方法

有很多人经常会分不清进程与线程的关系&#xff0c; 嗯。。。。。。可能只有我自己记不清吧 举个例子&#xff1a; 进程&#xff1a;登录一个qq号&#xff0c;就是一个进程。 线程&#xff1a;同时打开多个窗口聊天&#xff0c;就是多个线程。 每次记忆完&#xff0c;过了一段…...

支持私有化部署的 WorkPlus,助您构建定制化的即时通讯平台

随着信息技术的飞速发展&#xff0c;企业对于即时通讯平台的需求也不断提升。而在信息安全日益重要的时代背景下&#xff0c;随之而来的是对数据保护和隐私安全的高度关注。私有化即时通讯平台应运而生&#xff0c;成为企业保护数据安全的守护者。在众多品牌中&#xff0c;Work…...

adjustText库解决深度学习、视觉模型matplotlib画散点图时由于标签非常多导致的重叠现象

pytorch框架 import matplotlib.pyplot as plt import numpy as np from adjustText import adjust_texty [30.48, 30.71, 30.52, 31.35, 31.53, 31.54, 31.82, 32.13, 32.21, 32.15, 31.92, 32.24, 32.21, 32.20, 32.35] x [0.057, 0.012, 0.025, 0.665, 1.774, 0.813, 0.55…...

机器学习线性回归学习总结笔记

线性回归模板&#xff1a; 1&#xff09;获取数据: 2&#xff09;划分数据集&#xff1a; 一般使用&#xff1a;train_test_split&#xff08;&#xff09; 划分数据集的包from sklearn.model_selection import train_test_split 3&#xff09;标准化处理 StandardScaler…...

火狐连接错误代码SEC_ERROR_UNKNOWN_ISSUER

最近开发的实验启动功能&#xff0c;测试人员用火狐浏览进行测试&#xff0c;一直报错 错误代码SEC_ERROR_UNKNOWN_ISSUER 在网上搜索很多文章&#xff0c;都没有解决我的问题&#xff0c;最后自己花时间研究了下&#xff0c;灵感来源于项目中&#xff0c;就类似于白名单的功能…...

react 网页/app复制分享链接到剪切板,分享到国外各大社交平台,通过WhatsApp方式分享以及SMS短信方式分享链接内容

1.需求 最近在做一个国际网站app,需要把app中某个页面的图文链接分享到国外各大社交平台上(facebook,whatapp,telegram,twitter等),以及通过WhatApp聊天方式分享&#xff0c;和SMS短信方式分享链接内容&#xff0c;该怎么做呢&#xff1f;图示如下: 分享到国外各大社交平台&am…...

用智能文字识别技术赋能古彝文数字化之路

目录 1、前言 2、对古彝文古籍的保护迫在眉睫 3、古彝文识别的难点问题 4、古彝文文字识别的关键技术 4.1、智能高清滤镜技术 4.2、图像矫正 4.3、图像增强 4.4、版面还原 5、合合信息识别技术赋能古彝文数字化 1、前言 古彝文指的是在云南、贵州、四川等地的彝族人之…...

QT入门10个小demo——MP4视频播放器

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 一、前…...

MySQL常用操作

目录 1. 安装MySQL/MariaDB2. 用户管理2.1 用户信息2.2 用户权限privileges 3. 增删改查3.1 增删数据库/表3.2 查询 参考 1. 安装MySQL/MariaDB # 1) 确认是否已安装mysql rpm -qa | grep mysql# 2) &#xff08;如无&#xff09;执行以下命令进行安装 ## 方法一 yum install …...

uni-app 之 Toast 消息提示

uni-app 之 Toast 消息提示 image.png <template> <view class"content"> <u-button click"showToast">Toast 消息提示 </u-button><u-toast ref"uToast"></u-toast></view></template> <…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...