图论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.获取所有钥匙的最短路径)
用二进制表示获得的钥匙,假设n钥匙个数 000000000代表没有钥匙,0000000001代表有idx为1的钥匙,0000000011代表有idx1,2的钥匙 (这方法巧妙又复杂.. 代码: class Solution {static int[][] dirs {{-1,0}…...
vue 脚手架 入门 记录
vue 脚手架 入门 记录 以管理员身份运行PowerShell执行:get-ExecutionPolicy,回复Restricted,表示状态是禁止的 3.执行:set-ExecutionPolicy RemoteSigned 4.选择Y 注意:一定要以管理员的身份运行PowerShellÿ…...
汽车租赁系统演示租车小程序H5开发
一款适合汽车租赁业务的程序系统,支持在线支付、一键续租、在线签名。 为了方便用户端方便租车和查看已租车辆的信息和费用,支持上门取车和到店取车两种模式,支持待付款、待取车、待还车、订单管理、已完成、全部订单等订单状态查看和处理功…...
【MySQL】 MySQL 更新数据机制
MySQL 更新数据机制 一、问题描述 假设我们有这样一张表,且包含一条记录: 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管理系统中有哪些应用
在制造企业中,批次管理是一项至关重要的管理方法,它贯穿于企业的整个生产过程中。特别是在流程制造行业中,如药品、食品等行业,批次管理显得尤为重要。这些行业的产品通常需要进行严格的质量控制和追踪,以便在问题发生…...
python命名规范
一、概述 以前写python代码没有个代码,写出的代码一点也不规范 二、命名规范 2.1类的命名规范 总是使用首字母大写单词串。如MyClass、ClassName。内部类可以使用额外的前导下划线。 2.2函数和方法的命名规范 小写下划线,如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个原因 第一个原因是因为安装时候,漏掉勾选 vistual stdio sdk 和 windows 通用c运行时 其中的一项目 第2个原因是没有安装 sdk...
设计模式:中介者模式(C++实现)
在中介者模式中,中介者对象负责协调多个对象之间的交互,将对象之间的耦合度降低。 #include <iostream> #include <string> #include <vector>class Colleague;// 中介者接口 class Mediator { public:virtual void sendMessage(Coll…...
Python常用函数
最近跑实验,记录一些常用的 Python 函数,便于自己复习和学习,仅用来学习。 1.Python 中的 os.path.join() 参考该文章 深度了解 在 Python 中,处理文件和目录路径是常见的任务。为了简化路径的拼接和操作,Python 提供…...
进程与线程的记忆方法
有很多人经常会分不清进程与线程的关系, 嗯。。。。。。可能只有我自己记不清吧 举个例子: 进程:登录一个qq号,就是一个进程。 线程:同时打开多个窗口聊天,就是多个线程。 每次记忆完,过了一段…...
支持私有化部署的 WorkPlus,助您构建定制化的即时通讯平台
随着信息技术的飞速发展,企业对于即时通讯平台的需求也不断提升。而在信息安全日益重要的时代背景下,随之而来的是对数据保护和隐私安全的高度关注。私有化即时通讯平台应运而生,成为企业保护数据安全的守护者。在众多品牌中,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…...
机器学习线性回归学习总结笔记
线性回归模板: 1)获取数据: 2)划分数据集: 一般使用:train_test_split() 划分数据集的包from sklearn.model_selection import train_test_split 3)标准化处理 StandardScaler…...
火狐连接错误代码SEC_ERROR_UNKNOWN_ISSUER
最近开发的实验启动功能,测试人员用火狐浏览进行测试,一直报错 错误代码SEC_ERROR_UNKNOWN_ISSUER 在网上搜索很多文章,都没有解决我的问题,最后自己花时间研究了下,灵感来源于项目中,就类似于白名单的功能…...
react 网页/app复制分享链接到剪切板,分享到国外各大社交平台,通过WhatsApp方式分享以及SMS短信方式分享链接内容
1.需求 最近在做一个国际网站app,需要把app中某个页面的图文链接分享到国外各大社交平台上(facebook,whatapp,telegram,twitter等),以及通过WhatApp聊天方式分享,和SMS短信方式分享链接内容,该怎么做呢?图示如下: 分享到国外各大社交平台&am…...
用智能文字识别技术赋能古彝文数字化之路
目录 1、前言 2、对古彝文古籍的保护迫在眉睫 3、古彝文识别的难点问题 4、古彝文文字识别的关键技术 4.1、智能高清滤镜技术 4.2、图像矫正 4.3、图像增强 4.4、版面还原 5、合合信息识别技术赋能古彝文数字化 1、前言 古彝文指的是在云南、贵州、四川等地的彝族人之…...
QT入门10个小demo——MP4视频播放器
🙌秋名山码民的主页 😂oi退役选手,Java、大数据、单片机、IoT均有所涉猎,热爱技术,技术无罪 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 获取源码,添加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) (如无)执行以下命令进行安装 ## 方法一 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> <…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
