题目背景

在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有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”:魔板中央四格作顺时针旋转。

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

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个整数,用空格分开(这些整数在范围 1——8 之间)不换行,表示目标状态。

输出格式:

Line 1: 包括一个整数,表示最短操作序列的长度。

Line 2: 在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出60个字符。

输入输出样例

输入样例#1:

2 6 8 4 5 7 3 1 
输出样例#1:

7
BCABCCB

说明

题目翻译来自NOCOW。

USACO Training Section 3.2

思路:见代码。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5e4 + , M = 165e5;
const int G[][]={{,,,,,,,,}, //操作A:交换上下两行
{,,,,,,,,}, //操作B:将最右边的一列插入最左边
{,,,,,,,,}};//操作C:魔板中央四格作顺时针旋转
//我们可以用一个常量数组来简单地表示ABC三种操作
//即经过这一次操作后,现在状态中的第i个位置是有原先的哪一个位置变换来的
int h[N][],a[],pf[N][];
char stk[N];
int t,w=,x,edt,now,top;
bool vis[M]; //用于判重的bool数组
int main(){
for(int i=;i<=;++i){
scanf("%d",&x);
edt=(edt<<)+x-;
}
//同样将目标状态转换为八进制数,便于我们直接判断
for(int i=;i<=;++i)
now=(now<<)+(h[][i]=i-);
//“<< 3”即表示位运算的右移三位,也就是乘以8
vis[now]=true; //注意初始状态也要标记为已经搜索过
if(now==edt)
return puts(""), ;
//注意如果初始状态和目标状态相同应直接退出
while((t++)<w){
for(int i=;i<;++i){
//对于答案中的操作字典序问题,我们考虑按照操作ABC的顺序搜索
//这样先搜索到的一定是字典序最小的
now=;
for(int j=;j<=;++j)
now=(now<<)+(a[j]=h[t][G[i][j]]);
//计算经过转换后的状态
if(vis[now]) continue; //判重
vis[now]=true;
pf[++w][]=t;
pf[w][]=i+'A';
//因为题目中要求输出操作序列
//记录队列中每一个元素是由之前的哪一个元素、经过哪一个操作转换来的
//然后按着当前搜到的目标状态倒着找回去,再顺着输出操作就是答案了
h[w][]=h[t][]+;
for(int j=;j<=;++j)
h[w][j]=a[j];
if(now==edt){ //转换到了目标状态
printf("%d\n",h[w][]);
x=w;
while(pf[x][]){
stk[++top]=pf[x][];
x=pf[x][];
}
//数组stk即记录转换到目标状态依次进行的操作
for(int i=top;i>=;--i)
putchar(stk[i]);
return ;
}
}
}
return ;
}

最新文章

  1. 基于STM32Cube的DAC数模转化
  2. NUI四种提交数据方式c
  3. 关于JS的数据类型的一些见解
  4. 使用Alcatraz来管理Xcode插件
  5. css3属性column知多少
  6. Struts Upload上传文件
  7. datagridview中combobox类型的cell选中一个下拉列表之后,立即生效的事件
  8. linux学习书籍推荐linux学习书籍推荐
  9. JDK重要包和Java学习方法论
  10. 字体圆润属性的使用-webkit-font-smoothing: antialiased
  11. VS插件 热
  12. 漏掉的账目(用C语言去重)
  13. 解决IOS移动端 Safari流浪器 onclick无法触发的问题
  14. 下拉菜单css
  15. java.util.Collections.copy():列表List浅拷贝
  16. [转载]Tomcat部署与配置
  17. spring整合Jersey 无法注入service的问题
  18. 动态规划-最大的正方形面积 Maximal Square
  19. 非系统服务如何随系统启动时自动启动(rc.local加了可执行权限,仍然没有生效)
  20. 微信小程序开发--宽为百分百,页面仍可左右滑动

热门文章

  1. [JZOJ]100047. 【NOIP2017提高A组模拟7.14】基因变异
  2. 三、frpc 完整配置文件
  3. 【安装配置Redis】
  4. 大道至简第一章读后感 Java伪代码形式
  5. FastDFS 实现图片上传_01
  6. jQuery fadeOut无效
  7. android开发面试题
  8. HDU 4313 Contest 2
  9. openfiler作为文件server,实现ISCSI共享存储
  10. Vitual Router in The Cloud