http://poj.org/problem?id=1077
#include<cstdio> //双向BFS poj 1077 16ms
#include<cstring>
#include<queue>
#include <iostream>
using namespace std;
const int V=362882;
struct nod{
int n,x; //n表示康拓展开的值,x表示9的位置。
int m[9]; //记录状态
};
int fac[]={1,1,2,6,24,120,720,5040,40320}; //阶乘表
int dx[]={1,-1,0,0},dy[]={0,0,-1,1},tr[]={1,0,3,2}; //tr用于转向,就是正向遍历 <-> 逆向遍历
char dir[]="dulr";
int vir[2][V],p[V],fa[V],d[V],re,rs,ko;
queue<nod> q[2]; //两个队列
void bfs(nod st,nod ed);
int exp(nod s,int k);
int cato(nod a);
/*
void print(int s[]){
for(int i=1;i<=9; i++){
printf("%d ", s[i-1]);
if(i%3==0) puts("");
}
}
void invKT(int n, int k){
int s[10];
int t,j;
bool visit[10] = {false}; //需要记录该数是否已在前面出现过
for(int i=0; i<n; i++){
t = k/fac[n-i-1];
for(j=0; j<n; j++){
if(!visit[j]){
if(t == 0) break;
t--;
}
}
s[i] = j;
visit[j] = true;
k %= fac[n-i-1];
//cout << j << ",";
}
print(s);
cout << endl;
}
*/
int main()
{
freopen("in.txt","r",stdin);
char str[30]; int i;
nod st,ed;
while(gets(str)!=NULL)
{
int cnt=0;
for(i=0;i<9;i++) st.m[i]=i+1; //读取初始的起点和终点
for(i=0;i<strlen(str);i++){
if(str[i]=='x') ed.x=cnt, ed.m[cnt++]=9;
if(str[i]>='1'&&str[i]<='8') ed.m[cnt++]=str[i]-'0';
}
ed.n=cato(ed);
st.x=8; st.n=cato(st);
//cout << st.n << endl;
ko=-1,cnt=0;
bfs(st,ed); //双向BFS搜索
int tempP[V];
if(ko!=-1){ //ko表示是交点的方向,如果没改变说明没交点
for(i=re;fa[i]!=i;i=fa[i]){
tempP[cnt] = i;
d[cnt++]=p[i]; //下面几行打印路径
}
for(i=cnt-1;i>=0;i--){
printf("%c",dir[d[i]]);
//invKT(9,tempP[i]);
}
printf("%c",dir[ko]);
for(i=rs;i!=st.n;i=fa[i]) printf("%c",dir[tr[p[i]]]);
}
else printf("unsolvable");
printf("\n");
}
return 0;
}
int cato(nod a) //康拓展开
{
int i,j,k,sum=0;
for(i=0;i<9;i++){
for(j=i+1,k=0;j<9;j++) if(a.m[j]<a.m[i]) k++;
sum+=k*fac[8-i];
}
return sum;
}
void bfs(nod st,nod ed)
{
memset(fa,-1,sizeof(fa));
memset(vir,0,sizeof(vir));
q[0].push(st); q[1].push(ed); //起点终点入队
vir[0][st.n]=1; vir[1][ed.n]=1;
fa[st.n]=st.n; fa[ed.n]=ed.n;
while(!q[0].empty()||!q[1].empty())
{
nod ss=q[0].front(); q[0].pop();
nod ee=q[1].front(); q[1].pop();
if(exp(ss,0)||exp(ee,1)) break;
}
}
int exp(nod s,int k) //扩展函数,即对s点寻找下一层的点
{
int i,t,sn=s.x,sx=sn/3,sy=sn%3,nn;
nod nex; //下一个遍历节点
for(i=0;i<4;i++){
int nx=sx+dx[i],ny=sy+dy[i];
if(nx<3&&nx>=0&&ny<3&&ny>=0){
nex=s;
nn=nx*3+ny;
t=nex.m[sn]; nex.m[sn]=nex.m[nn]; nex.m[nn]=t; //交换两个位置的值
nex.n=cato(nex);
nex.x=nn; //求下一个可能扩展的点
if(vir[k][nex.n]) continue; //比重复遍历
if(vir[k^1][nex.n]==1) { //找到交点返回1,k代表是从起点还是从终点的路径
// 判断是正向还是逆向
if(k) { ko=i; re=s.n; rs=nex.n; }
else { ko=tr[i]; re=nex.n; rs=s.n; }
return 1;
}
vir[k][nex.n]=1;
q[k].push(nex); //可扩展,入队。
fa[nex.n]=s.n; //保存路径
p[nex.n]=i; //保存路径的方向
}
}
return 0;
}
分享到:
相关推荐
降群法解魔方 哈哈师大 使用双向BFS搜素
通过双向的BFS算法,使得公交安排这样一个问题在最大程度上减少了时间复杂度。而且对于换乘次数的限制一直是一个瓶颈,会严重增加时间复杂度,但本程序通过matlab巧妙的设计,使得换乘10次以内都可以理想时间内解答...
题目:752. 打开转盘锁执行用时:204 ms, 在所有 C++ 提交中击败了40.14%的用户内存消耗:40.3 MB, 在所有 C++ 提交中击败了25.
UI_missionaries_project-DFS,BFS,双向BFS及其时空分析传教士和食人族的问题和解决方案使用DFS,BFS和双向BFS实现。 有关更多信息,请访问 。
实现算法:DFS,BFS,双向BFS,一个自己的启发式,Bellman-Ford,Dijkstrra,SPFA,A*
BFS-DFS-搜索该程序在输入的文件上执行广度优先搜索和深度优先搜索,该文件显示哪些用户ID是朋友(从而创建图形)。
java原始发现双向搜索 假设您必须从阿拉德(Arad)市前往布加勒斯特(Bucharest)市。 您希望沿着这条路线旅行。 以下是路线图。 从一个城市到另一个城市的成本是相同的。 从阿拉德(Arad)市到布加勒斯特...
POJ 3131 双向BFS解立体八数码问题
实现算法:DFS,BFS,双向BFS,一个自己的启发式,Bellman-Ford,Dijkstrra,SPFA,A*
这是一个用Qt写的关于寻路的小程序。动态的演示了A*, BFS ,DFS ,双向BFS 等算法的寻路过程。有兴趣的可以下来看看,自己还可以修改修改。
BFS BFS BFS - 二维矩阵 BFS - 未加权图中的最短路径 BFS - 二部图 BFS - 双向 BFS 分布式文件系统 DFS - 连接组件 DFS - DAG 中的所有祖先 DFS - 计算进入和退出时间 DFS - 拓扑排序 DFS - 二维矩阵 DFS - 图形着色...
基于双向广度优先搜索的路径规划算法是一种常用的图搜索算法,用于寻找两个节点之间的最短路径。该算法从起始节点和目标节点同时进行搜索,通过不断扩展搜索范围,直到两个搜索队列相遇或找到最短路径为止。 核心...
双向 BFS 树 二叉树遍历 线程二叉树,莫里斯遍历 树径 图形 单源最短路径 贝尔曼福特 放松 V-1 次,适用于负加权边,时间复杂度:O(VE) 迪杰斯特拉 贪婪,不适用于负加权边 DS 时间复杂度 邻接矩阵 O(V^2) 邻接表+...
word源码java 算法与数据结构参考资料与典型题目 ...双向BFS 启发式搜索 参考链接 实战题目 平衡树 位运算 参考链接 实战题目 布隆过滤器和LRU 参考链接 题目 排序算法 参考链接 直播课回顾: 提取码:
双向BFS的实现和特性 启发式搜索的实现和特性 AVL树和红黑树的实现和特性 位运算基础与实战要点 布隆过滤器的实现及应用 LRU Cache的实现及应用 初级排序和高级排序的实现和特性 字符串算法 数据结构与算法—冒泡...
双向 BFS: , 所有对最短路径 - Johnson 网络流量 中位数和订单统计这个问题有一个线性的最坏情况运行时间。 : 确定在一组共线的 n 个点中是否存在任何 3 个点 确定一个点是否位于一个简单的多边形内(不是必要的...
当前实施的路径查找(Dijkstras,BFS,A星,双向)排序(合并,快速,堆,气泡,插入,选择)回溯(NQueen问题)搜索(线性,二进制)最新添加的寻路可视化工具排序算法可视化工具N皇后问题可视化工具线性搜索可视化...
# pyqt5 八数码拼图游戏 广度优先搜索(bfs)、双向广搜(dbfs)、A*搜索求解 1. pyqt5制作可视化窗口,qss美观ui; 2. 自定义导入图片,生成3、4、5阶八数码拼图; 3. 可以点击移动小方块进行游戏; 4. 可以选择使用...
n个端点的无向图,编号范围[0,n)。Edges0表示{{n1,n2},...{n3,n4}}表示n1和n2,n3和n4之间有路联接。Edges1表示{{n1,n2},...{n3,n4}}表示n1和n2,n3和n4之间有损坏的路连接。要想让s和d之间至少有一条通道,最小需要...
C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本...42图_BFS