/*这道题a的蛋疼无比啊。学了hash技术和cantor展开。具体的解释都在注释下。不多说了。好题啊!*/
#include<cstdio>
#include<set>
#include <cstring>
using namespace std;
typedef int State[9];
const int MAXSTATE = 1000000;
State st[MAXSTATE], goal;
int dist[MAXSTATE];
const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE], next[MAXSTATE];
void init_lookup_table() { memset(head, 0, sizeof(head)); }
int hash(State& s) {
int v = 0;
for(int i = 0; i < 9; i++) v = v * 10 + s[i];
return v % MAXHASHSIZE;
}
int try_to_insert(int s) {
int h = hash(st[s]);
int u = head[h];
while(u) {
if(memcmp(st[u], st[s], sizeof(st[s])) == 0) return 0;
u = next[u];
}
next[s] = head[h];
head[h] = s;
return 1;
}
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int bfs() {
init_lookup_table();
int front = 1, rear = 2;
while(front < rear) {
State& s = st[front];
if(memcmp(goal, s, sizeof(s)) == 0) return front;
int z;
for(z = 0; z < 9; z++) if(!s[z]) break;
int x = z/3, y = z%3;
for(int d = 0; d < 4; d++) {
int newx = x + dx[d];
int newy = y + dy[d];
int newz = newx * 3 + newy;
if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
State& t = st[rear];
memcpy(&t, &s, sizeof(s));
t[newz] = s[z];
t[z] = s[newz];
dist[rear] = dist[front] + 1;
if(try_to_insert(rear)) rear++;
}
}
front++;
}
return 0;
}
int main() {
int t;
scanf("%d",&t);
while(t--)
{
getchar();
for(int i=0; i<9; i++)
scanf("%d",&st[1][i]);
for(int i=0; i<9; i++)
scanf("%d",&goal[i]);
int ans=bfs();
if(ans==0) printf("-1\n");
else printf("%d\n",dist[ans]);
}
return 0;
}
分享到:
相关推荐
在图1,3*3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空。 如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态(图1左)到目标状态(图1右)。 可自行设计初始...
本C++代码解决了八数码问题,采用深度优先,广度优先和A*算法实现,基于visual studio 2017
解决八数码(N=3)以及十五数码(N=4)等人工智能数码,使用宽度搜索算法
基于C++的 BFS算法解决8数码问题 没有做界面 直接是输出步骤 算法是亮点
使用python实现八数码问题的宽度优先搜索
人工只能作业,利用python实现深度优先搜索解决八数码问题,测试通过,
该资源包用了BFS,DFS,一直代价,贪婪,A*算法求解八数码难题。其中包括一个设计UI界面的代码,实现了问题解决过程的可视化。
人工智能作业,其算法进行了优化,解决速度较快,代码附加注释,具有参考学习价值。
4.分别用广度优先搜索策略、和启发式搜索算法(A*算法)求解八数码问题; 1>BFS 1)状态表示的数据结构 //状态 struct State { int arr[3][3]; //记录九宫格 int zeroX; //0所在的横坐标 int zeroY; //0所在的...
自编的 可以看看试试 结合人工智能课本P57页
# pyqt5 八数码拼图游戏 广度优先搜索(bfs)、双向广搜(dbfs)、A*搜索求解 1. pyqt5制作可视化窗口,qss美观ui; 2. 自定义导入图片,生成3、4、5阶八数码拼图; 3. 可以点击移动小方块进行游戏; 4. 可以选择使用...
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
递归和排列 BFS BFS和队列 状态图搜索:八数码问题 BFS与A*算法 双向广搜 DFS DFS和递归 回溯与剪枝:八皇后 迭代加深搜索 IDA
八数码难题也称九宫问题,它是在3×3的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态S0,目标状态Sg,要求程序能输入任意的初始状态和目标状态,要求通过空格来移动八张牌使得棋盘由初始...
人工智能 一种现代的方法 第3章 通过搜索进行问题求解 DFS,BFS,IDS,UCS,DIS,BS,A*的罗马尼亚假日问题的实例编写,八数码问题的A*解决代码
人工智能作业,利用python实现宽度优先BFS搜索解决八数码问题
深度优先搜索算法(DFS) 广度优先搜索算法(BFS) A星算法(A*) 迭代加深的A星算法(IDA*) 模拟退火算法(SA) ...八数码、井字图部分(用于演示IDA start算法) 模拟退火部分(单独用于演示SA算法)
九宫拼图8数码C#解决方案 双向广度优先算法,如果想知道这个程序算法是什么的话,请联系我QQ:124286266,并在验证栏填写:D3D程序爱好者.运行时先按回车,再按空格
3、启发式搜索,八数码难题($h_1(x)=错放棋子数$、$h_2(x)=曼哈顿距离$)→ A*算法求解(OPEN、CLOSED标识); 4、子句集求取; 5、推理:消去互补对,消解式; 6、含变量的消解式(置换); 7、消解反演,反演求解...
第7章 DFS与BFS以及剪枝问题……………………………………………………119 7.1 深度优先遍历……………………………………………………………………119 〖案例l〗15数码难题…………………………………………...