Acwing八数码
2024-09-06 00:13:35
此题用\(bfs\)
首先我们可以定义两个重要的数组
\(unordered\_map<string,int> d\)表示\(string\)距离\(start\)的交换次数
\(queue<string> q\)广搜数组
然后我们初始化后进行三个操作
1.将一维的坐标转化为二维的坐标(\(x=k/3,y=k \%3\)k表示一维中的位置)
2.进行向4个方向搜索,交换一次,如果没有变成过这样的状态,那么就更新。
3.恢复状态。
当变为目标状态"12345678x"时,输出\(d['12345678x']\)即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int bfs(string start)
{
string end = "12345678x";
unordered_map<string,int> d;//记录状态距离
queue<string> q;//队列
q.push(start);
d[start] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size())
{
auto t = q.front();
q.pop();
int dis = d[t];
if(t == end) return dis;
//状态转移
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
swap(t[k],t[a * 3 + b]);
if(!d.count(t))
{
d[t] = dis + 1;
q.push(t);
}
swap(t[k],t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
string start;
for (int i = 0; i < 9; i ++ )
{
char ch;
cin >> ch;
start += ch;
}
cout << bfs(start) << endl;
return 0;
}
最新文章
- 基于Redis、Storm的实时数据查询实践
- [Android Pro] android 4.4 Android原生权限管理:AppOps
- DDD基本概念
- scjp考试准备 - 6 - 父类构造器的引用
- wpa_supplicant 连接成功后,如何配置wlan0与br0 协调上网
- javascript操作Math对象的方法总结
- 全面认识网络诊断命令功能与参数——netsh diagnostic命令
- ManagedPipelineHandler IIS
- Android上下左右滑动,显示底层布局
- Mac 下卸载 Graphviz
- 免费开源的boostrap模板
- Too many open files问题解决
- ES6系列之解构
- 免费的剪贴板工具Ditto安装与使用
- Confluence 6 创建一个项目空间
- (转)python-user-agents
- Easyradius对接WayOs维盟小区版XQ教程
- Window 常用系统变量
- Telnet远程重启路由器TP-LINK
- Linux工作管理