8数码,欺我太甚!

不多述,直接上代码,至于康拓展开,以前的文章里有

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘表
int dir[4][2]={1,0,0,1,-1,0,0,-1};//方向
int vis[362881];
int kangst,kanged;
int t1[3][3];
int t2[3][3];
pair<int,int>p;
struct node{
int maze[3][3];
pair<int,int>pos;
int kang;
int step;
};
int Kang_open (int t[3][3])
{
int s[9],num=0,k=0,sum=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
s[k++]=t[i][j];
for(int i=0;i<9;i++){
num=0;
for(int j=i+1;j<9;j++)
{
if(s[i]>s[j])
num++;
}
sum+=num*fac[8-i];
}
return sum;
}
int bfs()
{
node now;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
now.maze[i][j]=t1[i][j];
now.kang=kangst;
now.step=0;
now.pos=p;
vis[kangst]=1;
queue<node>que;
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
if(now.kang==kanged)
return now.step;
node next=now;
for(int i=0;i<4;i++)
{
next=now;
next.pos.first = now.pos.first+dir[i][0];
next.pos.second= now.pos.second+dir[i][1];
if(next.pos.first >=0&&next.pos.first <3&&next.pos.second>=0&&next.pos.second<3)
{
next.maze[now.pos.first][now.pos.second]=now.maze[next.pos.first][next.pos.second];
next.maze[next.pos.first][next.pos.second]=0;
next.kang=Kang_open(next.maze);
if(!vis[next.kang])
{
vis[next.kang]=1;
next.step++;
que.push(next);
}
}
}
}
return -1;
}
int main ()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
scanf("%d",&t1[i][j]);
if(t1[i][j]==0)
p.first=i,p.second=j;
}
kangst=Kang_open(t1);
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
scanf("%d",&t2[i][j]);
kanged=Kang_open(t2);
printf("%d\n",bfs());
return 0;
}
上一篇:vim主题颜色


下一篇:H2Database数据类型