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

小丑的身份证和复印件 (BFS + Floyd)

本题链接:登录—专业IT笔试面试备考平台_牛客网

题目:

样例:

输入
2 10
(JOKERjoke
#####asdr)
输出
12

思路:

        根据题意,要求最短时间,实际上也可以理解为最短距离。

        所以应该联想到有关最短距离的算法,在这里给出的 n,m是100,所以我们可以暴力求最短距离即可,身份碎片虽然分大小写,但是它们都是唯一的点,所以可以通过Floyd,记录每个点之间的最短距离,随后累加即可,其次这里的最短距离可以用BFS求得最短距离。注意一个细节,初始化无穷大的时候,尽量小一些,否则多个INF累加爆 long long 就会答案错误。

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#define endl '\n'
#define int long long
#define x first
#define y second
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;// cin >> _t;while (_t--){solve();}return 0;
}
using PII = pair<int,int>;
int n,m;
PII rem[256];	// rem 记录最短路中字符的位置
char g[110][110];int dist[256][256];	// Floyd最短距离int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
// BFS 求字符a 到字符 b 之间的最短路
inline int Dist(char a,char b)
{// 标记是否走动过当前位置vector<vector<bool>>st(110,vector<bool>(110,false));// 判断是否可以走动的条件auto isRun = [&](int x,int y)->bool{return (x >= 0 and x < n and y >= 0 and y < m and !st[x][y] and g[x][y] != '#');};// BFS 求最短路int step = 0;queue<PII>q;q.emplace(rem[a]);while(q.size()){int sz = q.size();while(sz--){PII now = q.front();q.pop();if(g[now.x][now.y] == b){rem[b] = now;	// 记录当前最短路的位置return step;}st[now.x][now.y] = true;for(int i = 0;i < 4;++i){int bx = now.x + dx[i];int by = now.y + dy[i];if(isRun(bx,by)){st[bx][by] = true;q.emplace(PII(bx,by));}}}++step;}// 返回无穷大return INT_MAX;
}inline void solve()
{// 拿取碎片的方案vector<char>plan = {'J','O','K','E','R','j','o','k','e','r'};cin >> n >> m;for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){char c;cin >> c;g[i][j] = c;// 存储好起点和终点的位置if(c == '(') rem[c] = PII(i,j);if(c == ')') rem[c] = PII(i,j);}}// 存储起点到各个字符之间的最短距离for(char &p:plan) dist['('][p] = Dist('(',p);// 存储终点到各个字符之间的最短距离for(char &p:plan) dist[p][')'] = Dist(')',p);// 存储各个点之间的最短距离for(char &st:plan){for(char &ed:plan){if(st == ed) continue;dist[st][ed] = Dist(st,ed);}}sort(All(plan));// 全排列遍历所有的捡碎片方案// 获取最小的一种答案即可int ans = INT_MAX;do{int res = 0;res += dist['('][*plan.begin()]; //累加起点开始的最短距离for(int i = 1;i < 10;++i) res += dist[plan[i - 1]][plan[i]];	// 按顺序累加最短距离res += dist[plan.back()][')'];	// 累加最后到终点最短距离ans = min(ans,res);}while(next_permutation(All(plan)));if(ans >= INT_MAX) cout << "-1" << endl;else cout << ans << endl;
}

最后提交:

相关文章:

小丑的身份证和复印件 (BFS + Floyd)

本题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 2 10 (JOKERjoke #####asdr) 输出 12 思路&#xff1a; 根据题意&#xff0c;要求最短时间&#xff0c;实际上也可以理解为最短距离。 所以应该联想到有关最短距离的算法&…...

C++类与对象(上)

C类与对象 面向过程和面向对象初步认识类的引入类的定义类的两种定义方式&#xff1a; 类的访问限定符及封装访问限定符 封装类的作用域类的实例化类对象模型如何计算类对象的大小结构体内存对齐规则&#xff1a; this指针 面向过程和面向对象初步认识 C语言是面向过程的&…...

Exchanger的 常用场景及使用示例

Exchanger的 常用场景及使用示例 Exchanger是Java并发包中的一个工具类&#xff0c;它用于两个线程之间交换数据。当两个线程都到达同步点并调用exchange()方法时&#xff0c;它们会交换数据然后继续执行。Exchanger特别适用于那些需要两个线程进行协作&#xff0c;交换数据或…...

Spring AI项目Open AI对话接口开发指导

文章目录 创建Spring AI项目配置项目pom、application文件controller接口开发接口测试 创建Spring AI项目 打开IDEA创建一个新的spring boot项目&#xff0c;填写项目名称和位置&#xff0c;类型选择maven&#xff0c;组、工件、软件包名称可以自定义&#xff0c;JDK选择17即可…...

决策规划仿真平台的搭建

以下内容笔记据来自于b站up主忠厚老实的老王&#xff0c;视频&#xff1b;链接如下&#xff1a; 自动驾驶决策规划算法第二章第一节 决策规划仿真平台搭建_哔哩哔哩_bilibili 使用到的软件有matlab、prescan、carsim以及visual stadio。 我电脑上软件的版本是matlab2022a&am…...

RustGUI学习(iced/iced_aw)之扩展小部件(十八):如何使用badge部件来凸显UI元素?

前言 本专栏是学习Rust的GUI库iced的合集,将介绍iced涉及的各个小部件分别介绍,最后会汇总为一个总的程序。 iced是RustGUI中比较强大的一个,目前处于发展中(即版本可能会改变),本专栏基于版本0.12.1. 概述 这是本专栏的第十八篇,主要讲述badge标记部件的使用,会结合实…...

触摸播放视频,并用iframe实现播放外站视频

效果&#xff1a; html: <div:style"{ height: homedivh }"class"rightOne_content_div_div"mouseenter"divSeenter(i)"mouseleave"divLeave(i)"click"ItemClick(i)"><!-- isUser是否是用户上传 --><divv-if…...

接口自动化-requests库

requests库是用来发送请求的库&#xff0c;本篇用来讲解requests库的基本使用。 1.安装requests库 pip install requests 2.requests库底层方法的调用逻辑 &#xff08;1&#xff09;get / post / put / delete 四种方法底层调用 request方法 注意&#xff1a;data和json都…...

队列的实现与OJ题目解析

"不是你变优秀了, 那个人就会喜欢你." 文章索引 前言1. 什么是队列2. 队列的实现3. OJ题目解析4. 总结 前言 感情可以培养是个伪命题. 如果有足够多的时间和爱, 就可以让另一个人爱上你的话, 那谁和谁都可以相爱了. 爱情之所以会让人死去活来, 是因为, 答案都写在了…...

中北大学软件学院javaweb实验三JSP+JDBC综合实训(一)__数据库记录的增加、查询

目录 1.实验名称2.实验目的3.实验内容4.实验原理或流程图5.实验过程或源代码&#xff08;一&#xff09;编程实现用户的登录与注册功能【步骤1】建立数据库db_news2024和用户表(笔者使用的数据库软件是navicat)【步骤2】实现用户注册登录功能(与上一实验报告不同的是&#xff0…...

高通QCS6490开发(一): 广翼智联FV01 AI板卡简介

《高通QCS6490开发》是一系列AIoT应用开发文章&#xff0c;我们将会在系列文章中陆续介绍基于QCS6490平台上的AIoT应用开发&#xff0c;在文章中&#xff0c;我们选择了广翼智联&#xff08;FAIOT&#xff09;公司的FV01产品作为开发板&#xff0c;介绍如何从底层的硬件板卡接线…...

【知识拓展】大白话说清楚:IP地址、子网掩码、网关、DNS等

前言 工作中常听别人说的本地网络是什么意思&#xff1f;同一网段又是什么意思&#xff1f;它俩有关系吗&#xff1f; 在工作中内经常会遇到相关的网络问题&#xff0c;涉及网络通信中一些常见的词汇&#xff0c;如IP地址、子网掩码、网关和DNS等。具体一点&#xff1a;经常会…...

Java 高级面试问题及答案2

Java 高级面试问题及答案 问题 1: 请解释 Java 中的多线程和并发的区别&#xff0c;并举例说明如何避免常见的并发问题。 答案&#xff1a; 多线程是指程序中有多个线程同时执行&#xff0c;而并发是指程序设计中允许多个操作看起来是同时执行的&#xff0c;即使它们可能不是…...

2024年网络安全威胁

随着2024年的到来&#xff0c;数字世界的版图正在以前所未有的速度扩张&#xff0c;引领我们进入一个技术革新的新时代。然而&#xff0c;这飞速的发展同时也催生了一系列错综复杂的网络安全挑战。在这个数字平台与我们生活日益紧密交织的时代&#xff0c;深入了解这些新兴的威…...

应用层之 HTTP 协议

HTTP 协议 HTTP (全称为 "超文本传输协议") 是一种应用非常广泛的 应用层协议。所谓 "超文本" 的含义, 就是传输的内容不仅仅是文本(比如 html, css 这个就是文本), 还可以是一些 其他的资源, 比如图片, 视频, 音频等二进制的数据。浏览器获取到网页&#…...

解决Word文档中页眉有部分有,有部分没有的问题

问题描述&#xff1a;一个Word文档中&#xff0c;在页眉上添加文档名称和页码&#xff0c;但是有的有&#xff0c;有的没有&#xff0c;选择“链接到前一节”也无法解决该问题。 原因分析&#xff1a;页眉页脚中&#xff0c;勾选了“首页不同”的选项&#xff0c;如下图&#…...

Python爬虫基础知识学习(以爬取某二手房数据、某博数据与某红薯(书)评论数据为例)

一、爬虫基础流程 爬虫的过程模块化&#xff0c;基本上可以归纳为以下几个步骤&#xff1a; 1、分析网页URL&#xff1a;打开你想要爬取数据的网站&#xff0c;然后寻找真实的页面数据URL地址&#xff1b; 2、请求网页数据&#xff1a;模拟请求网页数据&#xff0c;这里我们介…...

JavaScript-输入输出语句

输出语句 document.write( 输出的内容 ) 语法&#xff1a;document.write( 输出的内容) 作用&#xff1a;内容会显示在网页上 如果输出的内容是标签&#xff0c;也会被解析为网页元素 代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head>&…...

peft+llama3训练自定义数据

要微调自己的模型训练 LLaMA 3&#xff0c;则需要准备一个 JSON 格式的数据集&#xff0c;其中每个条目包含输入文本和相应的标签&#xff08;如果有的话&#xff09;。以下是一个 JSON 数据集的示例格式&#xff1a; [{"input": "这是一个输入样本。",&q…...

vue+ts+vite+pinia+less+echarts 前端可视化 实战项目

1.初始化前端 输入 npm init vuelatest 命令 然后 选择需要的插件2.构建完成后 在终端切换到vue-project文件夹下 npm install 下载依赖 3.下载 less样式 npm install less less-loader -D 4.下载axios npm install axios 5.下载echarts npm install echarts -S 6.引入中国…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...