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.

样例输入

12
212X453786
312345678X
4564178X23
57568X4123

样例输出

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

提示

无

思路

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

564178X23→123456X78

7568X4123→5126X3478

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

代码

  1using namespace std;
  2typedef long long ll;
  3const int inf = 0x3f3f3f3f;
  4const int N = 4e5+5;
  5
  6int vis[9][N], pre[9][N];
  7int T, n = 9;
  8int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
  9
 10int dx[] = { 1,  0,  0, -1};
 11int dy[] = { 0, -1,  1,  0};
 12char dir[] = "dlru";
 13
 14int s[][9] = {
 15    {9, 1, 2, 3, 4, 5, 6, 7, 8},
 16    {1, 9, 2, 3, 4, 5, 6, 7, 8},
 17    {1, 2, 9, 3, 4, 5, 6, 7, 8},
 18    {1, 2, 3, 9, 4, 5, 6, 7, 8},
 19    {1, 2, 3, 4, 9, 5, 6, 7, 8},
 20    {1, 2, 3, 4, 5, 9, 6, 7, 8},
 21    {1, 2, 3, 4, 5, 6, 9, 7, 8},
 22    {1, 2, 3, 4, 5, 6, 7, 9, 8},
 23    {1, 2, 3, 4, 5, 6, 7, 8, 9}
 24};
 25
 26struct P {
 27    int a[10];
 28    int h, x;
 29};
 30
 31int cantor(int *s) {
 32    int sum = 0;
 33    for(int i=0; i<n; i++) {
 34        int num = 0;
 35        for(int j=i+1; j<n; j++) {
 36            if(s[j]<s[i])
 37                num++;
 38        }
 39        sum += num*fac[n-i-1];
 40    }
 41    return sum;
 42}
 43
 44void decantor(int sum, int *t) {
 45    int vis[10] = {0};
 46    for(int i=0; i<n; i++) {
 47        int tmp = sum/fac[n-i-1];
 48        for(int j=0; j<=tmp; j++) {
 49            if(vis[j])
 50                tmp++;
 51        }
 52        t[i] = tmp+1;
 53        vis[tmp] = 1;
 54        sum %= fac[n-i-1];
 55    }
 56}
 57
 58void bfs(int k) {
 59    P sp;
 60    for(int i=0; i<n; i++) {
 61        sp.a[i] = s[k][i];
 62    }
 63    sp.h = cantor(sp.a);
 64    sp.x = k;
 65
 66    queue<P> q;
 67    q.push(sp);
 68    vis[k][sp.h] = 1;
 69
 70    while(!q.empty()) {
 71        P tp = q.front();
 72        q.pop();
 73
 74        P np;
 75        for(int i=0; i<4; i++) {
 76            int x = tp.x/3+dx[i];
 77            int y = tp.x%3+dy[i];
 78            if(x<0 || x>=3 || y<0 || y>=3) {
 79                continue;
 80            }
 81            np = tp;
 82            np.x = x*3+y;
 83
 84            swap(np.a[np.x], np.a[tp.x]);
 85            np.h = cantor(np.a);
 86
 87            if(vis[k][np.h]==-1) {
 88                q.push(np);
 89                vis[k][np.h] = i;
 90                pre[k][np.h] = tp.h;
 91            };
 92        }
 93    }
 94}
 95
 96int main(void) {
 97    memset(vis, -1, sizeof(vis));
 98    memset(pre, -1, sizeof(pre));
 99    for(int i=0; i<n; i++)
100        bfs(i);
101
102    scanf("%d", &T);
103    for(int cs=1; cs<=T; cs++) {
104        char str[10];
105        int k, num[10], t[10];
106
107        scanf("%s", str);
108        for(int i=0, j=1; i<n; i++) {
109            if(str[i]=='X')
110                k = i;
111            else
112                num[str[i]-'0'] = j++;
113        }
114
115        scanf("%s", str);
116        for(int i=0; i<n; i++) {
117            if(str[i]=='X')
118                t[i] = 9;
119            else
120                t[i] = num[str[i]-'0'];
121        }
122        int h = cantor(t);
123
124        string path = "";
125        while(h!=-1) {
126            path += dir[vis[k][h]];
127            h = pre[k][h];
128        }
129        printf("Case %d: %d\n", cs, path.length()-1);
130
131        for(int i=path.length()-2; i>=0; i--)
132            printf("%c", path[i]);
133        printf("\n");
134    }
135
136    return 0;
137}