UVa The Morning after Halloween 万圣节后的早晨 双向BFS
题目链接:The Morning after Halloween
题目描述:
给定一个二维矩阵,图中有障碍物和字母,你需要把小写字母移动到对应的大写字母位置,不同的小写字母可以同时移动(上下左右四个方向或者保持不动 ),但是移动之后两个字母不能重合,同时移动后不能是两个字母发生了位置的交换。
上图给出了一种情况即该情况下的四种合法移动。
同时题目保证任意一个2×22\times22×2的子区域中一定至少含有一个障碍物,同时边界一定是障碍物。
题解:
我们可以把每个矩阵的看成一个状态进行BFSBFSBFS但是这样状态的个数比较多。
由于题目保证了很小的区域有障碍这也就变相说明了题目可以到达的点并不会很多,所以我们可以把每个可以经过的点进行编号,然后记录字母落在点的编号的三元组(缺少的字母用000来表示,这意味着点的编号需要从111开始),然后将三元组看成是状态,而每一次移动看成是一条边,这样我们只需要进行BFSBFSBFS即可找到目标状态的最少移动次数(在移动的时候,我们需要判断是否违反规则,例如移动后两个字母在同一个位置,或者移动导致两个相邻的字母发生的交换)。由于本题的目标状态也是已知的,那么我们可以使用双向BFSBFSBFS也就是从目标状态和初始状态同时进行BFSBFSBFS当在中间的某个状态相遇的时候,就意味着找到了最少花费,在代码中我们只需要两个队列就可以实现双向BFSBFSBFS一个放入初始状态进行搜索,一个放入目标状态进行搜索。
为什么需要双向BFSBFSBFS?双向BFSBFSBFS通常情况下能够让时间复杂度下降。原理实际上是因为每一次都选择含有较少的节点进行扩展,这样能一定程度上节省时间。
双向BFSBFSBFS的代码应该是每次选择较小的队列进行扩展,而不是轮流进行扩展(如果是轮流进行扩展那么实际上和单向BFSBFSBFS没有太大的差别)。
代码:
#include <bits/stdc++.h>const int DIRECTION_NUM = 5;
const int MAXH = 16 + 1;
const int MAXW = 16 + 1;
const int MAX_NODE = MAXH * MAXW;using namespace std;int w, h, n, nodeNum;
char g[MAXH][MAXW];
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
vector<int> es[MAX_NODE];
int nodeId[MAXH][MAXW];
map<char, int> s, t;
int dis[MAX_NODE][MAX_NODE][MAX_NODE];
int inQ[MAX_NODE][MAX_NODE][MAX_NODE];struct State
{int a, b, c; //最多三个字母位置的结点编号State() {}State(int a, int b, int c) : a(a), b(b), c(c) {}State& operator=(map<char, int> &rhs){a = b = c = 0;auto iter = rhs.begin();for (size_t i = 0; i < n; i++) {if (i == 0) { a = iter->second; }else if (i == 1) { b = iter->second; }else if (i == 2) { c = iter->second; }iter++;}return *this;}
}st, ed;void buildGraph()
{nodeNum = 1;s.clear();t.clear();for (int i = 0; i < MAX_NODE; i++) { es[i].resize(0); }for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (g[i][j] == '#') { continue; }nodeId[i][j] = nodeNum++;if (islower(g[i][j])) {s[g[i][j]] = nodeId[i][j];} else if (isupper(g[i][j])) {t[g[i][j]] = nodeId[i][j];}}}st = s;ed = t;es[0].push_back(0);for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (g[i][j] == '#') { continue; }for (int k = 0; k < DIRECTION_NUM; k++) {int nx = i + dx[k];int ny = j + dy[k];if (g[nx][ny] == '#') { continue; }es[nodeId[i][j]].push_back(nodeId[nx][ny]);}}}
}bool conflict(int newA, int newB, int a, int b) { return (newA == newB && newA != 0) || (newA == b && newB == a && newA != 0 && newB != 0); }int bfs(queue<State> &q, int nowQ)
{int size = q.size();int a, b, c;while(size--) {State now = q.front();q.pop();a = now.a, b = now.b, c = now.c;for (auto newA : es[a]) {for (auto newB : es[b]) {if (conflict(newA, newB, a, b)) { continue; }for (auto newC : es[c]) {if (conflict(newA, newC, a, c) || conflict(newB, newC, b, c)) { continue; }if (inQ[newA][newB][newC] == nowQ) { continue; }if (inQ[newA][newB][newC] == 3 - nowQ) { // 在另一个队列中cout << dis[newA][newB][newC] + dis[a][b][c] + 1 << endl;return 0;}dis[newA][newB][newC] = dis[a][b][c] + 1;inQ[newA][newB][newC] = nowQ;q.push({newA, newB, newC});}}}}return -1;
}void dBfs()
{queue<State> qs;queue<State> qt;memset(inQ, 0, sizeof(inQ));qs.push(st);qt.push(ed);dis[st.a][st.b][st.c] = 0;inQ[st.a][st.b][st.c] = 1;dis[ed.a][ed.b][ed.c] = 0;inQ[ed.a][ed.b][ed.c] = 2;while (!qs.empty() && !qt.empty()) {if (qs.size() < qt.size()) { // 优先选择队列短的队列进行bfsif(bfs(qs, 1) != -1) { return; }}else {if(bfs(qt, 2) != -1) { return; };}}
}int main()
{ios::sync_with_stdio(false);while(cin >> w >> h >> n) {if (w == 0 && h == 0 && n == 0) { break; }cin.get(); //读取末尾的换行for (int i = 0; i < h; i++) { cin.getline(g[i], MAXW); } // cin.getline读取的数据末尾没有'\n', cin.getline会保证末尾有结束符0,所以最多读取MAXW-1个有效字符buildGraph();dBfs();}return 0;
}
相关文章:

UVa The Morning after Halloween 万圣节后的早晨 双向BFS
题目链接:The Morning after Halloween 题目描述: 给定一个二维矩阵,图中有障碍物和字母,你需要把小写字母移动到对应的大写字母位置,不同的小写字母可以同时移动(上下左右四个方向或者保持不动 ࿰…...
Connext DDS属性配置参考大全(3)
Transport传输dds.participant.logging.time_based_logging.process_received_messagedds.participant.logging.time_based_logging.process_received_message.timeout...

Docker-安装Jenkins-使用jenkins发版Java项目
文章目录0.前言环境背景1.操作流程1.1前期准备工作1.1.1环境变量的配置1.2使用流水线的方式进行发版1.2.1新建流水线任务1.2.2流水线操作工具tools步骤stages步骤1:拉取代码编译步骤2:发送文件并启动0.前言 学海无涯,旅“途”漫漫,“途”中小记ÿ…...
spring 中的 Bean 是否线程安全
文章目录结论1、spring中的Bean从哪里来?2、spring中什么样的Bean存在线程安全问题?3、如何处理spring Bean的线程安全问题?结论 其实,Spring 中的 Bean 是否线程安全,其实跟 Spring 容器本身无关。Spring框架中没有提…...

微电网两阶段鲁棒优化经济调度方法[3]【升级优化版本】(Matlab代码实现)
💥💥💥💞💞💞欢迎来到本博客❤️❤️❤️💥💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑…...
C++入门教程||C++ 数据类型||C++ 变量类型
C 数据类型 使用编程语言进行编程时,需要用到各种变量来存储各种信息。变量保留的是它所存储的值的内存位置。这意味着,当您创建一个变量时,就会在内存中保留一些空间。 您可能需要存储各种数据类型(比如字符型、宽字符型、整型…...

【visio使用技巧】图片导出pdf时去掉多余空白
问题 在visio导出pdf格式的图片时,往往会存在多余的白边,如下图所示: 解决方法 依次点击:菜单栏→文件→选项→自定义功能区→勾选“开发工具”→确定。 依次点击菜单栏→开发工具→显示ShapeSheet→页→Print Properties→将…...
Rust语言之Option枚举类型
概述 Option是Rust语言设计中最重要的枚举类型之一,它编码了其它语言中空值与非空值的概念,差异在于,Rust不会允许你像其它语言一样以非空值的方式来使用一个空值,这避免了很多错误。Option在标准库中的定义如下: pu…...

基于TimeQuest时序优化原理和方法
💡 回顾基于RTL逻辑时序优化的基本思路,在关键路径中插入寄存器来优化时序 分析最坏路径 通过前面对TimeQuest软件的理解,基本上可以找到关键路径,此文章主要对关键路径时序进行优化,使设计达到时序要求,以…...
LeetCode第332场周赛
2023.2.12LeetCode第332场周赛 6354. 找出数组的串联值 思路 双指针模拟,两个指针相遇的时候要特判 算法 class Solution { public:long long findTheArrayConcVal(vector<int>& nums) {long long ans 0;int i 0, j nums.size() - 1;while (i <…...

2023-2-12刷题情况
字母板上的路径 题目描述 我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]。 在本题里,字母板为board [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”],如下所示。 我们可以按下面的指令规则行动…...
拉普拉斯矩阵
拉普拉斯算子 Δff(xi1,yj)f(xi−1,yj)f(xi,yj1)f(xi,yj−1)−4f(xi,yj)∑(k,l)∈N(i,j)(f(xk,yl)−f(xi,yj))\begin{aligned} \Delta f & f\left(x_{i1}, y_j\right) f\left(x_{i-1},y_j\right) f\left(x_i,y_{j1}\right)f\left(x_i,y_{j-1}\right) - 4f\left(x_i,y_j\r…...

Top-1错误率、Top-5错误率等常见的模型算法评估指标解析
Top-1 错误率:指预测输出的概率最高的类别与人工标注的类别相符的准确率,就是你预测的label取最后概率向量里面最大的那一个作为预测结果,如过你的预测结果中概率最大的那个分类正确,则预测正确,否则预测错误。比如预测…...
Urho3D 容器类型
Urho3D实现了自己的字符串类型和模板容器,而不是使用STL。其基本原理如下: 在某些情况下提高了性能,例如使用PODVector类时。保证字符串和容器的二进制大小,以允许例如嵌入Variant对象内。减少了编译时间。直接命名和实现&#x…...
C语言学习笔记(四): 循环结构程序设计
while语句 定义 While语句是C语言中的循环语句,它按条件循环执行语句,直到条件不满足为止 语法格式如下: while(condition) {//循环体内容; }使用实例 求123…100 include <stdio.h> int main(){int i 1, sum 0;while (i<100){sum i …...

02 OpenCV图像通道处理
1 通道提取与合并 在数字图像处理中,图像通道是指一个图像中的颜色信息被分离为不同的颜色分量。常见的图像通道包括RGB通道、灰度通道、HSV通道等。 RGB通道是指将图像分离为红色、绿色和蓝色三个颜色通道,每个通道表示相应颜色的亮度。这种方式是最常…...

微信小程序图书馆座位预约管理系统
开发工具:IDEA、微信小程序服务器:Tomcat9.0, jdk1.8项目构建:maven数据库:mysql5.7前端技术:vue、uniapp服务端技术:springbootmybatis本系统分微信小程序和管理后台两部分,项目采用…...

有限元分析学习一
系列文章目录 有限元分析学习一 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录系列文章目录前言一、有限元方法的简单介绍1.1 有限元的基础概念1.2 有限元软件发展历史1.3 有限元软件二、弹性力学的简单介绍2.1.…...
android avb2.0 总结
1、android vbmeta结构深入解析 2、android libavb深入解读 看完结构与代码,进一步了解了avb 比如vbmeta的结构、5种描述符、hash公钥签名存储位置 多层vbmeta结构、无vbmeta分区的验证逻辑、hash计算对比、公钥验证、签名验签、5种描述符体的处理 但是还有一些问题没有解决 如…...
聊天机器人-意图识别类,开源库推荐
随着人工智能和自然语言处理技术的不断发展,聊天机器人在商业、教育、医疗等领域的应用越来越广泛。因此,开源聊天机器人代码库也逐渐成为了热门话题。 开源聊天机器人代码库可以帮助开发者快速构建功能强大的聊天机器人,而不必从头开始编写…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...

JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...
如何通过git命令查看项目连接的仓库地址?
要通过 Git 命令查看项目连接的仓库地址,您可以使用以下几种方法: 1. 查看所有远程仓库地址 使用 git remote -v 命令,它会显示项目中配置的所有远程仓库及其对应的 URL: git remote -v输出示例: origin https://…...

【技巧】dify前端源代码修改第一弹-增加tab页
回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码,在知识库增加一个tab页"HELLO WORLD",完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...