八数码问题是一个经典的人工智能问题。具体问题不累述了。

思路:由于存在多组测试数据,可以考虑“打表法“。所谓打表法,即枚举所有的初始情况,记录其到达终点的路径。而在这个题目中,顺序打表会调用很多次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 ; }

当然,这一题还有很多很好的方法,我会慢慢补充。

新手入门,希望多多交流!

最新文章

  1. Ubuntu开发笔记
  2. struts2 Advanced Learning
  3. Django admin coercing to Unicode: need string or buffer, tuple found
  4. f.lux for Linux安装
  5. 实现Map-side Join和Reduce-side Join(转)
  6. 结合源码看nginx-1.4.0之nginx全局变量ngx_cycle初始化详解
  7. 【ERROR】---Error executing &quot;adb devices&quot;:ADB server didn&#39;t ACK
  8. 【高级】C++中虚函数机制的实现原理
  9. NET .NET深入体验和实战精要
  10. Javascript--cookie创建与查看
  11. [Android] 对于com.google.gson.JsonElement的转义问题
  12. 工控随笔_08_西门子_Win10安装Step7.V5.6中文版授权管理器不能正常启动
  13. python-基于UDP通信的套接字,socketserver模块的使用
  14. java 原码反码及补码 总结
  15. web自动化测试---web页面元素的定位
  16. 记录一个简单的dbcp数据连接池
  17. (后端)出现org.hibernate.NonUniqueResultException的原因即解决办法
  18. Linux内核分析 读书笔记 (第三章)
  19. Python 新建程序
  20. TZOJ 1800 Martian Mining(二维dp)

热门文章

  1. SetCapture到底是什么?
  2. POJ - 2349 ZOJ - 1914 Arctic Network 贪心+Kru
  3. Coreseek 安装问题
  4. sql生成一个唯一标示
  5. 数据库路由中间件MyCat - 源代码篇(5)
  6. 数据库路由中间件MyCat - 源代码篇(3)
  7. Weekly Contest 112
  8. css布局知识点汇总
  9. 线程池(2)Executors.newFixedThreadPool
  10. Jexus 5.8.2