Question

拼图游戏算法

#include"iostream.h"

struct node{
int nodesun[4][4];
int x,y;
}path[1000];
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
int top;
int desti[4][4];//目标状态
int detect(struct node *p)
{int i,j;
for(i=1;i<4;i )
for(j=1;j<4;j )
if(p->nodesun[i][j]!=desti[i][j])
return 0;
return 1;
}

void printlj()
{int tempt;
int i,j;
tempt=1;
while(tempt<=top)
{ for(i=1;i<4;i )
for(j=1;j<4;j )
{cout<<path[tempt].nodesun[i][j];
if(j==3)
cout<<" "<<endl;
}
tempt ;
}
}

void main()
{ //初始化
int i,j,m,n,f;
int temp,find=0;
top=1;
for(i=1;i<4;i )
for(j=1;j<4;j )
{cout<<"请输入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
cin>>temp;
path[1].nodesun[i][j]=temp;
}
cout<<"请输入初始状态的空格的位置(行)"<<endl;
cin>>temp;
path[1].x=temp;
cout<<"请输入初始状态的空格的位置(列)"<<endl;
cin>>temp;
path[1].y=temp;
//目标状态
for(i=1;i<4;i )
for(j=1;j<4;j )
{cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
cin>>temp;
desti[i][j]=temp;
}
//深度优先搜索
while(!find)
{ m=path[top].x;
n=path[top].y ;
for(f=0;f<4;f )
{i=m+zx[f];
j=n+zy[f];
if(i>=1&&i<=3&&j>=1&&j<=3)
{top ;
path[top]=path[top-1];
path[top].nodesun[m][n]=path[top-1].nodesun[i][j];
path[top].nodesun[i][j]=0;

path[top].x=i;
path[top].y=j;

if(detect(&path[top]))
{printlj();
find=1;
break;
}

break;
}//if

}//for

}//while
}

请教一下谁能看懂这个算法，帮忙解释一下，这是九宫图的算法
概说一下 :假如一副图是由几个部分拼凑成的,现在要你把这些散块拼凑成一副完整的图片
也可以是几个数字来拼凑
比如 3*3的格子
1 2 3
4 5 6
7 8 (相当于原始矩阵)
有一个格子是空的现在要你组合成
1 2 7
3 6 4
5 8 (目标矩阵)
问题是编写一种算法 能根据输入的原始图形(矩阵)拼凑成目标图形(目标矩阵) 要求是步数最少(耗时间最少)
请各位会的帮帮忙，我们要编个程序，我实在是不会

Answer 1

我那个程序找不着了，我在那个帖子回了，你找一下。

这个算法应该是BFS，DFS你觉得。。。呵呵。。

BFS+hash

HASH选择排列数的康托展开。这样可以在2s内圆满解决。

（指2s预处理，然后应对所有的输入瞬间出解）