蓝桥杯算法题:卡片换位

问题描述
你玩过华容道的游戏吗?这是个类似的,但更简单的游戏。

看下面 2 x 3 的格子

+---+---+---+
| A | * | * |
+---+---+---+
| B |   | * |
+---+---+---+
1
2
3
4
5
在其中放 5 张牌,其中 A 代表关羽,B 代表张飞,* 代表士兵,还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。

游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。

输入格式
输入两行 6 个字符表示当前的局面

输出格式
一个整数,表示最少多少步,才能把 AB 换位(其它牌位置随意)

样例输入1

* A
**B
1
2
样例输出1
17

样例输入2

A B
***
1
2
样例输出2

解题思路:我是想把二维变成一维来算的,如图中的两个字符串,我把他变成* AB**来看,通过查找空格进行左移右移,具体可以看代码。可是他有一个测试点出现运行错误,很奇怪,也不像是类型超出最大值,或者数组越界,难道是队列满了?求大佬帮忙看下

不过又去看了一下,好像是它样例的问题

#include<bits/stdc++.h>
using namespace std;
map<string,long long>vis;
int x,y;
long long bfs(string s){
	queue<string>q;
	q.push(s);
	vis[s]=0;
	while(!q.empty()){
		string now=q.front();
		q.pop();
		int pos=now.find(' ');
		string temp=now;
		int len=now.length();
		if(x==now.find('A')&&y==now.find('B')){
			return vis[now];
		}
		
		swap(now[pos],now[(pos+1)%len]);//格子往右移
		if(vis[now]==0){
			vis[now]=vis[temp]+1;
			q.push(now);
		}
		swap(now[pos],now[(pos+1)%len]);
		
		swap(now[pos],now[(pos+len-1)%len]);//格子往左移
		if(vis[now]==0){
			vis[now]=vis[temp]+1;
			q.push(now);
		}
		swap(now[pos],now[(pos+len-1)%len]);
		
		if(pos==1||pos==4){//在格子中间,还能往上下走 
			swap(now[pos],now[(pos+3)%len]);
			if(vis[now]==0){
				vis[now]=vis[temp]+1;
				q.push(now);
			}
			// swap(now[pos],now[(pos+3)%len]);
		}
	}
	return -1;
}
int main(){
	string s1,s2;
	getline(cin,s1);
	getline(cin,s2);
	reverse(s2.begin(),s2.end());
	s1+=s2;
	x=s1.find('B');
	y=s1.find('A');
	cout<<bfs(s1)<<endl;
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/522393.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Erlang】【RabbitMQ】Linux(CentOS7)安装Erlang和RabbitMQ

一、系统环境 查版本对应&#xff0c;CentOS-7&#xff0c;选择Erlang 23.3.4&#xff0c;RabbitMQ 3.9.16 二、操作步骤 安装 Erlang repository curl -s https://packagecloud.io/install/repositories/rabbitmq/erlang/script.rpm.sh | sudo bash安装 Erlang package s…

CMake学习笔记(三)区分macro与function

目录 共同点--形式类似 macro的形式 function的形式 不同点 1 输入参数的替换阶段不同 macro function 2 输入参数作用域不同 macro function 共同点--形式类似 macro的形式 macro(宏名 输入参数名).... endmacro() function的形式 function(函数名 输入参数名).…

如何确认ip地址?一步步教会你

在数字化和网络化的时代&#xff0c;IP地址作为设备的网络标识&#xff0c;扮演着至关重要的角色。无论是个人用户还是企业网络管理员&#xff0c;掌握如何确认IP地址的方法都显得尤为重要。虎观代理将全面介绍如何确认IP地址&#xff0c;并深入探讨其背后的原理和意义。 首先&…

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表 文章目录 RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表1. MQTT概览2. MQTT 5.0 特性1. 特性概要2. Docker中安装RabbitMQ及启用MQTT5.0协议 3. MQTT 5.0 功能列表1. 消息过期1. 描述2. 举例3. 实现 2. 订阅标识…

Linux网卡与IP地址:通往网络世界的通行证

在探索Linux网卡和IP地址的关系之前&#xff0c;我们得先理解Linux网卡是怎么工作的。想象一下&#xff0c;每台计算机都是一个世界&#x1f30e;&#xff0c;而网卡就是连接这些世界的门户&#x1f6aa;。网卡的工作就是接收和发送数据包&#xff0c;就像邮差&#x1f4ec;递送…

还在担心报表不好做?不用怕,试试这个方法(三)

系列文章&#xff1a; 《还在担心报表不好做&#xff1f;不用怕&#xff0c;试试这个方法》&#xff08;一&#xff09; 《还在担心报表不好做&#xff1f;不用怕&#xff0c;试试这个方法》&#xff08;二&#xff09; 概要 在上一篇文章《还在担心报表不好做&#xff1f;…

C++数据结构与算法——回溯算法排列问题

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月&#xff0c;主要利用代码随想录来学习&#xff0c;刷题使用力扣网站&#xff0c;不定时更…

SV学习笔记(六)

文章目录 覆盖率类型写在前面代码覆盖率断言覆盖率功能覆盖率漏洞率曲线 功能覆盖策略收集信息而非数据只测量需要的内容验证的完备性 覆盖组写在前面在类里定义covergroup 数据采样写在前面coverpoint和binbin的创建和应用命名coverpoint和bin条件覆盖率翻转覆盖率wildcard覆盖…

k8s svc流量转发

https://blog.csdn.net/qq_44930876/article/details/134813129 https://blog.csdn.net/weixin_43845924/article/details/136232099 默认使用iptables [rootlocalhost ~]# k logs kube-proxy-jcbcq I0405 10:37:28.610683 1 node.go:136] Successfully retrieved no…

NzN的数据结构--实现双向链表

上一章中&#xff0c;我们学习了链表中的单链表&#xff0c;那今天我们来学习另一种比较常见的链表--双向链表&#xff01;&#xff01; 目录 一、双向链表的结构 二、 双向链表的实现 1. 双向链表的初始化和销毁 2. 双向链表的打印 3. 双向链表的头插/尾插 4. 双向链表的…

[蓝桥杯 2019 国 C] 数正方形

[蓝桥杯 2019 国 C] 数正方形 题目描述 在一个 N N N \times N NN 的点阵上&#xff0c;取其中 4 4 4 个点恰好组成一个正方形的 4 4 4 个顶点&#xff0c;一共有多少种不同的取法&#xff1f; 由于结果可能非常大&#xff0c;你只需要输出模 1 0 9 7 10^9 7 1097 的…

八股面试速成—计算机网络部分

暑期实习面试在即&#xff0c;这几天八股和算法轮扁我>_ 八股部分打算先找学习视屏跟着画下思维导图&#xff0c;然后看详细的面试知识点&#xff0c;最后刷题 其中导图包含的是常考的题&#xff0c;按照思维导图形式整理&#xff0c;会在复盘后更新 细节研究侧重补全&a…

基于单片机钢琴电子节拍器系统设计

**单片机设计介绍&#xff0c;基于单片机钢琴电子节拍器系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机钢琴电子节拍器系统设计是一个综合性的项目&#xff0c;它结合了单片机编程、音频处理、用户界面设计等多个领域的…

SQL 中除了写 in 和 not in外,其他写法

一、WHY&#xff1f; IN 和 NOT IN 是比较常用的关键字&#xff0c;为什么要尽量避免呢&#xff1f; 1、效率低 项目中遇到这么个情况&#xff1a; t1表 和 t2表 都是150w条数据&#xff0c;600M的样子&#xff0c;都不算大。 但是这样一句查询 ↓ select * from t1 whe…

[leetcode] 25. K 个一组翻转链表

给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 k 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍&#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值…

SDKMAN多版本SDK并行管理工具

一、简介 SDKMAN是管理多个SDK并行版本的工具&#xff0c;它提供了方便的命令行界面&#xff08;CLI&#xff09;和API&#xff0c;用于列出&#xff0c;安装&#xff0c;切换和删除候选对象。此外&#xff0c;它还为我们设置了环境变量。 它还允许开发人员安装基于JVM的SDK&…

c++的学习之路:13、vector(2)

本章主要是模拟实现vector&#xff0c;文章末附上代码&#xff0c;和源码。 目录 一、STL源码 二、构造与析构 三、迭代器与【】、size、capacity、empty 四、reserve与resize 五、push_back与pop_back 六、insert与erase 七、测试 1 八、代码 九、思维导图 一、STL源…

【leetcode面试经典150题】16.接雨水(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

Web 前端性能优化之六:构建优化

5、渲染优化 如果把浏览器呈现页面的整个过程一分为二&#xff0c;前面章节所讨论的诸如图像资源优化、加载优化&#xff0c;以及构建中如何压缩资源大小等&#xff0c;都可视为浏览器为呈现页面请求所需资源的部分&#xff1b;本章将主要关注浏览器获取到资源后&#xff0c;进…

高等数学基础篇(数二)之二重积分

二重积分&#xff1a; 一、二重积分的概念及性质 1.二重积分的概念 2.二重积分的性质 二、二重积分的计算 1.利用直角坐标计算 2.利用极坐标计算 3.利用函数的奇偶性计算 4.利用变量的轮换对称性计算 目录 一、二重积分的概念及性质 1.二重积分的概念 2.二重积分的性…