#include #include #include<stdio.h> #include <stdlib.h> typedef int State[9];//定义状态类型 const int maxstate = 1000000; State st[maxstate], goal;//状态数组，所有状态都保存在这里 int dist[maxstate];//距离数组 int fa[maxstate];//链表保存路径 const int hashsize = 1000003; int head[hashsize]; int next[maxstate]; const int dx[] = { -1, 1, 0, 0 }; const int dy[] = { 0, 0, -1, 1 };//控制分别向上下左右移动 //BFS,返回目标状态在st数组下标
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) { int h = hash(st[s]); int u = head[h]; while (u) {//从表头开始查找链表 if (memcmp(st[u], st[s], sizeof(st[s])) == 0) return 0;//找到了说明，已经存在，不能插入 u = next[u]; } next[s] = head[h];//如果两个节点的hash值相同，但是代表的状态不同插入到链表中(头插法) head[h] = s;//链表头节点置为s return 1;
}
int bfs() { init_lookup_table(); int front = 1, rear = 2;//不使用下标0 fa[front] = -1; while (front < rear) { State& s = st[front];//得到队头的九个数组成的数组； if (memcmp(goal, s, sizeof(s)) == 0) return front;//找到目标状态，成功返回 int z; for (z = 0; z < 9; z++) { if (!s[z]) break;//找到"0"的位置 } int x = z / 3; int y = z % 3; for (int d = 0; d < 4; d++) {//空格四个方向移动 int newx = x + dx[d]; int newy = y + dy[d]; int newz = newx * 3 + newy; if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) { //如果移动合法 State& t = st[rear];//得到队尾的九个数 memcpy(&t, &s, sizeof(s));//将s复制到t t[newz] = s[z]; t[z] = s[newz];//交换空格的位置 dist[rear] = dist[front] + 1;//更新节点的距离值 fa[rear] = front;//插入链表头部，记录路径 if (try_to_insert(rear))//成功插入表，更新队尾指针 rear++; } } front++; } return 0;//失败 }
int main() { printf(“请输入节点的起始状态:\n”); for (int i = 0; i < 9; i++) { scanf_s("%d", &st[1][i]); } printf(“请输入节点的目标状态:\n”); for (int i = 0; i < 9; i++) { scanf_s("%d", &goal[i]); } int ans = bfs();//返回目标状态的下标 if (ans > 0) printf(“一共需要移动%d次\n”, dist[ans]); else printf(“不能到达目标状态\n”); int head = ans; while (head != -1) {//打印路径 for (int i = 0; i < 9; i++) { printf("%d “, st[head][i]); if ((i + 1) % 3 == 0) printf(”\n"); } printf("\n"); head = fa[head];
} system("pause"); return 0;}
