当前位置: 首页 > 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> <…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...