热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BFSUSACOMagicSquares(魔板)

BFS-USACO-MagicSquares(魔板)Rubik先生在发明了风靡全球的魔方之后,又发明了它的二维版本——魔板。这是一张有8个大小相同的格子的魔板&#

BFS - USACO - Magic Squares(魔板)

Rubik 先生在发明了风靡全球的魔方之后,又发明了它的二维版本——魔板。

这是一张有 8 个大小相同的格子的魔板:

1 2 3 4
8 7 6 5

我们知道魔板的每一个方格都有一种颜色。

这 8 种颜色用前 8 个正整数来表示。

可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。

对于上图的魔板状态,我们用序列 (1,2,3,4,5,6,7,8) 来表示,这是基本状态。

这里提供三种基本操作,分别用大写字母 A,B,C 来表示(可以通过这些操作改变魔板的状态):

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

下面是对基本状态进行操作的示范:

A:

8 7 6 5
1 2 3 4

B:

4 1 2 3
5 8 7 6

C:

1 7 2 4
8 6 3 5

对于每种可能的状态,这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。

**注意:**数据保证一定有解。

输入格式
输入仅一行,包括 8 个整数,用空格分开,表示目标状态。

输出格式
输出文件的第一行包括一个整数,表示最短操作序列的长度。

如果操作序列的长度大于0,则在第二行输出字典序最小的操作序列。

数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。

输入样例:

2 6 8 4 5 7 3 1

输出样例:

7
BCABCCB


分析:

要求操作步数最少,字典序尽量小。要求操作步数最少,字典序尽量小。,

要字典序小,就按照A、B、C的顺序进行操作,用哈希表d存储每一种状态与初始状态之间的距离(操作次数),pre存储每一种状态是由哪一种状态转移而来的,是以何种操作转移而来的。要字典序小,就按照A、B、C的顺序进行操作,用哈希表d存储每一种状态与初始状态之间的距离(操作次数),\\pre存储每一种状态是由哪一种状态转移而来的,是以何种操作转移而来的。,ABC,d(),pre,

需要注意的是,本题是按照顺时针的顺序来表示状态的,为了与我们习惯一致,set函数来对第二列的数进行翻转操作。即将12345678转化为12348765。需要注意的是,本题是按照顺时针的顺序来表示状态的,为了与我们习惯一致,set函数来对第二列的数进行翻转操作。\\即将12345678转化为12348765。,,,set1234567812348765

BFS求出最小步数后,再通过pre表反推具体操作。BFS求出最小步数后,再通过pre表反推具体操作。BFS,pre

代码:

#include
#include
#include
#include
#includeusing namespace std;const int N = 1e6;string set(string u)
{string v;for(int i&#61;0;i<4;i&#43;&#43;) v&#43;&#61;u[i];for(int i&#61;7;i>&#61;4;i--) v&#43;&#61;u[i];return v;
}string A(string t)
{t&#61;set(t);for(int j&#61;0;j<4;j&#43;&#43;) swap(t[j],t[j&#43;4]);return set(t);
}string B(string t)
{t&#61;set(t);char u&#61;t[3],v&#61;t[7];for(int i&#61;3;i>&#61;1;i--){t[i]&#61;t[i-1];t[i&#43;4]&#61;t[i&#43;4-1];}t[0]&#61;u,t[4]&#61;v;return set(t);
}string C(string t)
{t&#61;set(t);char u&#61;t[1];t[1]&#61;t[5];t[5]&#61;t[6];t[6]&#61;t[2];t[2]&#61;u;return set(t);
}string S&#61;"12345678",E;
string q[N];
unordered_map<string,int> d;
unordered_map<string,pair<char,string>> pre;void bfs()
{int hh&#61;0,tt&#61;-1;q[&#43;&#43;tt]&#61;S;d[S]&#61;0;while(hh<&#61;tt){string t&#61;q[hh&#43;&#43;];if(t&#61;&#61;E) return ;string u[3];u[0]&#61;A(t);u[1]&#61;B(t);u[2]&#61;C(t);for(int i&#61;0;i<3;i&#43;&#43;)if(!d.count(u[i])){d[u[i]]&#61;d[t]&#43;1;pre[u[i]]&#61;{char(&#39;A&#39;&#43;i),t};q[&#43;&#43;tt]&#61;u[i];}}
}int main()
{char c;for(int i&#61;0;i<8;i&#43;&#43;){cin>>c;E&#43;&#61;c;}bfs();int step&#61;d[E];cout<<step<<endl;string ans;while(E!&#61;S){ans&#43;&#61;pre[E].first;E&#61;pre[E].second;}reverse(ans.begin(),ans.end());if(step) cout<<ans<<endl;return 0;
}

推荐阅读
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
author-avatar
UP7家族--婵婵_172
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有