8 puzzle问题 bfs,输出最少移动次数,输出最少移动次数下的移动路径,c++代码
时间: 2024-06-11 14:04:07 浏览: 11
以下是8 puzzle问题的BFS算法实现,包括输出最少移动次数和最少移动路径:
```c
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 3; // 3x3的棋盘
const int MAXM = 500000; // 最多状态数
struct node {
int state[MAXN][MAXN]; // 棋盘状态
int x, y; // 空格的坐标
int step; // 移动步数
int pre; // 前驱状态
char op; // 移动方式
} a[MAXM];
int head, tail;
int vis[MAXM];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; // 移动方向
int get_hash(node v) { // 哈希函数
int k = 0, sum = 0;
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
k++;
sum += k * v.state[i][j];
}
}
return sum % MAXM;
}
void init() { // 初始状态
node tmp;
int k = 0;
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
tmp.state[i][j] = ++k;
}
}
tmp.state[MAXN-1][MAXN-1] = 0;
tmp.x = MAXN-1;
tmp.y = MAXN-1;
tmp.step = 0;
tmp.pre = -1;
a[0] = tmp;
head = 0;
tail = 1;
vis[get_hash(tmp)] = 1;
}
void print_ans(int k) { // 输出答案
if (a[k].pre == -1) {
return;
}
print_ans(a[k].pre);
cout << a[k].op << endl;
}
void bfs() {
while (head < tail) {
node u = a[head++];
if (u.state[0][0] == 1 && u.state[0][1] == 2 && u.state[0][2] == 3 && u.state[1][0] == 4 && u.state[1][1] == 5 && u.state[1][2] == 6 && u.state[2][0] == 7 && u.state[2][1] == 8 && u.state[2][2] == 0) {
cout << u.step << endl;
print_ans(head-1);
return;
}
for (int i = 0; i < 4; i++) {
int nx = u.x + dir[i][0];
int ny = u.y + dir[i][1];
if (nx >= 0 && nx < MAXN && ny >= 0 && ny < MAXN) {
node v = u;
swap(v.state[u.x][u.y], v.state[nx][ny]);
v.x = nx;
v.y = ny;
v.step++;
v.pre = head - 1;
v.op = i == 0 ? 'd' : (i == 1 ? 'u' : (i == 2 ? 'r' : 'l'));
int h = get_hash(v);
if (!vis[h]) {
vis[h] = 1;
a[tail++] = v;
}
}
}
}
}
int main() {
init();
bfs();
return 0;
}
```
在该算法中,我们使用哈希表来存储已经访问过的状态,避免重复搜索。同时,我们使用结构体`node`来存储每个状态的信息,包括状态矩阵、空格坐标、移动步数、前驱状态和移动方式等。
在`bfs()`函数中,我们先判断当前状态是否为目标状态,如果是则输出答案并退出程序。否则,我们尝试四个方向的移动,并检查是否越界以及是否已经访问过。如果没有越界并且没有访问过,则将新状态加入队列中。最后,我们更新队列头指针`head`,并重复上述过程直到队列为空。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)