Talk is Cheap, Show Me the Code!

0%

八数码

Posted on In

八数码问题，就是在一个含有1-8和x的3*3方格中，每次可以将x与其相邻位置的数字交换。使得最后变成

1 2 3
4 5 6
7 8 x

你要做的就是实现八数码的解决方案，并要求交换次数最少

输入描述:

输入一个3*3的矩阵，包含1-8和x。

输出描述:

输出需要移动的步数
如果不可能实现，输出-1。

示例1
输入

2 3 4
1 5 x
7 6 8

输出

19

bashuma_bfs.cppview raw
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 <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 400010;
struct node{
    int mp[3][3];
    int x, y;
    int step;
    int h;
}Q[N], now;

int F[10];

// 康拓展开
int Hash(int A[3][3]){
    int res = 0;
    char s[10]; int k=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) s[k++] = A[i][j];

    int t = 0;
    for(int i=0;i<k;i++){
        t = s[i];
        for(int j=0;j<i;j++)
            if(s[j] < s[i]) t--;
        res += (t-1) * F[8-i];
    }
    return res;
}

int st[N];
int rx[] = {0, -1, 0, 1};
int ry[] = {-1, 0, 1, 0};

bool check(int x, int y){
    return x>=0 && x <3 && y>=0 && y<3;
}


int bfs(){
    int L = 0, R = -1;
    now.step = 0;
    Q[++R] = now;
    int h;
    st[h = Hash(now.mp)] = 1;
    if(h==0) return 0;
    while(L<=R){
        now = Q[L++];
        for(int i=0;i<4;i++){
            if (check(now.x + rx[i], now.y + ry[i])){
                swap(now.mp[now.x + rx[i]][now.y + ry[i]], now.mp[now.x][now.y]);
                now.x += rx[i], now.y += ry[i];
                now.step ++;
                int h = Hash(now.mp);
                if(h==0) return now.step;
                if(!st[h]){
                    st[h] = 1;
                    Q[++R] = now;
                }
                now.x -= rx[i], now.y -= ry[i], now.step--;
                swap(now.mp[now.x + rx[i]][now.y + ry[i]], now.mp[now.x][now.y]);
            }
        }
    }
    return -1;
}


int main(){
    F[0] = 1;
    for(int i=1;i<10;i++) F[i] = F[i-1] * i;

    char s[10];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) {
            scanf("%s", s);
            if (s[0] == 'x') {
                now.x = i, now.y = j;
                s[0] = '9';
            }
            now.mp[i][j] = s[0] - '0';
        }

    printf("%d\n", bfs());
    return 0;
}
bashuma_ASTAR.cppview raw
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
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

const int N = 400010;
struct node{
    int mp[3][3];
    int x, y;
    int step, h;
    bool operator < (const node&A) const {
        return step+h > A.step + A.h;
    }
}now;

priority_queue<node> Q;
int F[10];

// 康拓展开
int Hash(int A[3][3]){
    int res = 0;
    char s[10]; int k=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) s[k++] = A[i][j];

    int t = 0;
    for(int i=0;i<k;i++){
        t = s[i];
        for(int j=0;j<i;j++)
            if(s[j] < s[i]) t--;
        res += (t-1) * F[8-i];
    }
    return res;
}

int st[N];
int rx[] = {0, -1, 0, 1};
int ry[] = {-1, 0, 1, 0};

bool check(int x, int y){
    return x>=0 && x <3 && y>=0 && y<3;
}

int H(int A[3][3]){
    int res = 0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            if(A[i][j] == 9) continue;
            int x = (A[i][j] - 1) /3;
            int y = (A[i][j] - 1) %3;
            res += abs(i-x) + abs(j-y);
        }
    return res;
}


int bfs(){
    now.step = 0; now.h = H(now.mp);
    Q.push(now);
    int h = Hash(now.mp);
    if(h==0) return 0;
    while(!Q.empty()){
        now = Q.top(); Q.pop();
        int h = Hash(now.mp);
        if(h==0) return now.step;  //弹出来时最优
        if(st[h]) continue;  //类比dijstra
        st[h] = 1;
        for(int i=0;i<4;i++){
            if (check(now.x + rx[i], now.y + ry[i])){
                swap(now.mp[now.x + rx[i]][now.y + ry[i]], now.mp[now.x][now.y]);
                now.x += rx[i], now.y += ry[i]; now.step ++; now.h = H(now.mp);
                Q.push(now); // no if before entering priority_queue
                now.x -= rx[i], now.y -= ry[i], now.step--;
                swap(now.mp[now.x + rx[i]][now.y + ry[i]], now.mp[now.x][now.y]); now.h = H(now.mp);
            }
        }
    }
    return -1;
}


int main(){
    F[0] = 1;
    for(int i=1;i<10;i++) F[i] = F[i-1] * i;

    char s[10];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++) {
            scanf("%s", s);
            if (s[0] == 'x') {
                now.x = i, now.y = j;
                s[0] = '9';
            }
            now.mp[i][j] = s[0] - '0';
        }

    printf("%d\n", bfs());
    return 0;
}