1151 魔板

sicily algorithm 广搜 康托展开

---

---

原题中文描述

原题链接

魔板由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。
其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作：
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
用上述三种基本操作，可将任一种状态装换成另一种状态。

---

输入

输入包括多个要求解的魔板，每个魔板用三行描述。
第一行步数N，表示最多容许的步数.
第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。
当N等于-1的时候，表示输入结束.

---

输出

对于每一个要求解的魔板，输出一行.
首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格.
注意：如果不能达到，则M输出-1即可.

---

算法思想

• 广搜 - bfs
• 枚举所有可能的三种操作
• 利用康托展开来唯一标识每一个转移status
• 判重
• 第一个可行解就是最优解

至于康托展开的理解, 可以看下我写的一篇博文

---

数据结构

用数组变量来保存每次魔板转移操作的信息

const int M = 40330 ;
const int N = 8 ;
// 存储康托展开的个数, 即魔板方块的个数的阶乘
int ktNums[9] = {0 , 1 , 2 , 6 , 24 , 120 , 720 , 5040 , 40320} ;
// 记录魔板是否转移
bool visited[M] ;
// 存储每次转移的操作
string str[M] ;

---

解题思路及算法描述

1. 初始化搜索路径的init status及对应的变量visited(为bool数组, 取值为false), 字符串数组变量str为空,
2. 进行bfs搜索:
   2.1记录init status s, 将其放进列表, 并计算其的康托值ktVal, 设visited[ktVal]设为true
   2.2定义一个列表list<int*> q ;, 将s放进q里(入列)
   2.3进行广搜while(!q.empty())

2.3.1 获取列表`q`的队首`f = q.front()`, 并删除队首`q.pop_front()`
2.3.2 对`f`进行`A,B,C,`三种操作, 得到对应的`a,b,c`转移状态
2.3.3 如果`a,b,c`还没有被访问, 则分别将其放入队列`q`, 并计算其的康托值`ktVal`和设置其对应的状态`visited[ktVal]`为`true`, 否则不再扩展
2.3.4 `str`记录转移过程
2.3.5 直到循环条件结束

3.广搜结束

这里只需一次广搜所有可能的转移转移操作及其对应的转移status, 因为每次搜索的开始status是一样的.

---

code

// Problem#: 1151
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <list>
using namespace std ;
const int M = 40330 ;
const int N = 8 ;
int ktNums[9] = {0 , 1 , 2 , 6 , 24 , 120 , 720 , 5040 , 40320} ;
bool visited[M] ;
string str[M] ;
int bf[N] ;
// 康托展开
int cator(int q[]) {
    int i, j ;
    int result = 0 ;
    for (i = 0 ; i < N - 1 ; i++) {
        int count = 0 ;  
        for (j = i + 1 ; j < N ; j++)
            if (q[j] < q[i]) 
                count++ ;
        result += count * ktNums[N - i - 1] ;
    }
    return result ;
}
bool isEqual(int *a , int *b) {
    for(int i = 0 ; i < N ; i++) {
        if(a[i] != b[i]) {
            return 0 ;
        }
    }
    return 1 ;
}
// init the start status
void inni(int *a) {
    a[0] = 1 ; a[1] = 2 ;
    a[2] = 3 ; a[3] = 4 ;
    a[4] = 8 ; a[5] = 7 ;
    a[6] = 6 ; a[7] = 5 ;
}
void A(int *a ,int *b) {
    b[0] = a[4] ; b[1] = a[5] ;
    b[2] = a[6] ; b[3] = a[7] ;
    b[4] = a[0] ; b[5] = a[1] ;
    b[6] = a[2] ; b[7] = a[3] ;
}
void B(int *a ,int *b) {
    b[1] = a[0] ; b[2] = a[1] ;
    b[3] = a[2] ; b[0] = a[3] ;
    b[5] = a[4] ; b[6] = a[5] ;
    b[7] = a[6] ; b[4] = a[7] ;
}
void C(int *a ,int *b) {
    b[0] = a[0] ; b[3] = a[3] ;
    b[4] = a[4] ; b[7] = a[7] ;
    b[1] = a[5] ; b[2] = a[1] ;
    b[6] = a[2] ; b[5] = a[6] ;
}
void bfs() {
    list<int*> q ;
    int T , tt ;
    int *f  = new int[N] ;
    // int *f;
    // init
    memset(visited, false, sizeof(visited));
    inni(f) ;
    q.push_back(f) ;
    visited[cator(f)] = 1 ;
    while(!q.empty()) {
        int *fa = new int[N] ;
        int *fb = new int[N] ;
        int *fc = new int[N] ;
        // get the front status from the list
        f = q.front() ;
        // then pop and never visit it
        q.pop_front() ;
        if(isEqual(f , bf))
            break ;
        // compute the correspond kt value
        tt = cator(f) ;
        // A operation
        A(f , fa) ;
        //  compute the kt value
        T = cator(fa) ;
        // if not visited, visit it
        if(!visited[T]) {
            q.push_back(fa) ;
            visited[T] = true ;
            str[T] = str[tt] + "A" ;
        }
        // B operation
        B(f , fb) ;
        // compute the correspond kt value
        T = cator(fb) ;
        // if not visited, visit it
        if(!visited[T]) {
            q.push_back(fb) ;
            visited[T] = true ;
            str[T] = str[tt] + "B" ;
        }
        // C operation
        C(f , fc) ;
        // compute the correspond kt value
        T = cator(fc) ;
        // if not visited, visit it
        if(!visited[T]) {
            q.push_back(fc) ;
            visited[T] = true ;
            str[T] = str[tt] + "C" ;
        }
    }
}
int main() {
    int t , k ;
    // the start status
    int g[N] ;
    inni(g) ;
    // because each case start from the same status
    // so just bfs() one time
    bfs() ;
    while(cin >> t , t != -1) {
        for(int i = 0 ; i < N ; i++){
            cin >> bf[i] ;
        }
        // determin the target status is equal to 
        // the initial status
        if(isEqual(bf , g)) {
            cout << 0 << endl ;
        } else {
            // get kt value 
            k = cator(bf) ;
            // determine whether reach the target status
            if(!str[k].empty() && str[k].size() <= t) {
                cout << str[k].size() << ' ' << str[k] << endl ;
            } else {
                cout << -1 << endl ;
            }
        }
    }
    return 0 ;
}                                                                

---

测试数据

下面给出4给样例, 其中每个样例的第一行表示允许操作的步长, 第二行表示输入的target status, 第三行表示输出结果(按题意输出)
1.

3
3 2 4 7 1 6 8 5
-1

2.

9
3 5 4 7 1 6 8 2
-1

3.

16
5 8 7 6 4 1 2 3
AB

4.

20
2 4 3 7 1 6 8 5
CBBCBCBCBCBCBCB

5

-1
end

---

时间复杂度分析

总体来说, 对其进行判重后, 时间复杂度为O(n!), 其中n为魔板方块的个数.
(因为对初始status或者中间某个status进行三种转移操作后, 其输出的status不外乎是魔板的全排列中的一个)

---

end