题目描述
- 在一个
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;
}