8 puzzle问题 bfs,输入初始状态和最终状态,输出最少移动次数,输出最少移动次数下的移动路径,c++代码
时间: 2024-04-29 14:25:51 浏览: 24
以下是八数码问题的BFS算法的C++实现:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 3; // 3*3的方格
const int SIZE = N * N; // 每个状态的大小
const int dx[4] = {-1, 0, 1, 0}; // 四个方向的x坐标变化
const int dy[4] = {0, 1, 0, -1}; // 四个方向的y坐标变化
struct State {
int board[N][N]; // 当前状态的棋盘
int zeroX, zeroY; // 0的位置
int steps; // 走到当前状态的步数
State() {
steps = 0;
zeroX = zeroY = -1;
memset(board, 0, sizeof(board));
} // 初始化
bool operator==(const State &that) const { // 判断两个状态是否相等
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (board[i][j] != that.board[i][j])
return false;
return true;
}
bool operator!=(const State &that) const {
return !(*this == that);
}
};
struct Hash {
size_t operator()(const State &state) const { // 哈希函数
size_t hash = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
hash = hash * 10 + state.board[i][j];
return hash;
}
};
void printPath(const vector<State> &path) { // 输出路径
for (const auto &state : path) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << state.board[i][j] << " ";
cout << endl;
}
cout << endl;
}
}
int bfs(const State &start, const State &end) {
queue<State> q;
unordered_map<State, int, Hash> dist; // 记录状态到起点的距离
unordered_map<State, State, Hash> parent; // 记录状态的父亲
State curr = start;
dist[curr] = 0; // 起点到起点的距离为0
q.push(curr);
while (!q.empty()) {
curr = q.front();
q.pop();
if (curr == end) { // 找到最终状态
vector<State> path;
while (curr != start) {
path.push_back(curr);
curr = parent[curr];
}
path.push_back(start);
reverse(path.begin(), path.end()); // 反转路径
printPath(path);
return dist[end]; // 返回最短距离
}
int x = curr.zeroX, y = curr.zeroY;
for (int i = 0; i < 4; i++) { // 四个方向扩展
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) { // 判断是否越界
State next = curr;
swap(next.board[x][y], next.board[nx][ny]); // 交换0和相邻位置的数
next.zeroX = nx, next.zeroY = ny; // 更新0的位置
if (dist.count(next) == 0) { // 判断是否已经扩展过
dist[next] = dist[curr] + 1;
parent[next] = curr;
q.push(next);
}
}
}
}
return -1; // 无法到达最终状态
}
int main() {
State start, end;
cout << "请输入初始状态(共" << SIZE << "个数):" << endl;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
cin >> start.board[i][j];
if (start.board[i][j] == 0)
start.zeroX = i, start.zeroY = j;
}
cout << "请输入最终状态(共" << SIZE << "个数):" << endl;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
cin >> end.board[i][j];
if (end.board[i][j] == 0)
end.zeroX = i, end.zeroY = j;
}
int steps = bfs(start, end);
if (steps == -1)
cout << "无法到达最终状态" << endl;
else
cout << "最少移动次数为:" << steps << endl;
return 0;
}
```
该算法使用了哈希表来记录状态,从而避免了重复计算。同时,使用了unordered_map来记录状态到起点的距离和状态的父亲,从而在找到最终状态后可以输出路径。
相关推荐
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)