八数码问题

有许多问题都可以转化为图的遍历的问题，但是之前我们做的题目的图要么是一开始就根据题意建立起来然后去遍历或者更加简单题目直接给你。

但是类似于八数码问题它的图并不是一开始给你的，而是由程序动态生成的，称为隐式图。我们需要找到一个符合条件的终止路径

八数码问题

编号为 1~8 的 8个正方形滑块被摆成3行3列（有一个格子空留）。每次可以把与空格相邻的滑块（有公共边才算相邻）移到空格中，而它原来的位置就称为了

新的空格。给定初始局面和目标局面（ 用0表示空格格 ），你的任务是计算出最少的移动步数。 如果无法达到目标局面，则输 -1 

题目链接：https://www.luogu.com.cn/problem/P1379

　　　　 http://acm.hit.edu.cn/problemset/1868

分析：

既然是要找到最少的移动步数，那么很容易去想到利用 BFS 进行搜索，但是最主要的问题是这个涉及到隐式图的遍历，如何去记录隐式图以及如何去避免重复的搜索

根据紫书上的建议有两种比较常用：

1、直接采用STL里面的 set 进行去重

2、采用 hash 表的方式

STL的方式：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <string.h>
 5 #include <vector>
 6 #include <map>
 7 #include <stack>
 8 #include <set>
 9 #include <queue>
10 #include <math.h>
11 #include <time.h>
12 
13 #define LL long long
14 #define INF 0x3f3f3f3f
15 #define ls nod<<1
16 #define rs (nod<<1)+1
17 
18 const int maxn = 1e6 + 10;
19 const LL MOD = 1e9 + 7;
20 
21 typedef int State[9];
22 State st[maxn],goal;
23 int dis[maxn];
24 
25 int dx[] = {-1,1,0,0};
26 int dy[] = {0,0,-1,1};
27 
28 std::set<int> vis;
29 
30 
31 void init_lookup_table() {
32     vis.clear();
33 }
34 
35 int try_to_insert(int s) {
36     int v = 0;
37     for (int i = 0;i < 9;i++)
38         v = v * 10 + st[s][i];
39     if (vis.count(v))
40         return 0;
41     vis.insert(v);
42     return 1;
43 }
44 
45 int bfs() {
46     init_lookup_table();
47     int front = 1,rear = 2;
48     while (front < rear) {
49         State &s = st[front];
50         if (memcmp(goal,s, sizeof(s)) == 0) {
51             return front;
52         }
53         int z;
54         for (z = 0;z < 9;z++) {
55             if (!s[z])
56                 break;
57         }
58         int x = z / 3,y = z % 3;
59         for (int d = 0;d < 4;d++) {
60             int newx = x + dx[d];
61             int newy = y + dy[d];
62             int newz = newx * 3  +newy;
63             if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
64                 State &t = st[rear];
65                 memcpy(&t,&s, sizeof(s));
66                 t[newz] = s[z];
67                 t[z] = s[newz];
68                 dis[rear] = dis[front] + 1;
69                 if (try_to_insert(rear))
70                     rear++;
71             }
72         }
73         front++;
74     }
75     return 0;
76 }
77 
78 
79 int main() {
80     int t;
81     scanf("%d",&t);
82     while (t--) {
83         for (int i = 0; i < 9; i++) {
84             scanf("%d", &st[1][i]);
85         }
86         for (int i = 0; i < 9; i++)
87             scanf("%d", &goal[i]);
88         int ans = bfs();
89         if (ans > 0)
90             printf("%d
", dis[ans]);
91         else
92             printf("-1
");
93     }
94     return 0;
95 }

Ackerman

hash表的方式：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <string>
  4 #include <string.h>
  5 #include <vector>
  6 #include <map>
  7 #include <stack>
  8 #include <set>
  9 #include <queue>
 10 #include <math.h>
 11 #include <cstdio>
 12 #include <time.h>
 13 
 14 #define LL long long
 15 #define INF 0x3f3f3f3f
 16 #define ls nod<<1
 17 #define rs (nod<<1)+1
 18 
 19 const int maxn = 4e5 + 10;
 20 const LL MOD = 1e9 + 7;
 21 
 22 const int hashsize = 1000003;
 23 typedef int State[9];
 24 State st[maxn],goal;
 25 int head[hashsize],Next[maxn];
 26 int dis[maxn];
 27 
 28 int dx[] = {-1,1,0,0};
 29 int dy[] = {0,0,-1,1};
 30 
 31 void init_lookup_table() {
 32     memset(head,0, sizeof(head));
 33 }
 34 
 35 int hash(State &s) {
 36     int v = 0;
 37     for (int i = 0;i < 9;i++)
 38         v = v * 10 + s[i];
 39     return v % hashsize;
 40 }
 41 
 42 int try_to_insert(int s) {
 43     int h = hash(st[s]);
 44     int u = head[h];
 45     while (u) {
 46         if (memcmp(st[u],st[s], sizeof(st[s])) == 0)
 47             return 0;
 48         u = Next[u];
 49     }
 50     Next[s] = head[h];
 51     head[h] = s;
 52     return 1;
 53 }
 54 
 55 int bfs() {
 56     init_lookup_table();
 57     int front = 1,rear = 2;
 58     while (front < rear) {
 59         State &s = st[front];
 60         if (memcmp(goal,s, sizeof(s)) == 0) {
 61             return front;
 62         }
 63         int z;
 64         for (z = 0;z < 9;z++) {
 65             if (!s[z])
 66                 break;
 67         }
 68         int x = z / 3,y = z % 3;
 69         for (int d = 0;d < 4;d++) {
 70             int newx = x + dx[d];
 71             int newy = y + dy[d];
 72             int newz = newx * 3  +newy;
 73             if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
 74                 State &t = st[rear];
 75                 memcpy(&t,&s, sizeof(s));
 76                 t[newz] = s[z];
 77                 t[z] = s[newz];
 78                 dis[rear] = dis[front] + 1;
 79                 if (try_to_insert(rear))
 80                     rear++;
 81             }
 82         }
 83         front++;
 84     }
 85     return 0;
 86 }
 87 
 88 
 89 int main() {
 90     int t;
 91     scanf("%d",&t);
 92     while (t--) {
 93         for (int i = 0; i < 9; i++) {
 94             scanf("%d", &st[1][i]);
 95         }
 96         for (int i = 0; i < 9; i++)
 97             scanf("%d", &goal[i]);
 98         int ans = bfs();
 99         if (ans > 0)
100             printf("%d
", dis[ans]);
101         else
102             printf("-1
");
103     }
104     return 0;
105 }

Ackerman