文章目录
题目描述
- 在一个
3×3的网格中，1∼8这8个数字和一个x恰好不重不漏地分布在这3×3的网格中。 - 例如：
1 2 3
x 4 6
7 5 8
- 在游戏过程中，可以把
x与其上、下、左、右四个方向之一的数字交换（如果存在）。 - 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
- 例如，示例中图形就可以通过让
x先后与右、下、右三个方向的数字交换成功得到正确排列。 - 现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
- 输入占一行，将
3×3的初始网格描绘出来。 - 例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
- 则输入为：
1 2 3 x 4 6 7 5 8
输出格式
- 输出占一行，包含一个整数，表示最少交换次数。
- 如果不存在解决方案，则输出
−1。
基本思路
- 本题可以基于广度优先算法进行求解。对于数码的每一种摆放，我们可以将其视为一种状态，对应于一个图中的某一个结点。通过
x和相邻元素的交换可以转移到另一个结点。那么，现在问题就变为，如何从开始状态的结点走到表示最终状态的结点。 - 由于每一次x与相邻元素发生交换后的状态是可以枚举出来的，因此可以采用广度优先搜索算法进行求解。每找出一种新的状态，就记录从初始状态到当前状态所需的转换次数。
实现代码
#include <iostream>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;
// 用一个结构体来定义每一个状态的数码排列和离初始状态的距离
struct digital_state
{
string current;
int distance;
};
const string end_state = "12345678x";
int bfs(const string& start_state)
{
// 创建一个用于记录状态的队列，并将开始状态放入队列中
queue<digital_state> states;
states.push({start_state, 0});
// 创建一个哈希集合，存储已经出现过的状态，并将开始状态放入该集合中
unordered_set<string> finded;
finded.insert(start_state);
// 通过循环找出从开始状态开始的所有不同状态，并计算其距离
while(states.empty() == false)
{
// 取出队首元素
digital_state temp = states.front();
states.pop();
// 如果队首元素对应的状态就是最终状态，则将该状态的距离返回
if(temp.current == end_state) return temp.distance;
// 队首元素对应的状态不是最终状态，则查找该状态的下一个可能状态
else
{
// 首先确认字符x所在的位置，并将其转换为行和列
int x_position = temp.current.find('x');
int x_row = x_position / 3, x_col = x_position % 3;
//判定x是否可以向上移动，如果可以则找到移动后的状态
if(x_row >= 1)
{
string temp_state = temp.current;
swap(temp_state[x_position], temp_state[x_position - 3]);
// 如果该状态还未出现过，则记录该状态
if(finded.find(temp_state) == finded.end())
{
// 将该状态放入集合中
finded.insert(temp_state);
// 将该状态放入队列中
states.push({temp_state, temp.distance + 1});
}
}
//判定x是否可以向下移动，如果可以则找到移动后的状态
if(x_row <= 1)
{
string temp_state = temp.current;
swap(temp_state[x_position], temp_state[x_position + 3]);
// 如果该状态还未出现过，则记录该状态
if(finded.find(temp_state) == finded.end())
{
// 将该状态放入集合中
finded.insert(temp_state);
// 将该状态放入队列中
states.push({temp_state, temp.distance + 1});
}
}
//判定x是否可以向左移动，如果可以则找到移动后的状态
if(x_col >= 1)
{
string temp_state = temp.current;
swap(temp_state[x_position], temp_state[x_position - 1]);
// 如果该状态还未出现过，则记录该状态
if(finded.find(temp_state) == finded.end())
{
// 将该状态放入集合中
finded.insert(temp_state);
// 将该状态放入队列中
states.push({temp_state, temp.distance + 1});
}
}
//判定x是否可以向右移动，如果可以则找到移动后的状态
if(x_col <= 1)
{
string temp_state = temp.current;
swap(temp_state[x_position], temp_state[x_position + 1]);
// 如果该状态还未出现过，则记录该状态
if(finded.find(temp_state) == finded.end())
{
// 将该状态放入集合中
finded.insert(temp_state);
// 将该状态放入队列中
states.push({temp_state, temp.distance + 1});
}
}
}
}
// 不存在解决方案的情况
return -1;
}
int main(void)
{
string start_state;
for(int i = 0; i < 9; ++ i)
{
char c;
cin >> c;
start_state.push_back(c);
}
cout << bfs(start_state);
return 0;
}