热门标签 | 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;
}

推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
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社区 版权所有