【题解】HDU-3567 Eight II

发表于 分类于 ， ， ， 本文字数： 1.6k 阅读时长 ≈ 3 分钟
HDU-3567 Eight II 类型 BFS打表 康拓展开 路径输出

Eight II （HDU - 3567)

题面

Eight-puzzle, which is also called "Nine grids", comes from an old game.

In this game, you are given a 3 by 3 board and 8 tiles. The tiles are numbered from 1 to 8 and each covers a grid. As you see, there is a blank grid which can be represented as an 'X'. Tiles in grids having a common edge with the blank grid can be moved into that blank grid. This operation leads to an exchange of 'X' with one tile.

We use the symbol 'r' to represent exchanging 'X' with the tile on its right side, and 'l' for the left side, 'u' for the one above it, 'd' for the one below it.

img

A state of the board can be represented by a string S using the rule showed below.

img

The problem is to operate an operation list of 'r', 'u', 'l', 'd' to turn the state of the board from state A to state B. You are required to find the result which meets the following constrains: \1. It is of minimum length among all possible solutions. \2. It is the lexicographically smallest one of all solutions of minimum length.

输入

The first line is T (T <= 200), which means the number of test cases of this problem.

The input of each test case consists of two lines with state A occupying the first line and state B on the second line. It is guaranteed that there is an available solution from state A to B.

输出

For each test case two lines are expected.

The first line is in the format of "Case x: d", in which x is the case number counted from one, d is the minimum length of operation list you need to turn A to B. S is the operation list meeting the constraints and it should be showed on the second line.

样例输入

1
2
3
4
5
2
12X453786
12345678X
564178X23
7568X4123

样例输出

1
2
3
4
Case 1: 2
dd
Case 2: 8
urrulldr

提示

无

思路

思考一下，'X’在9个不同位置的目标状态可以反推所有情况。这时我们只需要简单映射一下：

564178X23→123456X78

7568X4123→5126X3478

大致思路就很明确了。继续思考字典序的问题，由于推导顺序和题目要求一致，则不需要和Eight(HDU - 1043)一般将方向颠倒，只用按字典序(dlru)排就行 注意参考代码中最后的路径是由pre数组链接的，直接倒推回去恰好和我们需要的相反，所以存入串中再逆序输出。而初始状态的方向被随意的存了一个1(vis数组)，所以在数量上和最后输出中都要-1 用了康拓展开，感觉再用上逆展开太耗时了，没想到好的方法，就在结构体里面丢了一个数组。尽管本题时间和空间限制范围都挺大。以后还得好好深入一下八数码八境界

代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 4e5+5;

int vis[9][N], pre[9][N];
int T, n = 9;
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

int dx[] = { 1,  0,  0, -1};
int dy[] = { 0, -1,  1,  0};
char dir[] = "dlru";

int s[][9] = {
    {9, 1, 2, 3, 4, 5, 6, 7, 8},
    {1, 9, 2, 3, 4, 5, 6, 7, 8},
    {1, 2, 9, 3, 4, 5, 6, 7, 8},
    {1, 2, 3, 9, 4, 5, 6, 7, 8},
    {1, 2, 3, 4, 9, 5, 6, 7, 8},
    {1, 2, 3, 4, 5, 9, 6, 7, 8},
    {1, 2, 3, 4, 5, 6, 9, 7, 8},
    {1, 2, 3, 4, 5, 6, 7, 9, 8},
    {1, 2, 3, 4, 5, 6, 7, 8, 9}
};

struct P {
    int a[10];
    int h, x;
};

int cantor(int *s) {
    int sum = 0;
    for(int i=0; i<n; i++) {
        int num = 0;
        for(int j=i+1; j<n; j++) {
            if(s[j]<s[i])
                num++;
        }
        sum += num*fac[n-i-1];
    }
    return sum;
}

void decantor(int sum, int *t) {
    int vis[10] = {0};
    for(int i=0; i<n; i++) {
        int tmp = sum/fac[n-i-1];
        for(int j=0; j<=tmp; j++) {
            if(vis[j])
                tmp++;
        }
        t[i] = tmp+1;
        vis[tmp] = 1;
        sum %= fac[n-i-1];
    }
}

void bfs(int k) {
    P sp;
    for(int i=0; i<n; i++) {
        sp.a[i] = s[k][i];
    }
    sp.h = cantor(sp.a);
    sp.x = k;

    queue<P> q;
    q.push(sp);
    vis[k][sp.h] = 1;

    while(!q.empty()) {
        P tp = q.front();
        q.pop();

        P np;
        for(int i=0; i<4; i++) {
            int x = tp.x/3+dx[i];
            int y = tp.x%3+dy[i];
            if(x<0 || x>=3 || y<0 || y>=3) {
                continue;
            }
            np = tp;
            np.x = x*3+y;

            swap(np.a[np.x], np.a[tp.x]);
            np.h = cantor(np.a);

            if(vis[k][np.h]==-1) {
                q.push(np);
                vis[k][np.h] = i;
                pre[k][np.h] = tp.h;
            };
        }
    }
}

int main(void) {
    memset(vis, -1, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    for(int i=0; i<n; i++)
        bfs(i);

    scanf("%d", &T);
    for(int cs=1; cs<=T; cs++) {
        char str[10];
        int k, num[10], t[10];

        scanf("%s", str);
        for(int i=0, j=1; i<n; i++) {
            if(str[i]=='X')
                k = i;
            else
                num[str[i]-'0'] = j++;
        }

        scanf("%s", str);
        for(int i=0; i<n; i++) {
            if(str[i]=='X')
                t[i] = 9;
            else
                t[i] = num[str[i]-'0'];
        }
        int h = cantor(t);

        string path = "";
        while(h!=-1) {
            path += dir[vis[k][h]];
            h = pre[k][h];
        }
        printf("Case %d: %d\n", cs, path.length()-1);

        for(int i=path.length()-2; i>=0; i--)
            printf("%c", path[i]);
        printf("\n");
    }

    return 0;
}