当前位置：首页 > news >正文

八数码问题

news 来源：原创 2024/5/4 2:33:49

类似于拼图游戏，只能移动和空白格相同的四周的格子，从初始状态到目标状态的最少步数。

很容易想到是bfs，至于具体怎么实现，关键点是状态的定义，定义的好事半功倍。

bfs里面有一个vis数组，如果你用一个vis[][][][][][][][][]，9维的数组来标记，是不合理的，数组也开不下，9⁹，

有hash可以帮忙，这里有两个方案，一个是自己写编码，解码的，其实和hash原理类似。具体的编码解码都只是一种策略。

记得数据结构考试的时候，有一道题目说是要怎么解决hash冲突，我就是写的加一个链表。后来听说不是这么做的，说什么直接加到后面一个单元，我觉得还不如加一个链表。

看了一下刘汝佳的写法，果然和我的思路相同，也是加一个链表。

然后最简单的方案就是stl里面的set了。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef int State[9];
  6 const int maxstadt = 1000000;
  7 State st[maxstadt],goal;
  8 
  9 int dist[maxstadt];
 10 
 11 const int dx[] = {-1,1,0,0};
 12 const int dy[] = {0,0,-1,1};
 13 
 14 /*
 15 int vis[362880],fact[9];
 16 
 17 void init_lookup_table() {
 18     fact[0] = 1;
 19     for(int i=1;i<9;i++)
 20         fact[i] = fact[i-1]*i;
 21 }
 22 
 23 int try_to_insert(int s) {
 24     int code = 0;
 25     for(int i=0;i<9;i++) {
 26         int cnt = 0;
 27         for(int j=i+1;j<9;j++)
 28             if(st[s][j]<st[s][i])
 29                 cnt++;
 30         code +=fact[8-i]*cnt;
 31     }
 32     if(vis[code]) return 0;
 33     return vis[code] = 1;
 34 }
 35 */
 36 
 37 /*
 38 set<int> vis;
 39 void init_lookup_table() {vis.clear();}
 40 int try_to_insert(int s) {
 41     int v = 0;
 42     for(int i=0;i<9;i++)
 43         v = v*10 + st[s][i];
 44     if(vis.count(v)) return 0;
 45     vis.insert(v);
 46     return 1;
 47 }
 48 */
 49 
 50 const int hashsize = 1000003;
 51 int head[hashsize],next[hashsize];
 52 void init_lookup_table() {memset(head,0,sizeof(head));}
 53 int hash(State& s) {
 54     int v;
 55     for(int i=0;i<9;i++)
 56         v = v*10 + s[i];
 57     return v % hashsize;
 58 }
 59 
 60 int try_to_insert(int s) {
 61     int h = hash(st[s]);
 62 
 63     int u = head[h];
 64     while(u) {
 65         if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
 66         u = next[u];
 67     }
 68     next[s] = head[h];
 69     head[h] = s;
 70     return 1;
 71 }
 72 
 73 
 74 
 75 int bfs() {
 76     init_lookup_table();
 77     int front=1,rear =2;
 78     while(front<rear) {
 79         State& s = st[front];
 80         if(memcmp(s,goal,sizeof(s))==0) return front;
 81 
 82         int z;
 83         for(z=0;z<9;z++)
 84             if(!s[z]) break;
 85 
 86         int x = z/3,y=z%3;
 87         for(int d=0;d<4;d++) {
 88             int newx = x + dx[d];
 89             int newy = y + dy[d];
 90 
 91             int newz = newx*3 + newy;
 92             if(newx>=0&&newx<3&&newy>=0&&newy<3) {
 93                 State& t = st[rear];
 94                 memcpy(&t,&s,sizeof(s));
 95 
 96                 t[newz] = s[z];
 97                 t[z] = s[newz];
 98                 dist[rear] = dist[front]+1;
 99                 if(try_to_insert(rear)) rear++;
100             }
101         }
102         front++;
103     }
104     return 0;
105 }
106 
107 int main()
108 {
109     freopen("in.txt","r",stdin);
110     for(int i=0;i<9;i++)
111         scanf("%d",&st[1][i]);
112 
113     for(int i=0;i<9;i++)
114         scanf("%d",&goal[i]);
115 
116     int ans = bfs();
117     if(ans>0)
118         printf("%d\n",dist[ans]);
119     else printf("-1\n");
120 
121     return 0;
122 }

Tip:hash的解决方案模板

int insert(/*结点*/ s) {
    int h = hash(str(s));    //hash值
    int u = head[h];        //这个hash值对应的最后一个*结点*，也可以说是表头或者表尾，我个人理解表尾
    while(u) {
         //依次检查 查到return 0;
          u = next[u];
    }
    next[s] = head[h];        // 结点 s 的下一个结点
      head[h] = s;
      return 1;
}