?

題目描述：

?

代碼如下：

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #define N 1000000 5 #define HN 1000003 6 #define LEN 9 7 8 int head[HN],next[N]; 9 int st[N][LEN], goal[LEN]; 10 int dis[N]; //記錄步數 11 12 int Hash(int *st)//獲取本次排列組合的哈希值 13 { 14 int i,v; 15 v = 0; 16 for (i=0 ; i<LEN ; i++)//得到一個LEN長度數值：v 17 { 18 v = v*10 + st[i]; 19 } 20 return v%HN;//得到對應哈希值 21 } 22 23 24 // 功能：對本次的排列組合，若不在哈希表中，則在哈希表中進行鍵值映射 25 int try_insert(int rear)//rear：本次組合的編號 26 { 27 int h = Hash(st[rear]); //獲得本次排列組合對應的哈希值 28 int u = head[h]; //根據哈希值，獲得哈希表中對應的鍵(key),若沒有則為0 29 30 while (u)//當上一步有拿到鍵(key),查找對應的值(value->排列組合), 31 { 32 if (memcmp(st[u],st[rear],sizeof(st[0]))==0)//存在相同的值(value->排列組合) 33 return 0; //本次值(value->排列組合)將不記錄，退出 34 u = next[u]; //當前鍵(key)還有其他值，遍歷獲得其他值(value->排列組合) 35 } 36 37 //當前值(value->排列組合)不在哈希表中，將進行記錄 38 next[rear] = head[h]; //當前鍵(key)的記錄是否有其他值，若本身為新組合，為0；若為存在組合，則為其上一個編號(相同組合) 39 head[h] = rear; //哈希表中對應的鍵(key)，更新為本次組合編號(rear) 40 return 1; 41 } 42 43 int bfs() 44 { 45 int d; 46 int x,y,z,nx,ny,nz; 47 int fron = 1,rear = 2; //fron：當前排列組合；rear：移動后的排列組合 48 const int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0},}; 49 50 memset(head,0,sizeof(head)); 51 while (fron < rear) 52 { 53 if (memcmp(goal,st[fron],sizeof(st[0]))==0)//當前排列組合為目標排列組合 54 return fron; 55 56 for (z=0 ; z<LEN ; z++) 57 { 58 if (st[fron][z]==0)//0即為對應的'.' 59 break; 60 } 61 62 x = z/3,y = z%3;//獲得'.'的坐標 63 for (d=0 ; d<4 ; d++) 64 { 65 nx = x+dir[d][0]; 66 ny = y+dir[d][1]; 67 if (nx>=0 && nx<3 && ny>=0 && ny<3) 68 { 69 nz = 3*nx+ny;//'.'將要移動的下一步位置 70 71 memcpy(&st[rear],&st[fron],sizeof(st[0])); 72 st[rear][nz] = st[fron][z]; 73 st[rear][z] = st[fron][nz]; 74 75 dis[rear] = dis[fron]+1;//記錄步數 76 if (try_insert(rear))//對新排列組合進行查找 77 rear ++;//進隊列 78 } 79 } 80 fron ++;//出隊列 81 } 82 83 return 0; 84 } 85 86 int main(void) 87 { 88 int i,ans; 89 char s1[LEN+1],s2[LEN+1]; 90 memset(dis,0,sizeof(dis)); 91 scanf("%s%s",&s1,&s2); 92 93 for (i=0 ; i<LEN ; i++)//將'.'轉換為0，便于計算哈希值 94 { 95 if (s1[i]=='.') 96 st[1][i] = 0; 97 else 98 st[1][i] = s1[i]-'0'; 99 100 if (s2[i]=='.') 101 goal[i] = 0; 102 else 103 goal[i] = s2[i]-'0'; 104 } 105 106 ans = bfs(); 107 if (ans > 0) 108 printf("%d",dis[ans]); 109 else 110 puts("-1"); 111 112 return 0; 113 } C解法

?

?

解題思路：

?本題要求最少步數轉換成目標組合，廣度優先遍歷(BFS)可滿足要求

每次對新組合進行檢查時，需要較高的檢索效率，

1.使用map或者set做檢索時，其對應的檢索效率低，超時不能滿足題目需求；

2.對組合進行哈希判重，大大提高了檢索效率；

?

關于本題的哈希判重，參考了：

https://blog.csdn.net/hao_zong_yin/article/details/62419919

https://www.cnblogs.com/acxblog/p/7253477.html

?

哈希判重，利用鍵-值映射，有效提高了搜索的效率；

1.建立鍵(key)表，head[NH]，需初始化；建立值(value)表，next[N]；

2.BFS搜索新組合，通過向不同方向移動?' . ' (0)? 得到新的組合；

3.根據新組合，計算對應的哈希值；

4.根據哈希值，進行檢索決定是否添加新的排列組合

　　4.1.插入的組合存在

?　　4.2.插入的組合不存在

?

5.若有新組合添加，隊列+1（rear+1）

6.每次出列(fron+1)，檢查是否為目標組合

7.若fron > rear，則不存在方案，輸出-1

?

轉載于:https://www.cnblogs.com/mind000761/p/10572127.html

總結

以上是生活随笔為你收集整理的[蓝桥杯]PREV-19.历届试题_九宫重排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。