UVa1063/LA3807 The Rotation Game

题目链接

  本题是2004年icpc亚洲区域赛上海赛区的H题

题意

  如下图所示形状的棋盘上分别有8个1、2、3，要往A～H方向旋转棋盘，使中间8个方格数字相同。图（a）进行A操作后变为图（b），再进行C操作后变为图（c），这正是一个目标状态（因为中间8个方格数字相同）。要求旋转次数最少。如果有多解，操作序列的字典序应尽量小。

输入格式

  输入包括不超过 30 组测试数据。每个测试数据只包括一行，包含 24 个整数，每相邻两个整数之间用 1 个空格隔开，表示这个 “#” 形棋盘的初始状态。（这些整数的排列顺序是从上至下，同一行的从左至右。）每两组测试数据之间没有换行符。输入文件以一行 0 结束。

输出格式

  对于每组测试数据，输出两行。第一行用字符 A∼H 输出操作的方法，每两个操作字符之间没有空格分开，如果不需要任何步数，输出 No moves needed。第二行输出最终状态中最中间的 8 个格子里的数字。如果有多组解，输出操作次数最少的一组解；如果仍有多组解，输出字典序最小的一组。任意相邻两组测试数据的输出之间不需输出换行符。

分析

  《算法竞赛入门经典》题解：

  本题是一个典型的状态空间搜索问题，可惜如果直接套用八数码问题的框架会超时。为什么？学完第10章的组合计数部分后会知道：8个1、8个2、8个3的全排列个数为24!/(8!*8!*8!)=9465511770。换句话说，最坏情况下最多要处理这么多结点！

  解决方法很巧妙：本题要求的是中间8个数字相同，即8个1或者8个2或者8个3。因此可以分3次求解。当目标是“中间8个数字都是1”时，2和3就没有区别了（都是“非1”），因此状态总数变成了8个1，16个“非1”的全排列个数，24!/(8!*16!)=735471，在可以接受的范围内了。

  非常好的状态空间分析思路，按这个思路写BFS，虽然较慢但能通过。用迭代加深搜索IDDFS会快一些，最优的方法还是IDA*，其启发式函数可以这样定：当前操作完成后，统计中间8个数字1、2、3数量的最大值x，则至少还需要8-x步操作。IDA*做法其实不需要进行状态空间分析，也就不用分中间8个数字都是1或者2或者3三类情况了。

AC 代码

IDA*

#include <iostream>
using namespace std;

#define M 16
const int m = 8, n = 24, c[] = {6, 7, 8, 11, 12, 15, 16, 17}, f[] = {5, 4, 7, 6, 1, 0, 3, 2},
        idx[][7] = {{0, 2, 6, 11, 15, 20, 22}, {1, 3, 8, 12, 17, 21, 23},
                    {10, 9, 8, 7, 6, 5, 4}, {19, 18, 17, 16, 15, 14, 13},
                    {23, 21, 17, 12, 8, 3, 1}, {22, 20, 15, 11, 6, 2, 0},
                    {13, 14, 15, 16, 17, 18, 19}, {4, 5, 6, 7, 8, 9, 10}};
int v[n]; char a[M+1];

int h() {
    int cnt[] = {0, 0, 0, 0}, mx = 0;
    for (int j=0; j<m; ++j) mx = max(mx, ++cnt[v[c[j]]]);
    return m - mx;
}

bool IDAStar(int s, int d) {
    if (s == d) {
        for (int i=1; i<m; ++i) if (v[c[i]] != v[c[i-1]]) return false;
        return true;
    } else for (int i=0; i<m; ++i) if (s == 0 || f[i] != a[s-1]-'A') {
        int x = v[idx[i][0]];
        for (int j=1, k=m-1; j<k; ++j) v[idx[i][j-1]] = v[idx[i][j]];
        v[idx[i][m-2]] = x; a[s] = 'A'+i;
        if (s+h() < d && IDAStar(s+1, d)) return true;
        x = v[idx[i][m-2]];
        for (int j=m-2; j>0; --j) v[idx[i][j]] = v[idx[i][j-1]];
        v[idx[i][0]] = x;
    }
    return false;
}

void solve() {
    for (int i=1; i<n; ++i) cin >> v[i];
    for (int d=0; d<M; a[++d] = 0) if (IDAStar(0, d)) {
        cout << (d == 0 ? "No moves needed" : a) << endl << v[c[0]] << endl;
        break;
    }
}

int main() {
    while (cin >> v[0] && v[0]) solve();
    return 0;
}

分3次BFS

#include <iostream>
#include <cstring>
using namespace std;

#define M 735471 // C(24,8)
const int m = 8, n = 24, c[] = {6, 7, 8, 11, 12, 15, 16, 17}, f[] = {5, 4, 7, 6, 1, 0, 3, 2},
        idx[][7] = {{0, 2, 6, 11, 15, 20, 22}, {1, 3, 8, 12, 17, 21, 23},
                    {10, 9, 8, 7, 6, 5, 4}, {19, 18, 17, 16, 15, 14, 13},
                    {23, 21, 17, 12, 8, 3, 1}, {22, 20, 15, 11, 6, 2, 0},
                    {13, 14, 15, 16, 17, 18, 19}, {4, 5, 6, 7, 8, 9, 10}};
int s[M], q[M], p[M], a[M], v[n], g[n], t, b, cc, d; char ans[50], ss[50];

bool term() {
    for (int i=1; i<m; ++i) if (v[c[i]] != v[c[i-1]]) return false;
    return true;
}

bool term2() {
    for (int i=0; i<m; ++i) if (g[c[i]] != b) return false;
    return true;
}

void insert() {
    int x = 0;
    for (int i=0; i<n; ++i) x = x<<1 | (g[i] == b ? 1 : 0);
    int k = x % M;
    while (s[k]) {
        if (s[k] == x) return;
        k = (k+1) % M;
    }
    s[k] = x; q[t++] = k;
}

void decode(int x) {
    for (int i=n-1; i>=0; --i) g[i] = x&1 ? b : 0, x >>= 1;
}

void get_path(int f, char c, int d) {
    if (f) get_path(p[f], char('A'+ a[f]), d-1);
    ss[d] = c;
}

void bfs() {
    memset(s, t = 0, sizeof(s)); memset(ss, 0, sizeof(ss)); memcpy(g, v, sizeof(v)); ss[0] = 'X'; a[0] = -1; insert();
    for (int h=0, c=t, dd=1; h<c; ++h) {
        int k = q[h]; decode(s[k]);
        for (int i=0; i<m; ++i) if (f[i] != a[h]) {
            int x = g[idx[i][0]];
            for (int j=1, k=m-1; j<k; ++j) g[idx[i][j-1]] = g[idx[i][j]];
            g[idx[i][m-2]] = x;
            if (term2()) {
                get_path(h, char('A'+i), dd - 1);
                if (dd < d || strcmp(ss, ans) < 0) memcpy(ans, ss, sizeof(ss)), cc = b, d = dd;
                return;
            }
            p[t] = h; a[t] = i; insert();
            x = g[idx[i][m-2]];
            for (int j=m-2; j>0; --j) g[idx[i][j]] = g[idx[i][j-1]];
            g[idx[i][0]] = x;
        }
        if (h+1 == c) {
            c = t;
            if (++dd > d) return;
        }
    }
}

void solve() {
    for (int i=1; i<n; ++i) cin >> v[i];
    if (term()) {
        cout << "No moves needed" << endl << v[c[0]] << endl;
        return;
    }
    for (b=1, cc=0, d=50; b<4; ++b) bfs();
    cout << ans << endl << cc << endl;
}

int main() {
    while (cin >> v[0] && v[0]) solve();
    return 0;
}