• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

算法竞赛入门经典——八数码 (Cantor展开 + 一堆c++语法)

开发技术 开发技术 2天前 9次浏览

Experience:

1.如果本地ac而oj上re,很有可能是数组开小了

2.

typedef int State[9];//相当于一种结构体,在st中作为数组的第二维

3.Cantor板子

int code = 0;
for (int i = 0; i < 9; i++) {
  int cnt = 0;
  for (int j = i + 1; j < 9; j++) if (a[j] < a[i]) cnt++;
  code += fact[8 - i] * cnt;
}

4.返回值与0的大小关系即为str1与str2的大小关系

memcmp(goal, s, sizeof(s))

5.取地址可以访问二维数组中的某一维,从而简化代码

State &a = st[s];

6.memcpy 目标/源头/要被复制的字节数

memcpy(&t, &s, sizeof(s));

7.手写队列BFS的一种写法

int bfs() {
  //do something 
  int l = 1, r = 2;
  while (l < r) {
    ...;//取出队首
    if (ok) return l;
    for(...) {
   st[r] = ... ....
if (ok) r++; } l++; } return 0; }

 

Code:

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 typedef int State[9];//相当于一种结构体,在st中作为数组的第二维
 5 const int maxstate = 1e6 + 10;
 6 State st[maxstate], goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
 7 int dist[maxstate];
 8 
 9 int vis[362880], fact[9];
10 void init_lookup_table() {
11   fact[0] = 1;
12   for (int i = 1; i < 9; i++) fact[i] = fact[i - 1] * i;
13 }
14 int try_to_insert(int s) {
15   State &a = st[s]; //取地址<->别名
16   //Cantor板子
17   int code = 0;
18   for (int i = 0; i < 9; i++) {
19     int cnt = 0;
20     for (int j = i + 1; j < 9; j++) if (a[j] < a[i]) cnt++;
21     code += fact[8 - i] * cnt;
22   }
23   if (vis[code]) return 0;
24   return vis[code] = 1;
25 }
26 
27 const int dx[] = {-1, 1, 0, 0};
28 const int dy[] = {0, 0, -1, 1};
29 int bfs() {
30   init_lookup_table();
31   int l = 1, r = 2;
32   while (l < r) {
33     State &s = st[l];//取出队首
34     if (memcmp(goal, s, sizeof(s)) == 0) return l;
35     int z;
36     for (z = 0; z < 9; z++) if (!s[z]) break;
37     int x = z / 3, y = z % 3;
38     for (int i = 0; i < 4; i++) {
39       int tx = x + dx[i], ty = y + dy[i], tz = tx * 3 + ty;
40       if (tx >= 0 && ty >= 0 && tx < 3 && ty < 3) {
41         State &t = st[r];
42         memcpy(&t, &s, sizeof(s));
43         t[tz] = s[z];
44         t[z] = s[tz];
45         dist[r] = dist[l] + 1;
46         if (try_to_insert(r)) r++;
47       }      
48     }
49     l++;
50   }
51   return 0;
52 }
53 
54 int main() {
55   for (int i = 0; i < 9; i++) {
56     char c[2];
57     scanf("%s", c);
58     st[1][i] = isdigit(c[0]) ? c[0] - '0' : 0;
59   }
60   //for (int i = 0; i < 9; i++) printf("%d ", st[1][i]); puts("");
61   int ans = bfs();
62   if (ans > 0) printf("%d", dist[ans]);
63   else printf("-1");
64   return 0;
65 }

 

 

喜欢 (0)