网站做报表,二级医院网站建设的方案,带有响应式的网站,营销型网站建设公司易网拓文章目录 题目描述基本思路实现代码 题目描述
在一个33的网格中#xff0c;1∼8这8个数字和一个x恰好不重不漏地分布在这33的网格中。例如#xff1a; 1 2 3 x 4 6 7 5 8 在游戏过程中#xff0c;可以把x与其上、下、左、右四个方向之一的数字交换#xff08;如果存在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)
{// 创建一个用于记录状态的队列并将开始状态放入队列中queuedigital_state states;states.push({start_state, 0});// 创建一个哈希集合存储已经出现过的状态并将开始状态放入该集合中unordered_setstring 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;
}
