八数码问题

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

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

 

这是一道比较经典的BFS题目，有回溯的思想（不是废话吗）

还是有一些点需要注意的：

1.BFS较多使用队列实现，因此在进行BFS时需要用到队列（蒟蒻的笔者目前所了解orz）

　那么说到队列，我就想到了孙悟空师徒四人一队。。咳咳，说到队列，就需要复习一下队列了。

　队列有静态以及STL实现，这题使用的是静态，其实用STL也是可以的，只不过笔者对于STL的队列操作不太熟练

　因此这次使用的是静态数组模拟队列

2.对于在搜索过程中记录中间状态，紫书上介绍了3种方法：

　①运用编码和解码函数

　②哈希表

　叁使用set STL

　下面给出的代码中有哈希的做法也有STL的做法，都是将0-8的位置转换成9位int数进行存储

3.memcpy和memcmp是<cstring>的对整块内存的复制和比较函数，比循环比较和复制快（要学习一个）

4.每次进行一个节点进行搜索时，需要先复制队头的排列情况到队尾，然后对队尾进行操作，操作完成后队尾向后移一位

 

 

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5  6 typedef int State[9]; 7 const int maxstate = 1000000; 8 State st[maxstate],goal; 9 int dist[maxstate];10 int fa[maxstate];11 12 const int dx[]={-1,1,0,0};13 const int dy[]={
      0,0,-1,1};14 //使用set STL15 set
           
             vis;16 void init_lookup_table(){vis.clear();}17 int try_to_insert(int s){18     int v=0;19     for(int i=0;i<9;i++) v=v*10+st[s][i];20     if(vis.count(v)) return 0;21     vis.insert(v);22     return 1;23 }24 25 //使用哈希26 /*const int hashsize = 1000003;27 int head[hashsize],Next[maxstate];28 void init_lookup_table(){memset(head,0,sizeof(head));}29 30 int hash(State& s){31     int v=0;32     for(int i=0;i<9;i++) v=v*10+s[i];33     return v % hashsize;34 }35 36 int try_to_insert(int s){37     int h = hash(st[s]);38     int u = head[h];39     while(u){40         if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;41         u=Next[u];42     }43     Next[s]=head[h];44     head[h]=s;45     return 1;46 }*/47 48 int bfs(){49     init_lookup_table();50     int front = 1,rear=2;51     while(front
            
             =0 && newx<3 && newy>=0 && newy<3){62                 State& t=st[rear];63                 memcpy(&t,&s,sizeof(s));64                 //memcpy(st[rear],st[front],sizeof(st[front]));65                 t[newz]=s[z];66                 t[z]=s[newz];67                 /*st[rear][newz]=st[front][z];68                 st[rear][z]=st[front][newz];*/69                 dist[rear] = dist[front]+1;70                 if(try_to_insert(rear)) rear++;71             }72         }73         front++;74     }75     return 0;76 }77 78 int main(){79     for(int i=0;i<9; i++) scanf("%d",&st[1][i]);80     for(int i=0;i<9; i++) scanf("%d",&goal[i]);81     int ans=bfs();82     if(ans>0) printf("%d\n",dist[ans]); else printf("-1\n");83     return 0;84 }
            
           
          
         
        

这道题还是很值得去琢磨的，里面涉及了较多的内容，如set STL，哈希，encoding和decoding等等，也是细节满满的一道题。

话说我为什么要在蓝桥杯比赛前两天突然发一篇题解呢？主要还是做题做累了（其实就是想偷懒），但又不能无所事事，就上来写了一下题解qwq

最后还是希望蓝桥杯rp++把