题目链接

题意

经典的八数码的题目，还要判断是否有解，wiki链接

解题思路

用IDA*算法来解决，先算出当前状态和目标状态的哈曼顿距离，当距离为0时即解出答案。
有两个可以剪枝的条件：

  • 下一个方向和当前的方向不能相反
  • 当前的步数加上当前的哈曼顿距离不能大于初始状态的哈曼顿距离

关于8数码是否有解，可参考这篇文章

AC代码

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
#include<vector>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring>
#include<functional>
#include<map>
#include<cmath>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> PII;
const int maxn = 1e6+5;
int goal[10][2] = {{2,2},{0,0},{0,1},{0,2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}};
int G[10][10];
int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
char dir[] = {‘d’,‘l’,‘r’,‘u’};

int manhattan()
{
    int sum = 0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            int w = G[i][j];
            if(w==0)continue;
            sum += abs(goal[w][0] - i) + abs(goal[w][1] - j);
        }
    }
    return sum;
}
char sta[500];
bool flag = 0;
void idastar(int x,int y,int pre,int step,int top)
{
    if(flag)return;
    for(int i=0;i<4;i++){
        if(flag)return;
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx > 2||ny>2||nx < 0||ny<0)continue;
        if(pre + i == 3)continue;
        swap(G[x][y],G[nx][ny]);
        int mht = manhattan();
        if(mht==0){
            sta[step] = dir[i];
            printf(“%s\n”,sta);
            flag = 1;
            return;
        }
        if(mht + step <= top){
            if(flag) return;
            sta[step] = dir[i];
            idastar(nx,ny,i,step+1,top);
        }
        swap(G[x][y],G[nx][ny]);
    }
}

bool isok(int state)
{
    int sum = 0;
    for(int i=0;i<9;i++){
        int num = 0;
        if(state[i]==0)continue;
        for(int j=i+1;j<9;j++){
            if(state[i] > state[j]&&state[j])
                num++;
        }
        sum += num;
    }
    return sum%2;
}

int main(int argc, char const argv[])
{
    char s[100];
    while(~scanf(“ %c”,&s[0])){
        memset(sta,0,sizeof(sta));
        for(int i=1;i<9;i++){
            scanf(“ %c”,&s[i]);
        }
        flag = 0;
        int bx,by;
        int state[10];
        for(int i=0;i<9;i++){
            if(s[i]==‘x’){
                G[i/3][i%3] = 0;
                state[i] = 0;
                bx = i/3;
                by = i%3;
            }else{
                G[i/3][i%3] = s[i]-‘0’;
                state[i] = s[i] - ‘0’;
            }
        }
        
        if(isok(state)){
            printf(“unsolvable\n”);
            continue;
        }
        int ans = manhattan();
        if(ans==0){
            printf(“\n”);
            continue;
        }

        int top = 0;
        while(++top){
            idastar(bx,by,-1,0,top);
            if(flag)
                break;
        }
    }
    
    return 0;
}