POJ 2286 The Rotation Game

康复计划 之 ida*

题意：

这种玩具要你操作最少次数且操作字典序最小，使得中间的8个数字相同。

思路：
迭代加深 启发式 搜索
估价函数采用 8 – 中间数字最多的数字数量
因为每次操作如果想达到最终结果，一次最多只能转化出一个，如 aaab ，一次转化出两个的话，中间那个必定不相同，可以自己在纸上试试。

这道题本身在深搜层数上并不会很大，ida * 的优势就体现了出来。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;
int ary[30], deep;
int center[] = { 7, 8, 9, 12, 13, 16, 17, 18 };
int ret[] = { 5, 4, 7, 6, 1, 0, 3, 2 };
int mat[][8] = {
    { 1, 3, 7, 12, 16, 21, 23 },
    { 2, 4, 9, 13, 18, 22, 24 },
    { 11, 10, 9, 8, 7, 6, 5 },
    { 20, 19, 18, 17, 16, 15, 14 },
    { 24, 22, 18, 13, 9, 4, 2 },
    { 23, 21, 16, 12, 7, 3, 1 },
    { 14, 15, 16, 17, 18, 19, 20 },
    { 5, 6, 7, 8, 9, 10, 11 }
};

bool isEnd()
{
    int tmp = ary[7];
    for (int i = 1; i < 8; i++)
        if (tmp != ary[center[i]])
            return false;
    return true;
}

void change(int dir)
{
    int tmp = ary[mat[dir][0]];
    for (int i = 0; i < 6; i++)
        ary[mat[dir][i]] = ary[mat[dir][i + 1]];
    ary[mat[dir][6]] = tmp;
}

int getH()
{
    int num[4] = { 0 };
    for (int i = 0; i < 8; i++)
        num[ary[center[i]]]++;
    return 8 - max(num[1], max(num[2], num[3]));
}

bool dfs(int now)
{
    if (now == deep)
        return isEnd();
    int h = getH();
    if (now + h > deep)
        return false;
    for (int i = 0; i < 8; i++) {
        change(i);
        ans.push_back(i);
        if (dfs(now + 1))
            return true;
        ans.pop_back();
        change(ret[i]);
    }
    return false;
}

int main()
{
    while (scanf("%d", &ary[1]) != EOF && ary[1]) {
        for (int i = 2; i <= 24; i++)
            scanf("%d", ary + i);
        ans.clear();
        if (isEnd()) {
            puts("No moves needed");
            printf("%d\n", ary[7]);
            continue;
        }
        deep = 1;
        while (dfs(0) == false)
            deep++;
        for (unsigned i = 0; i < ans.size(); i++)
            printf("%c", ans[i] + 'A');
        printf("\n%d\n", ary[7]);
    }
    return 0;
}