任务1：
思路：使用广度优先搜索算法，从初始棋局开始，每次将相邻的数字方块移动到空格中，并保存这个状态，直到达到目标棋局。
具体实现：
- 定义一个结构体，表示每个状态，包括当前棋局、空格的位置和已经移动的步数。
struct State {
int board[3][3]; // 棋局
int empty_x, empty_y; // 空格位置
int steps; // 移动步数
};
- 定义一个队列，保存所有状态。
queue q;
- 定义一个标记数组，标记每个状态是否已经出现过。
bool vis[3][3][3][3][3][3][3][3];
- 将初始状态加入队列中。
State start;
start.board = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} };
start.empty_x = 1;
start.empty_y = 2;
start.steps = 0;
q.push(start);
vis[2][8][3][1][6][4][7][0][5] = true;
- 在队列中循环，直到找到目标状态。
while (!q.empty()) {
State cur = q.front();
q.pop();
if (cur.board == target.board) {
cout << cur.steps << endl;
break;
}
// 将相邻的数字方块移动到空格中
for (int i = 0; i < 4; i++) {
int nx = cur.empty_x + dx[i], ny = cur.empty_y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
State next = cur;
swap(next.board[cur.empty_x][cur.empty_y], next.board[nx][ny]);
next.empty_x = nx;
next.empty_y = ny;
next.steps++;
// 如果这个状态没有出现过，就加入队列中
if (!vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]]) {
q.push(next);
vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]] = true;
}
}
}
}
完整代码：
#include
#include
using namespace std;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
struct State {
int board[3][3];
int empty_x, empty_y;
int steps;
};
int main() {
State start, target;
start.board = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} };
start.empty_x = 1;
start.empty_y = 2;
start.steps = 0;
target.board = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} };
queue q;
q.push(start);
bool vis[3][3][3][3][3][3][3][3][3] = {false};
vis[2][8][3][1][6][4][7][0][5] = true;
while (!q.empty()) {
State cur = q.front();
q.pop();
if (cur.board == target.board) {
cout << cur.steps << endl;
break;
}
for (int i = 0; i < 4; i++) {
int nx = cur.empty_x + dx[i], ny = cur.empty_y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
State next = cur;
swap(next.board[cur.empty_x][cur.empty_y], next.board[nx][ny]);
next.empty_x = nx;
next.empty_y = ny;
next.steps++;
if (!vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]]) {
q.push(next);
vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]] = true;
}
}
}
}
return 0;
}
任务2：
思路：在任务1的基础上，记录每个状态是从哪个状态转移过来的，最终可以通过逆推出移动序列。
具体实现：
- 在结构体中新增一个成员变量，表示上一个状态的索引。
struct State {
int board[3][3];
int empty_x, empty_y;
int steps;
int prev; // 上一个状态的索引
};
- 在加入队列时，记录当前状态的索引。
vector states; // 保存所有状态
start.prev = -1; // 初始状态的上一个状态为-1
states.push_back(start);
int cur_index = 0;
- 在每次找到新状态时，记录这个状态是从哪个状态转移过来的，并将这个状态加入队列中。
next.prev = cur_index;
states.push_back(next);
q.push(next);
- 在找到目标状态后，从目标状态开始逆推，直到回到初始状态，记录每个状态的移动方向。
vector directions; // 保存移动方向
int index = states.size() - 1; // 从目标状态开始逆推
while (index != 0) { // 回到初始状态
int prev_index = states[index].prev;
int x1 = states[prev_index].empty_x, y1 = states[prev_index].empty_y;
int x2 = states[index].empty_x, y2 = states[index].empty_y;
if (x1 == x2) {
if (y1 < y2) {
directions.push_back(0); // 向右移动
} else {
directions.push_back(1); // 向左移动
}
} else {
if (x1 < x2) {
directions.push_back(2); // 向下移动
} else {
directions.push_back(3); // 向上移动
}
}
index = prev_index;
}
reverse(directions.begin(), directions.end()); // 反转方向
完整代码：
#include
#include
#include
#include
using namespace std;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
struct State {
int board[3][3];
int empty_x, empty_y;
int steps;
int prev;
};
int main() {
State start, target;
start.board = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} };
start.empty_x = 1;
start.empty_y = 2;
start.steps = 0;
target.board = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} };
vector states;
start.prev = -1;
states.push_back(start);
int cur_index = 0;
queue q;
q.push(start);
bool vis[3][3][3][3][3][3][3][3][3] = {false};
vis[2][8][3][1][6][4][7][0][5] = true;
while (!q.empty()) {
State cur = q.front();
q.pop();
if (cur.board == target.board) {
cout << cur.steps << endl;
int index = states.size() - 1;
vector directions;
while (index != 0) {
int prev_index = states[index].prev;
int x1 = states[prev_index].empty_x, y1 = states[prev_index].empty_y;
int x2 = states[index].empty_x, y2 = states[index].empty_y;
if (x1 == x2) {
if (y1 < y2) {
directions.push_back(0);
} else {
directions.push_back(1);
}
} else {
if (x1 < x2) {
directions.push_back(2);
} else {
directions.push_back(3);
}
}
index = prev_index;
}
reverse(directions.begin(), directions.end());
for (int d : directions) {
if (d == 0) {
cout << "R";
} else if (d == 1) {
cout << "L";
} else if (d == 2) {
cout << "D";
} else {
cout << "U";
}
}
cout << endl;
break;
}
for (int i = 0; i < 4; i++) {
int nx = cur.empty_x + dx[i], ny = cur.empty_y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
State next = cur;
swap(next.board[cur.empty_x][cur.empty_y], next.board[nx][ny]);
next.empty_x = nx;
next.empty_y = ny;
next.steps++;
if (!vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]]) {
next.prev = cur_index;
states.push_back(next);
q.push(next);
vis[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]][next.board[2][0]][next.board[2][1]][next.board[2][2]] = true;
}
}
}
cur_index++;
}
return 0;
}
