写一个解决华容道游戏的c++程序
时间: 2023-12-18 10:04:44 浏览: 149
好的,我很乐意为您解答。下面是一个简单的解决华容道游戏的 C++ 程序:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 3; // 华容道的大小
struct Status {
vector<vector<int>> board; // 华容道的当前状态
int step; // 走的步数
int zero_x, zero_y; // 数字 0 的位置
Status(vector<vector<int>>& b, int s, int zx, int zy) {
board = b;
step = s;
zero_x = zx;
zero_y = zy;
}
bool operator==(const Status& other) const {
return board == other.board;
}
};
// 判断当前状态是否是目标状态
bool is_target(Status& status) {
int target = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == N - 1 && j == N - 1) {
if (status.board[i][j] != 0) return false;
} else {
if (status.board[i][j] != target) return false;
target++;
}
}
}
return true;
}
// 判断当前状态是否合法
bool is_valid(Status& status, int new_x, int new_y) {
if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N)
return false;
if (abs(new_x - status.zero_x) + abs(new_y - status.zero_y) != 1)
return false;
return true;
}
// 移动数字
Status move(Status& status, int new_x, int new_y) {
vector<vector<int>> new_board = status.board;
swap(new_board[status.zero_x][status.zero_y], new_board[new_x][new_y]);
return Status(new_board, status.step + 1, new_x, new_y);
}
// 广度优先搜索
int bfs(Status& start) {
queue<Status> q;
q.push(start);
while (!q.empty()) {
Status now = q.front();
q.pop();
if (is_target(now)) {
return now.step;
}
int new_x, new_y;
new_x = now.zero_x - 1, new_y = now.zero_y;
if (is_valid(now, new_x, new_y)) {
Status next = move(now, new_x, new_y);
if (next == start) continue;
q.push(next);
}
new_x = now.zero_x + 1, new_y = now.zero_y;
if (is_valid(now, new_x, new_y)) {
Status next = move(now, new_x, new_y);
if (next == start) continue;
q.push(next);
}
new_x = now.zero_x, new_y = now.zero_y - 1;
if (is_valid(now, new_x, new_y)) {
Status next = move(now, new_x, new_y);
if (next == start) continue;
q.push(next);
}
new_x = now.zero_x, new_y = now.zero_y + 1;
if (is_valid(now, new_x, new_y)) {
Status next = move(now, new_x, new_y);
if (next == start) continue;
q.push(next);
}
}
return -1; // 无解
}
int main() {
vector<vector<int>> board(N, vector<int>(N));
int zero_x, zero_y;
cout << "请输入华容道的初始状态:" << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
if (board[i][j] == 0) {
zero_x = i;
zero_y = j;
}
}
}
Status start(board, 0, zero_x, zero_y);
int steps = bfs(start);
if (steps == -1) {
cout << "无解" << endl;
} else {
cout << "最少需要 " << steps << " 步" << endl;
}
return 0;
}
```
这个程序实现了一个广度优先搜索算法来解决华容道游戏。首先输入华容道的初始状态,然后使用一个 `Status` 结构体来存储当前的状态,包括当前的棋盘状态 `board`、走的步数 `step`,以及数字 0 的位置 `zero_x` 和 `zero_y`。然后使用 `is_target()` 函数来判断当前状态是否是目标状态,使用 `is_valid()` 函数判断当前状态下,能否移动某个数字到某个位置,使用 `move()` 函数来移动数字,最后使用 `bfs()` 函数来进行广度优先搜索,找到最少需要多少步可以从当前状态到达目标状态。
希望这个程序能够对您有所帮助!