八数码问题(一) 暴力BFS + STL
2024-08-30 03:20:34
八数码问题是一个经典的人工智能问题。具体问题不累述了。
思路:由于存在多组测试数据,可以考虑“打表法“。所谓打表法,即枚举所有的初始情况,记录其到达终点的路径。而在这个题目中,顺序打表会调用很多次BFS,所以我们采用逆序打表,只要调用一次BFS。
代码如下:
/*************map存路径,set判重,string存状态*****************/
/*********************暴力广搜 + STL **************************/
#include<stdio.h>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<sstream>
using namespace std;
map<string, string>slu;
set<string>visited;
int dir[][] = { {-,},{,},{,},{,-} };
string base = "udrl";
char input[];
struct node {
string sta;
string path;
int pos; //x所在的位置
node(string stas, string paths, int poss) {
sta = stas;
path = paths;
pos = poss;
}
};
bool check(int x, int y)
{
if (x >= && x < && y >= && y < )
return true;
else
return false;
}
void prv_bfs()
{
queue<node>q;
set<string>v;
q.push(node("12345678x", "", )); //从目标状态往回扩展
slu["12345678x"] = " ";
v.insert("12345678X");
while (!q.empty())
{
struct node h = q.front();
q.pop(); int a = h.pos / ;
int b = h.pos % ; //得到x的坐标
for (int i = ; i < ; i++)
{
int x = a + dir[i][];
int y = b + dir[i][];
int pos = * x + y;
if (!check(x, y))
continue;
swap(h.sta[h.pos], h.sta[pos]);
if (slu.find(h.sta) != slu.end())
{
swap(h.sta[h.pos], h.sta[pos]);
continue;
}
q.push(node(h.sta, h.path + base[i], pos));
slu[h.sta] = h.path + base[i];
v.insert(h.sta);
swap(h.sta[h.pos], h.sta[pos]);
}
}
}
int main()
{
prv_bfs();
while (~scanf("%s", input))
{
string line = "";
line = line + input[];
for (int i = ; i <= ; i++)
{
scanf("%s", input);
line = line + input[];
}
if (slu[line] == "") cout << "unsolvable" << endl;
else cout << slu[line] << endl;
} return ; }
当然,这一题还有很多很好的方法,我会慢慢补充。
新手入门,希望多多交流!
最新文章
- Ubuntu开发笔记
- struts2 Advanced Learning
- Django admin coercing to Unicode: need string or buffer, tuple found
- f.lux for Linux安装
- 实现Map-side Join和Reduce-side Join(转)
- 结合源码看nginx-1.4.0之nginx全局变量ngx_cycle初始化详解
- 【ERROR】---Error executing ";adb devices";:ADB server didn&#39;t ACK
- 【高级】C++中虚函数机制的实现原理
- NET .NET深入体验和实战精要
- Javascript--cookie创建与查看
- [Android] 对于com.google.gson.JsonElement的转义问题
- 工控随笔_08_西门子_Win10安装Step7.V5.6中文版授权管理器不能正常启动
- python-基于UDP通信的套接字,socketserver模块的使用
- java 原码反码及补码 总结
- web自动化测试---web页面元素的定位
- 记录一个简单的dbcp数据连接池
- (后端)出现org.hibernate.NonUniqueResultException的原因即解决办法
- Linux内核分析 读书笔记 (第三章)
- Python 新建程序
- TZOJ 1800 Martian Mining(二维dp)