#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <
set>
using namespace std;
typedef int state[
9];
const int maxstate=
1000000;
state st[maxstate],goal;
int dst[maxstate];
int fa[maxstate];
set<
int>
vis;
const int dx[]={
0,
0,-
1,
1};
const int dy[]={-
1,
1,
0,
0};
void init_lookup_table() {vis.clear();}
bool try_to_insert(
int n)
{
int v=
0;
for(
int i=
0;i<
9;i++) v=v*
10+
st[n][i];
if(vis.count(v))
return 0;
vis.insert(v);
return 1;
}
//bfs只可能在两种情况下返回,一是找到满足的状态
//二是front大于rear,即队列空
int bfs()
{
init_lookup_table();
int front=
1;
int rear=
2;
while(front<
rear)
{
state& s=
st[front];
if(memcmp(s,goal,
sizeof(goal))==
0)
return front;
int z;
for(z=
0;z<
9;z++)
if(s[z]==
0)
break;
int x=z/
3;
int y=z%
3;
for(
int i=
0;i<
4;i++
)
{
int newx=x+
dx[i];
int newy=y+
dy[i];
if(newx>=
0 && newx<=
2 && newy>=
0 && newy<=
2)
{
int newz=newx*
3+
newy;
state& t=
st[rear];
memcpy(t,s,sizeof(s));
//!!!!!!!!!!!!!!!!!
t[newz]=
s[z];
t[z]=
s[newz];
dst[rear]=dst[front]+
1;
fa[rear]=
front;
if(try_to_insert(rear)) rear++
;
//如果在一个front下rear没有更新意味着这条路走不通
}
}
front++
;
}
return 0;
}
void print_ans(
int n)
{
for(
int i=
0;i<
9;i++
)
printf("%d ",st[n][i]);
printf("\n");
}
int main()
{
for(
int i=
0;i<
9;i++) scanf(
"%d",&st[
1][i]);
for(
int i=
0;i<
9;i++) scanf(
"%d",&
goal[i]);
int cnt=
bfs();
if(cnt!=
0)
{
printf("%d\n",dst[cnt]);
while(cnt!=
1)
{
print_ans(cnt);
cnt=
fa[cnt];
}
}
else printf(
"-1\n");
return 0;
}
转载于:https://www.cnblogs.com/tclan126/p/7445970.html
