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

【BFS最小步数】魔板题解

news 来源：原创 2025/8/29 5:38:43

魔板题解

题目传送门

一、题目描述

Rubik先生发明了魔板的二维版本，这是一个有8个格子的板子，初始状态为：

1 2 3 4
8 7 6 5

我们可以用三种操作来改变魔板状态：

A：交换上下两行
B：将最右边一列插入到最左边
C：魔板中央的4个数顺时针旋转

给定一个目标状态，要求找出从初始状态到目标状态的最短操作序列，如果有多个解，输出字典序最小的那个。

二、题目分析

这是一个典型的状态空间搜索问题，我们需要找到从初始状态到目标状态的最短路径。由于状态数量有限（8! = 40320种可能状态），可以使用广度优先搜索(BFS)来求解。

三、解题思路

使用BFS从初始状态开始搜索
对于每个状态，尝试三种操作生成新状态
记录每个状态的来源和操作，以便最后回溯路径
当找到目标状态时，根据记录的信息回溯操作序列
由于BFS按层扩展，第一个找到的解就是最短的
按照A、B、C的顺序尝试操作，保证字典序最小

四、算法讲解

广度优先搜索(BFS)

算法原理：BFS是一种图搜索算法，它从起始节点开始，逐层向外扩展，直到找到目标节点。在状态空间搜索中，每个节点代表一个状态，边代表操作。
使用场景：适用于寻找无权图中的最短路径问题，如本题中的最少操作次数。
实现步骤：
- 初始化队列，加入起始状态
- 记录每个状态的访问情况和距离
- 对于队列中的每个状态，尝试所有可能的操作
- 将未访问过的新状态加入队列
- 直到找到目标状态为止

结合例子

以样例输入2 6 8 4 5 7 3 1为例：

初始状态：1 2 3 4 5 6 7 8
通过BFS逐步扩展，最终找到目标状态
回溯操作序列得到BCABCCB

五、代码实现

#include <bits/stdc++.h>
using namespace std;
string Start, End;
char g[2][4];
unordered_map<string, pair<char, string>> pre; // 记录前驱状态和操作
unordered_map<string, int> dist; // 记录距离// 将字符串表示的状态设置到二维数组中
void setString(string t)
{for (int i = 0; i < 4; i++)g[0][i] = t[i];for (int i = 7, j = 0; j < 4; i--, j++)g[1][j] = t[i];
}// 从二维数组获取字符串表示的状态
string getString()
{string res;for (int i = 0; i < 4; i++)res += g[0][i];for (int i = 3; i >= 0; i--)res += g[1][i];return res;
}// 操作A：交换上下两行
string move0(string t)
{setString(t);for (int i = 0; i < 4; i++)swap(g[0][i], g[1][i]);return getString();
}// 操作B：将最右边的一列插入到最左边
string move1(string t)
{setString(t);char v0 = g[0][3], v1 = g[1][3];for (int i = 3; i > 0; i--)g[0][i] = g[0][i - 1], g[1][i] = g[1][i - 1];g[0][0] = v0, g[1][0] = v1;return getString();
}// 操作C：魔板中央的4个数顺时针旋转
string move2(string t)
{setString(t);char v = g[0][1];g[0][1] = g[1][1];g[1][1] = g[1][2];g[1][2] = g[0][2];g[0][2] = v;return getString();
}// BFS搜索最短路径
int bfs(string Start, string end)
{if (Start == end)return 0;queue<string> q;q.push(Start);dist[Start] = 0;while (q.size()){auto t = q.front();q.pop();string m[3];m[0] = move0(t); // 尝试操作Am[1] = move1(t); // 尝试操作Bm[2] = move2(t); // 尝试操作Cfor (int i = 0; i < 3; i++)if (!dist.count(m[i])){dist[m[i]] = dist[t] + 1;pre[m[i]] = {'A' + i, t}; // 记录前驱和操作q.push(m[i]);if (m[i] == end)return dist[m[i]];}}return -1;
}void solve()
{for (int i = 0; i < 8; i++){int x;cin >> x;End += char(x + '0');}Start = "12345678"; // 初始状态int step = bfs(Start, End);cout << step << "\n";string res;while (End != Start){res += pre[End].first; // 获取操作End = pre[End].second; // 回溯到前驱状态}reverse(res.begin(), res.end()); // 反转得到正确顺序if (step > 0)cout << res << "\n";
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

六、重点细节

状态表示：使用字符串表示魔板状态，前四个字符是第一行，后四个字符是第二行的逆序。
操作实现：三种操作通过二维数组转换实现，注意操作C的旋转方向。
字典序处理：按照A、B、C的顺序尝试操作，保证找到的第一个解就是字典序最小的。
路径记录：使用pre哈希表记录每个状态的前驱和操作，便于回溯路径。
边界处理：当初始状态就是目标状态时直接返回0。

七、复杂度分析

时间复杂度：O(8!) = O(40320)，因为最多有8!种不同的状态。
空间复杂度：O(8!)，需要存储所有可能状态的访问信息和前驱关系。

八、总结

本题通过BFS搜索状态空间，利用哈希表记录状态信息和路径，是一种典型的图搜索问题。关键在于：

合理表示状态
正确实现三种操作
高效记录和回溯路径
处理字典序要求

这种BFS方法适用于类似的"最少操作次数"问题，如八数码问题等。

【BFS最小步数】魔板题解

魔板题解题目传送门题目传送门一、题目描述 Rubik先生发明了魔板的二维版本，这是一个有8个格子的板子，初始状态为： 1 2 3 4 8 7 6 5我们可以用三种操作来改变魔板状态： A：交换上下两行B：将最右边一…...

编程日记 2025/8/29 5:38:43

简介 QHostInfo表示主机信息，即主机名称常用接口 static QHostInfo fromName(const QString &name); QString hostName() const; QList<QHostAddress> addresses() const;结构 #mermaid-svg-HTJ95sEk8JwO4uCy {font-family:"trebuchet ms",…...

编程日记 2025/8/26 8:19:35

C++11观察者模式示例

该示例代码采用C11标准，解决以下问题： 消除了类继承的强耦合方式；通知接口使用可变参数模板，支持任意参数； 示例代码 .h文件如下： #include <functional> #include <string> #include <…...

编程日记 2025/8/29 5:33:41

解释观察者模式，如何实现观察者模式？

一、模式本质观察者模式（Observer Pattern）建立对象间的一对多依赖关系，当核心对象（Subject）状态变化时，自动通知所有订阅者（Observers）。这是一种推模型的典型…...

编程日记 2025/8/28 22:09:21

机器学习算法能够自动学习并使用不同条件下的变化趋势，确保预测结果的准确性的智慧地产开源了

智慧地产视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。 AI是新形势下数…...

编程日记 2025/8/26 19:35:52

【首款ARMv9开源芯片“星睿“O6测评】在“周易”NPU上部署Yolov8l模型并实现实时目标检测

博主未授权任何人或组织机构转载博主任何原创文章，感谢各位对原创的支持！ 博主链接博客内容主要围绕： 5G/6G协议讲解高级C语言讲解 Rust语言讲解文章目录在"星睿"O6的“周易”NPU上部署Yolov8l模型并实现…...

编程日记 2025/8/28 23:33:10

[ctfshow web入门] web4

前置知识 robots.txt是机器人协议，在使用爬虫爬取网站内容时应该遵循的协议。协议并不能阻止爬虫爬取，更像是一种道德规范。假设robots.txt中写道 Disallow: /admind.php，那我就暴露了自己的后台，这属于信息泄漏，攻击…...

编程日记 2025/8/27 13:02:52

Golang的Goroutine（协程）与runtime

目录 Runtime 包概述 Runtime 包常用函数 1. GOMAXPROCS 2. Caller 和 Callers 3. BlockProfile 和 Stack 理解Golang的Goroutine Goroutine的基本概念特点： Goroutine的创建与启动示例代码解释 Goroutine的调度 Gosched的作用示例代码输出解…...

编程日记 2025/8/29 5:37:57

与Linux操作系统相关的引导和服务

目录一.Linux操作系统引导过程 1.1引导过程总览 1.2系统初始化进程 1.2.1init进程 1.2.2sysmted 1.3systemd单元类型二.排除启动类故障 2.1MBR扇区故障 2.1.1故障原因 2.1.2故障现象 2.1.3解决办法 2.1.4模拟修复MBR扇区故障 1)添加新的硬盘 2）进行…...

编程日记 2025/8/28 7:46:34

JS API 事件监听

焦点事件案例：搜索框激活下拉菜单事件对象事件对象存储事件触发时的相关信息可以判断用户按键，点击元素等内容如何获取事件绑定的回调函数中的第一个形参就是事件对象一般命名为e,event 事件对象常用属性 type类型 click mouseenter client…...

编程日记 2025/8/23 18:58:47

【8】搭建k8s集群系列（二进制部署）之安装node节点组件（kubelet）

一、下载k8s二进制文件下载地址： https://github.com/kubernetes/kubernetes/blob/master/CHANGELOG/CHANGELOG -1.20.md 注：打开链接你会发现里面有很多包，下载一个 server 包就够了，包含了 Master 和 Worker Node 二进制文件。…...

编程日记 2025/8/29 5:34:19

Harmony OS“一多” 详解：基于窗口变化的断点自适应实现

一、一多开发核心概念（18N模式） 目标：一次开发多端部署解决的问题： 1、界面级一多：适配不同屏幕尺寸 2、功能级一多：设备功能兼容性处理(CanIUser) 3、工…...

编程日记 2025/8/27 15:58:40

Rust切片、结构体、枚举

文章目录切片类型字符串切片其他结构的切片结构体结构体实例元组结构体结构体所有权输出结构体结构体的方法结构体关联函数单元结构体枚举match语法Option枚举类if let 语句切片类型切片（Slice）是对数据值的部分“引用” 我们可以从一个数据集合中…...

编程日记 2025/8/27 4:05:19

量子纠错码实战：从Shor码到表面码

引言：量子纠错的必要性量子比特的脆弱性导致其易受退相干和噪声影响，单量子门错误率通常在10⁻~10⁻量级。量子纠错码（QEC）通过冗余编码测量校正的机制，将逻辑量子比特的错误率降低到可容忍水平。本文从首个量子纠错…...

编程日记 2025/8/28 1:12:47

Pod的生命周期

概念 Pod对象自从其创建开始至其终止退出的时间范围称为其生命周期。在这段时间中，Pod会处于多种不同的状态，并执行一些操作；其中，创建主容器（main container）为必需的操作，其他可选的操作还包…...

编程日记 2025/8/29 0:19:24

使用QAction编辑器添加QAction到ui里

在 Qt Designer 或 Qt Creator 的 UI 设计器中，可以直接通过 Action Editor 可视化添加和管理 QAction，无需手动编写代码。以下是详细步骤： 步骤 1：打开 Action Editor 在 Qt Creator 中打开 .ui 文件（双击项目中的…...

编程日记 2025/8/27 21:29:44

Unity：标签（tags）

为什么需要Tags？ 在游戏开发中，游戏对象（GameObject）数量可能非常多，比如玩家、敌人、子弹等。开发者需要一种简单的方法来区分这些对象，并根据它们的类型执行不同的逻辑。核心需求： 分类和管…...

编程日记 2025/8/29 2:57:19

深入解析 Python 正则表达式：全面指南与实战示例

深入解析 Python 正则表达式：全面指南与实战示例 📌 引言正则表达式（Regular Expressions, regex）是用于文本匹配、查找和替换的强大工具。在 Python 中，我们可以使用 re 模块来处理正则表达式。无论是数据清洗、日…...

编程日记 2025/8/28 13:40:25

Nginx介绍及使用

1.Nginx介绍 Nginx是一款开源的、高性能的HTTP和反向代理服务器 1.正向代理和反向代理正向代理（代理客户端）是一种位于客户端和目标服务器之间的中间服务器。客户端通过正向代理服务器向目标服务器发送请求，代理服务器将请求转发给目标服…...

编程日记 2025/8/27 15:12:45

【Block总结】自适应矩形卷积，即插即用|CVPR2025

论文信息标题: Adaptive Rectangular Convolution for Remote Sensing Pansharpening年份: 2025年会议: CVPR论文地址: arXiv代码地址: GitHub任务: 遥感图像融合（Pansharpening） 创新点本论文提出了一种新颖的自适应矩形卷积模块（ARCon…...

编程日记 2025/8/28 7:44:13

第2课：JSX语法与组件基础

第2课：JSX语法与组件基础学习目标深入理解JSX语法掌握组件的基本结构和用法学习使用Props传递数据掌握React中的样式添加方法创建任务卡片组件一、JSX语法深入 1. 什么是JSX？ JSX是JavaScript XML的缩写，它允许我们在JavaScript中编写…...

编程日记 2025/8/27 21:55:27

DevOps与Docker的关系

DevOps 与 Docker 是相辅相成的关系。DevOps 是一种强调开发（Development）与运维（Operations）之间协作的文化、实践和工具链，而 Docker 是一种容器化技术，为 DevOps 的实现提供了高效的技术支撑。 Docker …...

编程日记 2025/8/27 3:45:12

嵌入式AI简介

嵌入式AI是一种将人工智能算法部署在终端设备中运行的技术，使智能硬件能够在本地实时完成感知、交互和决策功能，无需依赖云端计算。以下是其核心要点： 一、核心特点 1. 本地化处理：数据在设备端直接处理，无需联网&a…...

编程日记 2025/8/28 12:44:28

多GPU训练

写在前面限于财力不足，本机上只有一个 GPU 可供使用，因此这部分的代码只能够稍作了解，能够使用的 GPU 也只有一个。多 GPU 的数据并行：有几张卡，对一个小批量数据，有几张卡就分成几块，每个 …...

编程日记 2025/8/28 1:13:01

JVM虚拟机篇（三）：JVM运行时数据区与方法区详解

JVM虚拟机篇（三）：JVM运行时数据区与方法区详解 JVM虚拟机篇（三）：JVM运行时数据区与方法区详解一、引言二、JVM运行时数据区2.1 概述2.2 各部分的作用与交互2.2.1 堆与其他区域的关系2.2.2 方法区与其他区域…...

编程日记 2025/8/27 9:45:26

Rust学习日记：编写一个Python扩展

参考https://segmentfault.com/a/1190000044555330 命令行创建一个新的Rust项目cargo new --lib rust_python_ext 配置Cargo.toml [package] name "rust_python_ext" version "0.1.0" edition "2024"[lib] name "rust_python_ext"…...

编程日记 2025/8/28 13:23:29

Pod的调度

在默认情况下，一个Pod在哪个Node节点上运行，是由Scheduler组件采用相应的算法计算出来的，这个过程是不受人工控制的。但是在实际使用中，这并不满足的需求，因为很多情况下，我们想控制某些Pod到达某些节点上&…...

编程日记 2025/8/28 7:07:50

系统思考：思考的快与慢

在做重大决策之前，什么原因一定要补充碳水化合物？人类的大脑其实有两套运作模式：系统1：自动驾驶模式，依赖直觉，反应快但易出错；系统2：手动驾驶模式，理性严谨，…...

编程日记 2025/8/27 16:50:51

[ 计算机网络 ] | HTTP协议(一)

目录前置知识： URL URL的URLENCODE和URLDECODE HTTP协议的宏观格式如何保证报文是完整的？怎么做序列，反序列化的？ 前置知识： URL 我们把数据给别人，别人把数据给我们，不是在做IO嘛~&am…...

编程日记 2025/8/27 7:25:24

大模型快速 ASGI 服务器uvicorn

基础概念类 1. 什么是 Uvicorn，它的作用是什么？ 答案：Uvicorn 是一个基于 Python 的快速 ASGI（异步服务器网关接口）服务器。它的主要作用是作为 Web 应用程序的服务器，负责接收客户端的请求，并…...

编程日记 2025/8/28 19:20:44

android studio 基础

1.android Module not specified 今天做一个实验时出现：Android Studio Run/Debug configuration error: Module not specified，要想解决这个问题： 1、打开根目录的 settings.gradle，删除 include :exampleapp 2、在 Android Stu…...

编程日记 2025/8/28 3:03:11

python爬虫爬取淘宝热销(热门)零食商品加数据清洗、销量、店铺及词云数据分析_源码及相关说明文档；售后可私博主

TOC 如有侵权,联系删除一、环境说明使用前必须检查以下环境 （1）python编译环境 （2）python脚本执行所需要的库，具体看代码（main.py）import导入的部分库 （3）确保电脑可…...

编程日记 2025/8/26 23:49:13

Android /proc/meminfo解释

高通8295设备 msmnile_gvmq:/proc # cat meminfo MemTotal: 16433968 kB MemFree: 7709832 kB…...

编程日记 2025/8/27 18:05:02

VScode 玩 MCP的server

vscode 1.99版本刚支持MCP server，我就测试了一下翻到一个gitte的MCP sever 我本身是Mac版本1.99居然没更新agent，所以我就直接用1.100版本的vscode inside了来掩饰一下了点击setting，然后你要edit一下这个json配置文件主要修改的其实是…...

编程日记 2025/8/28 4:08:24

详解 MySQL 索引的最左前缀匹配原则

MySQL 的最左前缀匹配原则主要是针对复合索引（也称为联合索引）而言的。其核心思想是：只有查询条件中包含索引最左侧（第一列）开始的连续一段列，才能让 MySQL 有效地利用该索引。一、复合索引的结构复合…...

编程日记 2025/8/28 10:15:26

ROS Master多设备连接

Bash Shell Shell是位于用户与操作系统内核之间的桥梁，当用户在终端敲入命令后，这些输入首先会进入内核中的tty子系统，TTY子系统负责捕获并处理终端的输入输出流，确保数据正确无误的在终端和系统内核之中。Shell在此过程不仅仅是…...

编程日记 2025/8/27 20:35:33

【Mysql】数据库备份与恢复

一、备份类型物理备份：直接对数据库的数据文件、日志文件、索引文件进行备份逻辑备份：对数据库对象（库、表）以SQL语句的形式导出进行备份二、备份工具 1、使用tar、gzip等方式压缩打包数据库文件（完全备份、物理冷…...

编程日记 2025/8/28 11:21:21

Java HttpURLConnection修仙指南：从萌新到HTTP请求大能的渡劫手册

一、筑基篇：初识HttpURLConnection 1.1 基础开光（创建连接） URL url new URL("https://api.example.com/data"); HttpURLConnection conn (HttpURLConnection) url.openConnection(); // 注意！此处可能抛出Malforme…...

编程日记 2025/8/24 16:58:12

python 重要易忘语言基础

Collections 1、Counter 计数器 counter:计数器类似字典统计可迭代对象中元素的出现次数, Counter({b: 3, c: 2, a: 1, d: 1}) 相当于字典{b: 3, c: 2, a: 1, d: 1} a.items() 取键值对对应为dict_items([(a, 1), (b, 3), (c, 2), (d, 1)]) 也可以是 list(a.items…...

编程日记 2025/8/27 10:34:20

【新能源汽车研发测试数据深度分析：从传感器到智能决策的硬核方法论】

摘要： 本文系统性解构新能源汽车（NEV）研发测试中的数据采集、处理及分析全链条，覆盖传感器融合、大数据清洗、AI算法优化等核心技术，并引入行业顶级案例（如特斯拉Autopilot验证、宁德时代BMS算法迭代&#…...

编程日记 2025/8/27 12:56:56

GD32H759IMT6 Cortex-M7 OpenHarmony轻量系统移植——接管中断修改为不接管

笔者在去年利用国庆时间，将Cortex-M7 的国产厂商兆易创新GD32H459移植OpenHarmony轻量系统，但是适配不太完善——只能选择liteos-m接管中断。这样导致使用中断非常麻烦。于是笔者最近将接管中断模式修改为不接管，这样可以方便的使用gd32提供的…...

编程日记 2025/8/26 13:01:51

MySQL基础学习笔记

学习笔记 1. 基础小知识1.1 数据库分类1.2 下载安装、变量配置过程（略）1.3 连接命令1.4 连接mysql服务端的软件选择1.4.1 要求不高的话，选择有很多1.4.2 适合做企业级管理的工具（适合团队协作）1.4.3 总结 1.5 编程语言…...

编程日记 2025/8/26 1:32:12

[Linux]进程状态、僵尸进程处理回收、进程优先级 + 图例展示

目录一、进程状态 1.一般操作系统学科的进程状态二、Linux操作系统的进程状态运行状态（R） 睡眠状态（S） 深度睡眠状态（D） 暂停状态（T） 追踪暂停状态&#x…...

编程日记 2025/8/28 0:27:16

2022 年 6 月青少年软编等考 C 语言七级真题解析

目录 T1. 有多少种二叉树思路分析T2. 城堡问题T3. 快速堆猪思路分析T4. 重建二叉树思路分析T1. 有多少种二叉树题目链接：SOJ D1189 输入 n ( 1 < n < 13 ) n\ (1<n<13) n (1<n<13)，求 n n n 个结点的二叉树有多少种形态？思路分析此题考查 C a…...

编程日记 2025/8/28 9:42:15

flutter修改 Container 中的 Text 和 Image 的样式

在Flutter中，Container 是一个常用的布局组件，它可以包含子组件（如文本、图片等），并允许你通过设置各种属性来自定义样式。如果你需要修改 Container 中的 Text 和 Image 的样式，可以通过以下方式实现。 1.…...

编程日记 2025/8/28 10:01:04

零基础入门unity游戏开发——动画篇】Animation动画窗口，创建编辑动画

考虑到每个人基础可能不一样，且并不是所有人都有同时做2D、3D开发的需求，所以我把【零基础入门unity游戏开发】分为成了C#篇、unity通用篇、unity3D篇、unity2D篇。【C#篇】：主要讲解C#的基础语法，包括变量、数据类型、运算符、…...

编程日记 2025/8/27 6:09:45

【设计模式】命令模式

简介假设你有一个智能家居遥控器，上面有多个按钮，每个按钮对应不同的设备操作（如开灯、关灯、调空调温度）。命令模式的解决方案是： 将每个操作（如“开灯”）封装成一个独立的命令对象&#x…...

编程日记 2025/8/28 10:07:45

Python作业3 字符田字格绘制

字符田字格绘制：编写程序,用字符方式打印输出一个简单的田字格,要求采用函数方式,以田字格宽度为参数,能够根据参数绘制任意大小的田字格。 def draw(n):line 3 * n 1for i in range(1, line 1):if i % 3 1:print(n * " —— —— ", end"&quo…...

编程日记 2025/8/28 1:57:32