題目：

編號為1~8的8個正方形滑塊被擺成3行3列（有一個格子空留）。每次可以把與空格相鄰的滑塊（有公共邊才算相鄰）移到空格中，而它原來的位置就稱為了新的空格。給定初始局面和目標局面（用0表示空格格），你的任務是計算出最少的移動步數。如果無法達到目標局面，則輸-1.

輸入：
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
輸出：
31

分析與解：

無權圖上的最短路問題可以用BFS求解
涉及到hash內部鏈表的我抽空再補上（我數據結構還沒學好- - |）
先說一下大致思路

1.不斷移動空格的位置，并將移動的距離進行標記
2.移動過程中會有重復的情況出現，此時利用hash去重
3.一直移動到與目標局面相同，然后輸出移動的距離

我寫了十分詳盡的注釋，如下

#include<iostream> #include<cstdio> #include<cstring> #include<set> using namespace std; typedef int State[9];//定義狀態類型 /* typedef int a[10]; a b[10];//等同與int b[10][10]; */const int maxstate = 1000000; State st[maxstate], goal; //狀態數組 /* 等價于int st[maxstate][9] */ int dist[maxstate]; //距離數組const int dx[] = {-1, 1, 0 , 0}; const int dy[] = {0, 0, -1, 1};const int hashsize = 1000003; int head[hashsize], n[maxstate]; /*head[]:哈希表 */ void init_lookup_table() {memset(head, 0, sizeof(head)); } int Hash(State & s) {int v = 0;for (int i = 0; i < 9; i++) v = v * 10 + s[i];//把九個數字合成九位數 return v % hashsize; //hash函數值是不超過hash表的大小的非負整數 } int try_to_insert(int s)//尾部rear狀態 {int h = Hash(st[s]);//把第rear狀態下的st中的元素，轉換成一個數 （st[rear][i]->h) int u = head[h]; while (u) {if (memcmp(st[u], st[s], sizeof(st[s])) == 0) return 0;//如果之前訪問過該結點，那么直接退出 u = n[u]; //順著鏈表繼續找 }n[s] = head[h];//插入鏈表中 head[h] = s;return 1; }int bfs() {init_lookup_table();//初始化查找表 int fron = 1, rear = 2;//fron,當前狀態下標，rear，下一步狀態下標 while (fron < rear) {State & s = st[fron]; //此時s引用st[fron]，s是一維數組，里面有九個元素 if (memcmp(goal, s, sizeof(s)) == 0) return fron;//如果找到目標狀態，返回目標狀態在st數組下標 int z;for (z = 0; z < 9; z++) if (!s[z]) break;//找0的位置int x = z/3, y = z%3; //0的行列編號（0-2） for (int i = 0; i < 4; i++) { //上下左右移動零的位置 int newx = x + dx[i]; int newy = y + dy[i];int newz = newx*3 + newy; //newz是z移動之后的下標，t[newz]=0.t[z]=s[newz] if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {//如果移動合法 State & t = st[rear]; //開一個新的狀態 memcpy(&t, &s, sizeof(s));//把之前的狀態（那九個元素）先填到新狀態里 t[newz] = s[z]; //之前狀態中，下標為z的是零，在新狀態下，為零的下標變成newz t[z] = s[newz]; dist[rear] = dist[fron] + 1; //更新節點的距離值 （dist【rear】：走到rear狀態時的走的步驟個數） if (try_to_insert(rear)) rear++;//如果成功插入查找表，修改隊尾指針（也就是從這個支路向外發散） }}fron++;//擴展完畢修改隊首指針，也就是從下一個位置開始找 }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();// 返回目標狀態在st數組下標 if (ans > 0) printf("%d\n", dist[ans]);else printf("-1\n");return 0; }

總結

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

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