前言

好的，首先说明一下，这里用的是字符串的方法。根据c++字符串的尿性，速度比较慢，当然也可以改成字符数组，只不过我比较懒（没错╭(╯^╰)╮）

正题

有个2*4的矩阵被称为魔板，有三种操作

“A”：交换上下两行；

“B”：将最右边的一列插入最左边；

“C”：魔板中央四格作顺时针旋转。

然后初始状态是

1 2 3 4

8 7 6 5

然后嘞，就是嘞

给出一个状态，要求改变到那个状态。

输入输出（建议无视）

Input

只有一行，包括8个整数，用空格分开（这些整数在范围 1——8 之间），表示目标状态。

Output

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

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

Sample Input

2 6 8 4 5 7 3 1

Sample Output

BCABCCB

解题思路

这道题就是得把一块板线性化，然后找出变化规律。然后用哈希来判断重复优化广搜。

将线性化之后的版转换为数字，然后存进哈希表里判断重复。

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int ruler[3][8]={
   {
   8,7,6,5,4,3,2,1},{
   4,1,2,3,6,7,8,5},{
   1,7,2,4,5,3,6,8}};//变化公式string state[100003];//状态string hash[100003],ss;//哈希表int head,tail,z,x,father[100003],num[100003];char dot[100003];int hashm(string s)//哈希表{    int w=0;    for (int i=0;i<8;i++)    {        w=w*10+s[i]-48;    }//转成数字    w%=100003;//哈希函数    int i=0;    while (i<100003 && hash[(w+i)%100003]!="" && hash[(w+i)%100003]!=s)      i++;//定位    if (hash[(w+i)%100003]=="")//如果找到空位    {        hash[(w+i)%100003]=s;//记录        return false;    }    else return true;//放回找到}void bfs(){       hashm("12345678");//记录状态    head=0;tail=1;    state[1]="12345678";//状态记录    do    {        head++;//出队        for (int i=0;i<3;i++)        {            tail++;//入队            father[tail]=head;//记录上一个            state[tail]="";//状态为空            num[tail]=num[head]+1;//记录改变次数            if (i==0) dot[tail]='A';            if (i==1) dot[tail]='B';            if (i==2) dot[tail]='C';//记录操作            for (int j=0;j<8;j++)            {              state[tail]+=state[head][ruler[i][j]-1];              //变化状态            }            if (hashm(state[tail])) tail--;//拒绝入队            else if (state[tail]==ss) return;//找到退出        }    }    while(head