題目：編號為1~8的8個正方形滑塊被擺成3行3列（有一個格子留空）。把一種狀態變成另一種狀態最少移動多少步，到達不了，就輸出-1。

2	6	4
1	3	7
?	5	8

8	1	5
7	3	6
4	?	2

?

?

?

?

分析：題目就是一個bfs最短路徑問題，關鍵是如何判斷當前狀態是尋找過的。作者給了3種方法，我總結一下。

第一種：把0~8的所有可能的排列組合和0~362879（全排列的數目）對應起來，說起來這種方法真是精妙，看你怎么編碼，最能激發想象力。作者編碼如下：

int vis[362880],fact[9]; void init_lookup_table(){fact[0]=1;for(int I=1;i<9;i++)fact[I]=fact[I-1]*I; }

?fact[1]=1*1!;

fact[2]=2*fact[1]=2*1*1;

fact[3]=3*fact[2]=3*2*1;

fact[4]=4*fact[3]=4*3*2*1;

...

fact[8]=8!;

int try_to_insert(int s){int code=0;for(int I=0;i<9;i++){int cnt=0;for(int j=I+1;j<9;j++){if(st[s][j]<st[s][I]){cnt++;}}code+=fact[8-i]*cnt;}if(vis[code])return 0;return vis[code]=1; }

這里利用了排列組合每次變換后的每個位置上的值的后面所有值小于它本身的有多少個。假設當前排列是8 7 6 5 4 3 2 1 0。然后第一個后面所有元素小于它有8個，fact[8-0]=8!，8*8！，9！=9*8！，還剩下8！。再看7，fact[8-1]=7!，7*7！，8！=8*7！，還剩下7！。同樣6還剩下6！，5還剩下5!，4還剩下4!，3還剩下3！，2還剩下2！。1就是0，還剩下1個。一共就是362879就是最大下標。

每一種排列都是唯一的，因為即使cnt有可能一樣，但是fact的值是不一樣的。數學真是有趣，這都能推出來，美！

這種排序方法也有缺陷，一是數量大就不適用，二是比較難想。

第二種：

哈希編碼，映射，先聲明這題沒有沖突，是完美的哈希編碼。

以 12 8 4 6 23 45為例，共6個可以開長度為6的數組。映射到表中12%6=0；8%6=2；4%6=4；6%6=0；23%6=5；45%6=3；

0	1	2	3	4	5
12	6	8	45	4	23

發現有沖突向后一位，位數放入偏移數組，但是這題沒有沖突，作者神仙。 解題思路就是將排列組合的9個數組合起來變成一個數，一共有362880個組合，就有362880個數，開長度為1000003的數組。

代碼部分：

const int hashsize = 1000003; int head[hashsize], nexts[maxstate]; void init_lookup_table() {memset(head, 0, sizeof(head)); } int hashs(State& s) {int v = 0;for (int i = 0; i < 9; i++)v = v * 10 + s[i];//將組合變成一個9位數return v % hashsize; } int try_to_insert(int s) {int h = hashs(st[s]);int u = head[h];while (u) {if (memcmp(st[u], st[s], sizeof(st[s])) == 0)return 0;u = nexts[u];}nexts[s] = head[h];head[h] = s;return 1; }

?第三種：

終于到了不用動腦子的方法了。

建立集合用集合判重，具體看代碼。

set<int>vis; void init_lookup_table(){vis.clear();} int try_to_insert(int s){int v=0;for(int I=0;i<9;i++)v=v*10+st[s][I];if(vis.count(v))return 0;vis.insert(v);return 1; }

最后一種雖然簡單，但是效率相對前面兩種來說就顯得低很多。

?

最后?

附上回歸正題，八數碼代碼：

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include<iostream> using namespace std; const int maxstate = 1000000; typedef int State[9]; State st[100000],goal; int dist[maxstate];//距離數組 //如果需要打印，可在這里加一個“父親編號”數組 int fa[maxstate] const int dx[] = { -1,1,0,0 }; const int dy[] = { 0,0,-1,1 }; const int hashsize = 1000003; int head[hashsize], nexts[maxstate]; void init_lookup_table() {memset(head, 0, sizeof(head)); } int hashs(State& s) {int v = 0;for (int i = 0; i < 9; i++)v = v * 10 + s[i];//將組合變成一個9位數return v % hashsize; } int try_to_insert(int s) {int h = hashs(st[s]);int u = head[h];while (u) {if (memcmp(st[u], st[s], sizeof(st[s])) == 0)return 0;u = nexts[u];}nexts[s] = head[h];head[h] = s;return 1; } int bfs() {init_lookup_table();int front = 1, rear = 2;while (front < rear) {State& s = st[front];if (memcmp(s, goal, sizeof(s)) == 0)return front;//找到目標狀態，成功返回int z;for ( z = 0; z < 9; z++)if (!s[z])break;//找到空位int x = z / 3, y = z % 3;//計算空位坐標for (int i = 0; i < 4; i++) {int newx = x + dx[i];int newy = y + dy[i];int newz = newx * 3 + newy;//投影到一維數組if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {//判斷是否超界State& t = st[rear];memcpy(&t, &s, sizeof(s));t[newz] = s[z];t[z] = s[newz];//位置對換dist[rear] = dist[front] + 1;//計算步數if (try_to_insert(rear)) {//判重，如果找不到，就移動隊尾指針，也就是插入操作rear++;}}}front++;//后移，也就是出隊}return 0;//失敗 } int main() {for (int i = 0; i < 9; i++)scanf("%d", &st[1][i]);for (int i = 0; i < 9; i++)scanf("%d", &goal[i]);int ans = bfs();if (ans > 0)printf("%d\n", dist[ans]);else printf("-1\n");system("pause");return 0; }

?

總結

以上是生活随笔為你收集整理的路劲寻找-八数码问题（判重）的全部內容，希望文章能夠幫你解決所遇到的問題。

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