经典题目：八数码

广搜处理的对象不仅可以是一个数，还可以是一种状态，这里最经典的题目就是八数码

先来道基础的题目

点击查看题目

  • 题目描述

    在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

  • 输入格式

    输入初始状态，一行九个数字，空格用0表示

  • 输出格式

    只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

  • 样例 #1

    • 样例输入 #1

      1
      283104765

    • 样例输出 #1

      1
      4

对于这道题，我们需要从给定的初始状态变化到目标状态，当我们在搜索的时候，可以直接将生成的子状态加入到队列中，每次再取出状态来处理，这就是所谓的状态图搜索

确定了思路，就有两个主要问题

  • 怎么表示状态
  • 怎么去重

朴素做法

因为洛谷上的这道题比较简单，对于第一个问题，可以直接将 3x3 的数组转换为一个 9 位的数字，使用 int 来保存

而去重的话，可以直接借助于 STL 中的 map 或者 set

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
#include <bits/stdc++.h>
#define swap(a, b) { int t = a; a = b; b = t; }
using namespace std;
const int N = 3;
const int M = 4;
const int TARGRT = 123804765;
const int dx[M] = {0, 1, 0, -1};
const int dy[M] = {1, 0, -1, 0};
struct point
{
    int x, y;
};
map<int, int> dist;

inline int board2number(int board[N][N])
{
    int number = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            number = number * 10 + board[i][j];

    return number;
}
inline point number2board(int number, int board[N][N])
{
    point zero;
    for (int i = N - 1; i >= 0; i--)
        for (int j = N - 1; j >= 0; j--)
        {
            board[i][j] = number % 10;
            number /= 10;
            if (board[i][j] == 0)
            {
                zero.x = i;
                zero.y = j;
            }
        }
    return zero;
}

void bfs(int start)
{
    int board[N][N];
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        if (now == TARGRT)
            return;
        point zero = number2board(now, board);
        point next;
        for (int i = 0; i < M; i++)
        {
            next.x = zero.x + dx[i];
            next.y = zero.y + dy[i];
            if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N)
            {
                swap(board[zero.x][zero.y], board[next.x][next.y]);
                int next_number = board2number(board);
                if (dist.count(next_number) == 0)
                {
                    dist[next_number] = dist[now] + 1;
                    q.push(next_number);
                }
                swap(board[zero.x][zero.y], board[next.x][next.y]);
            }
        }
    }
}
int main()
{
    int start;
    cin >> start;
    bfs(start);
    cout << dist[TARGRT] << endl;
}

image-20220716182603243

难度升级

接下来看一下升级了点难度的版本：hdu 1043

这道题除了变了一下输入格式，还有以下两点

  • 要求输出一个可行的解决方法（每次的动作）
  • 有多组数据

而这时，如果还使用上面的方法，就会 TLE

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
#include <bits/stdc++.h>
#define swap(a, b) \
    {              \
        int t = a; \
        a = b;     \
        b = t;     \
    }
using namespace std;
const int N = 3, M = 4, TARGRT = 123456780;
const int dx[M] = {0, 1, 0, -1};
const int dy[M] = {1, 0, -1, 0};
const char dir[M] = {'u', 'r', 'd', 'l'};
struct point
{
    int x, y;
};
map<int, pair<int, int>> search_log; // <number, <father, direction>>
// map<int, int> dist;

inline int board2number(int board[N][N])
{
    int number = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            number = number * 10 + board[i][j];

    return number;
}
inline point number2board(int number, int board[N][N])
{
    point zero;
    for (int i = N - 1; i >= 0; i--)
        for (int j = N - 1; j >= 0; j--)
        {
            board[i][j] = number % 10;
            number /= 10;
            if (board[i][j] == 0)
            {
                zero.x = i;
                zero.y = j;
            }
        }
    return zero;
}
void bfs(int start)
{
    int board[N][N];
    queue<int> q;
    q.push(start);
    // dist[start] = 0;
    search_log[start] = make_pair(-1, -1);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        if (now == TARGRT)
            return;
        point zero = number2board(now, board);
        point next;
        for (int i = 0; i < M; i++)
        {
            next.x = zero.x + dx[i];
            next.y = zero.y + dy[i];
            if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N)
            {
                swap(board[zero.x][zero.y], board[next.x][next.y]);
                int next_number = board2number(board);
                if (search_log.count(next_number) == 0)
                {
                    // dist[next_number] = dist[now] + 1;
                    search_log[next_number] = make_pair(now, i);
                    q.push(next_number);
                }
                swap(board[zero.x][zero.y], board[next.x][next.y]);
            }
        }
    }
}

int read()
{
    int number = 0;
    char c[10];
    scanf("%c  %c  %c  %c  %c  %c  %c  %c  %c", &c[0], &c[1], &c[2], &c[3], &c[4], &c[5], &c[6], &c[7], &c[8]);
    for (int i = 0; i < 9; i++)
    {
        if (c[i] != 'x')
            number = number * 10 + c[i] - '0';
        else
            number = number * 10 + 0;
    }
    return number;
}

void print()
{
    string ans;
    if (search_log.count(TARGRT) == 0)
    {
        printf("unsolvable\n");
        return;
    }

    int now = TARGRT;
    int father = search_log[now].first;
    int direction = search_log[now].second;
    ans.push_back(dir[direction]);
    // printf("%c", dir[direction]);
    while (father != -1)
    {
        now = father;
        father = search_log[now].first;
        direction = search_log[now].second;
        ans.push_back(dir[direction]);
        // printf("%c", dir[direction]);
    }
    reverse(ans.begin(), ans.end());
    cout << ans<<endl;
}

int main()
{
    while (1)
    {
        search_log.clear();
        int start = read();
        bfs(start);
        print();
    }

    // cout << dist[TARGRT] << endl;
}

image-20220716190719302

使用康托展开

为了解决 TLE 的问题，我减少了 STL 的使用，不再使用 map 去重和保存历史，而是使用简单的结构体数组

但是，这个数组要开多大呢？这取决于表示状态的方法，现在是直接将 9 宫格展开成数字，这样结构体下标就是 9 位数

但如果这样的话，这个数组就开会到 search_log[1000000000] ，内存直接爆炸，显然是不行的

image-20220716191646096

当你尝试在 HDUOJ 上开一个超大数组（滑稽）

如何解决这一问题呢？可以使用康托展开

简单地说，康托展开可以求出某一排列在所有排列中的序号

例如， 9 个数的全排列共有 9!=3628809!=362880 种，使用康托展开可以将所有状态与编号一一对应，这样结构体的大小就降到了可以承受的地步，只用开到 search_log[362880]

经过上述改进的版本如下

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
#define swap(a, b) \
    {              \
        int t = a; \
        a = b;     \
        b = t;     \
    }
using namespace std;
const int N = 3, M = 4, MAX = 362880, TARGRT = 0;
const int FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
const int dx[M] = {0, 1, 0, -1};
const int dy[M] = {1, 0, -1, 0};
const char dir[M] = {'u', 'r', 'd', 'l'};
struct point
{
    int x, y;
};
struct log
{
    bool vis;
    int father;
    int move_direction;
} search_log[MAX];
struct node
{
    int state[9];
    point zero_pos;
    int CantorValue;
} start;

inline int To1D(point p)
{
    return p.x * 3 + p.y;
}
inline point To2D(int x)
{
    point p;
    p.x = x % 3;
    p.y = x / 3;
    return p;
}

inline int Cantor(int a[9])
{
    int x = 0;
    for (int i = 0; i < 9; i++)
    {
        int count = 0;
        for (int j = i + 1; j < 9; j++)
        {
            if (a[i] > a[j])
                count++;
        }
        x += FACT[9 - i - 1] * count;
    }
    return x;
}

inline void bfs()
{
    //memset(search_log, 0, sizeof(search_log));
    queue<node> q;
    q.push(start);
    search_log[start.CantorValue].vis = true;
    search_log[start.CantorValue].father = -1;
    search_log[start.CantorValue].move_direction = -1;
    while (!q.empty())
    {
        node now = q.front();
        q.pop();
        if (now.CantorValue == TARGRT)
            return;

        for (int i = 0; i < M; i++)
        {
            point swap_pos = now.zero_pos;
            swap_pos.x += dx[i];
            swap_pos.y += dy[i];
            if (swap_pos.x < 0 || swap_pos.x >= 3 || swap_pos.y < 0 || swap_pos.y >= 3)
                continue;
            node next = now;
            swap(next.state[To1D(swap_pos)], next.state[To1D(now.zero_pos)]);
            next.CantorValue = Cantor(next.state);
            if (search_log[next.CantorValue].vis)
                continue;
            search_log[next.CantorValue].vis = true;
            next.zero_pos = swap_pos;
            search_log[next.CantorValue].father = now.CantorValue;
            search_log[next.CantorValue].move_direction = i;
            q.push(next);
        }
    }
}
inline bool is_digit(char c)
{
    return c >= '0' && c <= '9';
}
inline bool read()
{
    char a[9], tmp = getchar();
    int i = 0;
    while (i != 9)
    {
        while (!is_digit(tmp) && tmp != 'x')
            if ((tmp = getchar()) == EOF)
                return false;

        a[i] = tmp;
        i++;
        tmp = getchar();
    }
    // scanf("%c %c %c %c %c %c %c %c %c", &a[0], &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8]);
    for (int i = 0; i < 9; i++)
    {
        if (a[i] != 'x')
        {
            start.state[i] = a[i] - '0';
            start.zero_pos = To2D(i);
        }

        else
            start.state[i] = 9;
    }
    start.CantorValue = Cantor(start.state);
    return true;
}
inline void print()
{
    int now = TARGRT;
    if (search_log[now].vis == false)
    {
        printf("unsolvable\n");
        return;
    }
    while (now != start.CantorValue)
    {
        printf("%c", dir[search_log[now].move_direction]);
        now = search_log[now].father;
    }
    printf("\n");
}
void init()
{
    memset(search_log, 0, sizeof(search_log));
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    while (read())
    {
        // print start
        //  for (int i = 0; i < 9; i++)
        //      printf("%d", start.state[i]);
        init();
        bfs();
        print();

    }
}

但是很不幸，由于依旧使用了 STL （ queue ） ，抑或是我的码风不好，面对这么多组数据还是败下阵来

image-20220716193237538

打表

现在怎么办？

俗话说的好：暴搜出奇迹，打表出省一！既然查询这么多，那么为何不直接从终点出发搜索，全跑一遍？这样后续的查询就全都是 O(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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
#define swap(a, b) \
    {              \
        int t = a; \
        a = b;     \
        b = t;     \
    }
using namespace std;
const int N = 3, M = 4, MAX = 362880, TARGRT = 0;
const int FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
const int dx[M] = {0, 1, 0, -1};
const int dy[M] = {1, 0, -1, 0};
// const char dir[M] = {'u', 'r', 'd', 'l'};
const char dir[M] = {'l', 'u', 'r', 'd'};
struct point
{
    int x, y;
};
struct log
{
    bool vis;
    int father;
    int move_direction;
} search_log[MAX];
struct node
{
    int state[9];
    point zero_pos;
    int CantorValue;
} start,target = {
    {1, 2, 3, 4, 5, 6, 7, 8, 9},
    {2, 2},
    0};

inline int To1D(point p)
{
    return p.x * 3 + p.y;
}
inline point To2D(int x)
{
    point p;
    p.x = x % 3;
    p.y = x / 3;
    return p;
}

inline int Cantor(int a[9])
{
    int x = 0;
    for (int i = 0; i < 9; i++)
    {
        int count = 0;
        for (int j = i + 1; j < 9; j++)
        {
            if (a[i] > a[j])
                count++;
        }
        x += FACT[9 - i - 1] * count;
    }
    return x;
}

inline void bfs()
{
    // memset(search_log, 0, sizeof(search_log));
    queue<node> q;

    q.push(target);
    search_log[target.CantorValue].vis = true;
    search_log[target.CantorValue].father = -1;
    search_log[target.CantorValue].move_direction = -1;
    while (!q.empty())
    {
        node now = q.front();
        q.pop();

        for (int i = 0; i < M; i++)
        {
            point swap_pos = now.zero_pos;
            swap_pos.x += dx[i];
            swap_pos.y += dy[i];
            if (swap_pos.x < 0 || swap_pos.x >= 3 || swap_pos.y < 0 || swap_pos.y >= 3)
                continue;
            node next = now;
            swap(next.state[To1D(swap_pos)], next.state[To1D(now.zero_pos)]);
            next.CantorValue = Cantor(next.state);
            if (search_log[next.CantorValue].vis)
                continue;
            search_log[next.CantorValue].vis = true;
            next.zero_pos = swap_pos;
            search_log[next.CantorValue].father = now.CantorValue;
            search_log[next.CantorValue].move_direction = i;
            q.push(next);
        }
    }
}
inline bool is_digit(char c)
{
    return c >= '0' && c <= '9';
}
inline bool read()
{
    char a[9], tmp = getchar();
    int i = 0;
    while (i != 9)
    {
        while (!is_digit(tmp) && tmp != 'x')
            if ((tmp = getchar()) == EOF)
                return false;

        a[i] = tmp;
        i++;
        tmp = getchar();
    }
    // scanf("%c %c %c %c %c %c %c %c %c", &a[0], &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8]);
    for (int i = 0; i < 9; i++)
    {
        if (a[i] != 'x')
        {
            start.state[i] = a[i] - '0';
            start.zero_pos = To2D(i);
        }
        else
            start.state[i] = 9;
    }
    start.CantorValue = Cantor(start.state);
    return true;
}
inline void print()
{
    if(!search_log[start.CantorValue].vis)
        printf("unsolvable\n");
    else
    {
        int now = start.CantorValue;
        while (search_log[now].father != -1)
        {
            printf("%c", dir[search_log[now].move_direction]);
            now = search_log[now].father;

        }
        printf("\n");
    }
}
// void init()
// {
//     memset(search_log, 0, sizeof(search_log));
// }
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    bfs();
    while (read())
    {
        print();
    }
}

这样，终于过了，而且只花了 78ms

image-20220716194012011