解題區►解題區 - UVa

UVa 1343 - The Rotation Game

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

一款很神秘的遊戲，盤面上只會有 1, 2, 3 三種數字，可以藉由八種轉動方式，目標是將中間的八格變成都是相同數字。

求最少步數。

Sample Input

1
2
3
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

Sample Output

1
2
3
4
AC
2
DDHH
2

Solution

一開始設想，直接將三個分開討論，只考慮目標為 1 或 2 或 3，將狀態只變成 0/1，但分開計算的結果再取最小值可能會太慢，利用 BFS 很容易造成 TLE。

藉由 IDA* 的思路，啟發函數為中間位置還差多少個目標才能湊滿八個，因為每一次轉動，至多增加某一個數字在中間的個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXSTATE 1048576
#define MAXN (20000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXN];
// 24! / (8! 16!) = 735471
int shift[8][8] = {
    {0, 2, 6, 11, 15, 20, 22},      // A
    {1, 3, 8, 12, 17, 21, 23},      // B
    {10, 9, 8, 7, 6, 5, 4},         // C
    {19, 18, 17, 16, 15, 14, 13},   // D
    {23, 21, 17, 12, 8, 3, 1},      // E
    {22, 20, 15, 11, 6, 2, 0},      // F
    {13, 14, 15, 16, 17, 18, 19},   // G
    {4, 5, 6, 7, 8, 9, 10}          // H
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int invShift[8] = {5, 4, 7, 6, 1, 0, 3, 2};
void shiftStrip(int A[], int dir) {
    int tmp = A[shift[dir][0]];
    for (int i = 0; i < 6; i++)
        A[shift[dir][i]] = A[shift[dir][i+1]];
    A[shift[dir][6]] = tmp;
}
int H(int A[]) {
    int K[4] = {};
    for (int i = 0; i < 8; i++) {
        K[A[center[i]]]++;
    }
    return 8 - max(K[1], max(K[2], K[3]));
}
int ida_depth, solved;
int path[128];
int IDA(int A[], int dep, int hv) {
    if (hv == 0) {
        solved = 1;
        if (dep == 0) {
            puts("No moves needed");
        } else {
            for (int i = 0; i < dep; i++)
                printf("%c", path[i] + 'A');
            puts("");
        }
        printf("%d\n", A[center[0]]);
        return dep;
    }
    if (dep + hv > ida_depth)
        return dep + hv;
    int back = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < 8; i++) {
        shiftStrip(A, i);
        shv = H(A), path[dep] = i;
        tmp = IDA(A, dep + 1, shv);
        back = min(back, tmp);
        shiftStrip(A, invShift[i]);
        if (solved) return back;
    }
    return back;
}
int main() {
    while (true) {
        int A[32];
        for (int i = 0; i < 24; i++) {
            scanf("%d", &A[i]);
            if (A[i] == 0)  return 0;
        }
        solved = 0;
        for (ida_depth = 0; solved == 0;)
            ida_depth = IDA(A, 0, H(A));
    }
    return 0;
}
/*
 
*/