#include<iostream> #include<map> using namespace std; typedef struct { int x; int w; char s; }aaa; map<int,int>a; aaa dui[1000000],du[1000000];//两个队列 char www[1000000]; int main() { int i,j; int many,ji,ji1,zan,zan2,x,y,tt,ww,ta,wa,q; int fang1[4][2]={-1,0,0,-1,1,0,0,1};//方向数组 int fang2[4][2]={0,-1,-1,0,0,1,1,0};//方向数组 int jin[9]={100000000,10000000,1000000,100000,10000,1000,100,10,1}; char w[3][3]; while(cin>>w[0][0]) { cin>>w[0][1]>>w[0][2]; for(i=1;i<3;i++) for(j=0;j<3;j++) cin>>w[i][j]; many=0; char w2[9]; for(i=0;i<3;i++) for(j=0;j<3;j++) w2[many++]=w[i][j]; many=0; for(i=0;i<9;i++) for(j=0;j<i;j++) if((w2[i]<w2[j])&&w2[i]!='x'&&w2[j]!='x') many+=1; if(many%2==1) { printf("unsolvable\n"); return(0); } int e,s; s=0; for(i=0;i<3;i++) for(j=0;j<3;j++) { if(w[i][j]!='x')s=10*s+w[i][j]-'0'; else s=10*s+9; } tt=ww=ta=wa=1; e=123456789; dui[ww].w=s; du[wa].w=e; a[s]=1; a[e]=2; bool neng=false; if(s==e)neng=true; while(!neng) { ji=0; ji1=0; for(i=0;i<9;i++) if((dui[tt].w/jin[i])%10==9) { ji=i; break; } for(i=0;i<9;i++) if((du[ta].w/jin[i])%10==9) { ji1=i; break; } for(i=0;i<4;i++) { x=ji/3; y=ji%3; if(x+fang1[i][0]<3&&x+fang1[i][0]>=0&&y+fang1[i][1]<3&&y+fang1[i][1]>=0&&neng==false) { s=dui[tt].w; zan=s/jin[ji]; zan2=s/jin[(x+fang1[i][0])*3+(y+fang1[i][1])]; zan=zan%10; zan2=zan2%10; s=s-zan*jin[ji]-zan2*jin[(x+fang1[i][0])*3+(y+fang1[i][1])]; s=s+zan2*jin[ji]+zan*jin[(x+fang1[i][0])*3+(y+fang1[i][1])]; if(a[s]!=1) { if(a[s]==2)neng=true; a[s]=1; ww+=1; dui[ww].w=s; dui[ww].x=tt; if(i==0)dui[ww].s='u'; if(i==1)dui[ww].s='l'; if(i==2)dui[ww].s='d'; if(i==3)dui[ww].s='r'; } } x=ji1/3; y=ji1%3; if(x+fang2[i][0]<3&&x+fang2[i][0]>=0&&y+fang2[i][1]<3&&y+fang2[i][1]>=0&&neng==false) { s=du[ta].w; zan=s/jin[ji1]; zan2=s/jin[(x+fang2[i][0])*3+(y+fang2[i][1])]; zan=zan%10; zan2=zan2%10; s=s-zan*jin[ji1]-zan2*jin[(x+fang2[i][0])*3+(y+fang2[i][1])]; s=s+zan2*jin[ji1]+zan*jin[(x+fang2[i][0])*3+(y+fang2[i][1])]; if(a[s]==0) { a[s]=2; wa+=1; du[wa].w=s; du[wa].x=ta; if(i==0)du[wa].s='r'; if(i==1)du[wa].s='d'; if(i==2)du[wa].s='l'; if(i==3)du[wa].s='u'; } } } ta+=1; tt+=1; } ji=0; q=ww; while(q!=1) { ji+=1; www[ji]=dui[q].s; q=dui[q].x; } for(i=ji;i>=1;i--)printf("%c",www[i]); ji=0; q=1; while(du[q].w!=dui[ww].w)q++; while(q!=1) { ji+=1; www[ji]=du[q].s; q=du[q].x; } for(i=1;i<=ji;i++)printf("%c",www[i]); printf("\n"); while(!a.empty())a.erase(a.begin()); } return(0); }
相关推荐
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [实现提示] 设图的结点不超过30个,每个结点用一个编号表示(如果...
通过广度优先算法进行八数码难题的求解,在VC++2010上编译通过
深度优先遍历和广度优先遍历 建立图的应用等等
无向图的连接表存储结构的创建...从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的算法 对具有G.vexnum个顶点的图的广度优先遍历的算法
图的深度遍历和广度遍历是两个重要的算法,这也是我们理解并掌握图这一数据结构的基础。通过此程序算法可以进一步掌握图的构造以及遍历的相关知识。
迷宫问题-广度优先遍历 迷宫 代码 算法
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
数据结构中的图结构,其中最重要的两个遍历算法——深度优先遍历与广度优先遍历
深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现
使用邻接表表示法创建无向图,然后使用非递归算法进行深度优先遍历和广度优先遍历
c++实现图的邻接表深度优先遍历,广度优先遍历
图的遍历,查找最短路径 广度优先遍历 深度优先遍历
c语言的数据结构图的深度优先遍历和广度优先遍历
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
通过广度优先遍历、深度优先遍历实现 开发工具:C#
图的相关操作,对图实现深度优先遍历,值得!!!!!!
实现图的深度与广度优先遍历 c++6.0运行
图的深度优先遍历和广度优先遍历-Java实现
本源文件CPP中代码使用深度优先和广度优先遍历图的算法。