[洛谷P2730] 魔板 Magic Squares

洛谷题目链接:魔板

题目背景

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有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

简述一下题意: 给出一个序列,以及三种操作方式,求出最少达到目标序列的步数及进行的操作.



显然我们需要通过搜索来求解,有两种方法: 迭代深搜 和 广搜 .

很显然如果直接迭代的话,时间复杂度是\(O(3^{ans})\)级别的,这样搜不了答案为15以上的数据.所以这里考虑广搜.

我们可以将排列情况哈希一下,然后通过广搜搜最优解.

这里介绍一个定理: 康托展开 (其实这题可以不用).

这玩意是什么呢?应该可以算作是一中哈希方法.

• 康托展开:求一个排列情况是全排列中的第x项.
• 康托逆展开:求全排列的第x项是什么.

这里推荐一个觉得讲的比较好的博客:https://blog.csdn.net/wbin233/article/details/72998375

大概讲一下如何求一个排列的康托展开:

首先看有几个数小于最高位，然后这个数乘以数据规模-1的阶乘，累加到一个给定的值里面，然后第二位变为最高位，只向后找小于当前的值，一直到个位。

如果这题用康托展开的话,可以很大程度上减小空间复杂度(似乎并没有什么用).但是直接转8进制也是可以过的.

#include<bits/stdc++.h>

using namespace std;

const int N=20;

const int M=50000;

int jc[]={1,1,2,6,24,120,720,5040.40320};//预处理一个阶乘的数组

int a[N], aim[N], goal, c[50];

int step[M], con[M][N], q[M], vis[M], opt[M], pre[M];

void out(int x){

    //printf("x=%d pre[x]=%d\n",x,pre[x]);

    if(pre[x] > 1) out(pre[x]);

    if(x == 0) return;

    printf("%c",opt[x]-1+'A');

}

void change(int);//模拟改变情况

int contor(int ch[]){//求康托展开

    int res = 0;

    for(int i=1;i<=8;i++){

	    int cnt = 0;

	    for(int j=i+1;j<=8;j++)

	        if(ch[j] < ch[i]) cnt++;

	    res += cnt * jc[8-i];

    }

    return res;

}

void bfs(){

    int head = 0, tail = 1, x;

    while(head < tail){

	    x = head; head++;

	    if(q[x] == goal){

	        printf("%d\n",step[x]);

	        out(x); printf("\n");

	        exit(0);

	    }

	    for(int i=1;i<=3;i++){

	        memcpy(a,con[x],sizeof(a));

	        change(i); int nx = contor(a);

	        if(vis[nx]) continue;

	        q[++tail] = nx; vis[nx] = 1;

	        step[tail] = step[x]+1; opt[tail] = i; pre[tail] = x;

	        memcpy(con[tail],a,sizeof(a));

	    }

    }

}

int main(){

    //freopen("magic.in","r",stdin);

    //freopen("magic.out","w",stdout);

    for(int i=1;i<=8;i++) cin >> aim[i];

    for(int i=1;i<=8;i++) con[1][i] = i;

    goal = contor(aim);

    bfs();

    return 0;

}

void change(int f){

    if(f == 1){

	    for(int i=1;i<=4;i++)

	        swap(a[i],a[9-i]);

    }

    if(f == 2){

	    for(int i=4;i>1;i--)

	        swap(a[i],a[i-1]);

	    for(int i=5;i<8;i++)

	        swap(a[i],a[i+1]);

    }

    if(f == 3){

	    swap(a[7],a[6]); swap(a[6],a[3]);

	    swap(a[3],a[2]);

    }

    //out();

}