#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <
set>
using namespace std;
typedef int State[
9];
const int maxstate =
1000000;
State st[maxstate], goal;
int dist[maxstate];
const int dx[] = {-
1,
1,
0,
0};
const int dy[] = {
0,
0, -
1,
1};
set<
int>
vis;
/*
void init_lookup_table()
{
vis.clear();
}
int try_to_insert(int s)
{
int v = 0;
for(int i = 0; i < 9; i++)
v = v * 10 + st[s][i];
if(vis.count(v))
return 0;
vis.insert(v);
return 1;
}
*/
const int hashsize =
1000003;
int head[hashsize], Next[maxstate];
void init_lookup_table()
{
memset(head, 0,
sizeof(head));
}
int Hash(State &
s)
{
int v =
0;
for(
int i =
0; i <
9; i++
)
v = v *
10 +
s[i];
return v %
hashsize;
}
int try_to_insert(
int s)
{
int h =
Hash(st[s]);
int u =
head[h];
while(u)
{
if(memcmp(st[u], st[s],
sizeof(st[s])) ==
0)
return 0;
u =
Next[u];
}
Next[s] =
head[h];
head[h] =
s;
return 1;
}
int bfs()
{
init_lookup_table();
int first =
1, last =
2;
dist[1] =
0;
while(first <
last)
{
State &s =
st[first];
if(memcmp(goal, s,
sizeof(s)) ==
0)
return first;
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 fx = x +
dx[i];
int fy = y +
dy[i];
int fz = fx *
3 +
fy;
if(fx >=
0 && fy >=
0 && fx <
3 && fy <
3)
{
State &t =
st[last];
memcpy(&t, &s,
sizeof(s));
t[fz] =
s[z];
t[z] =
s[fz];
dist[last] = dist[first] +
1;
if(try_to_insert(last))
last++
;
}
}
first++
;
}
return 0;
}
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 ans =
bfs();
if(ans >
0)
printf("%d\n", dist[ans]);
else
printf("-1\n");
return 0;
}
/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/
转载于:https://www.cnblogs.com/zhaopAC/p/5269322.html
相关资源：USB资料.zip(紫薯布丁略略略)
