Eight puzzle --HOJ 11918
29478 ワード
1、テーマタイプ:シミュレーション、ハッシュ表、BFS.
2、解題構想:(1)Eigh Puzzleの変換方式をシミュレートし、配列に記録する.(2)変換の最終結果は同じであるため、逆のBFSを用いてすべての状況を遍歴し、すべての状況を記録する.(3)検索状況の過程でバイナリハッシュテーブル形式を採用し、検索を容易にする.(4)タイトルごとに入力されたcaseに基づいてテーブルを検索し,直接答えを出力する.
3、注意事項:ハッシュ表方式に注意し、そうでなければTLE.
4、実現方法:(またテンプレートを借りるので、コードが少し乱れている)
2、解題構想:(1)Eigh Puzzleの変換方式をシミュレートし、配列に記録する.(2)変換の最終結果は同じであるため、逆のBFSを用いてすべての状況を遍歴し、すべての状況を記録する.(3)検索状況の過程でバイナリハッシュテーブル形式を採用し、検索を容易にする.(4)タイトルごとに入力されたcaseに基づいてテーブルを検索し,直接答えを出力する.
3、注意事項:ハッシュ表方式に注意し、そうでなければTLE.
4、実現方法:(またテンプレートを借りるので、コードが少し乱れている)
#include
<
iostream
>
#include
<
string
>
using
namespace
std;
const
int
r[]
=
{
0
,
1
,
4
,
3
,
0
,
3
,
4
,
1
,
1
,
2
,
5
,
4
,
1
,
4
,
5
,
2
,
3
,
4
,
7
,
6
,
3
,
6
,
7
,
4
,
4
,
5
,
8
,
7
,
4
,
7
,
8
,
5
};
int
final[]
=
{
69074
,
77576
,
135289
,
157120
,
205759
,
227590
,
285303
,
293805
};
int
p[]
=
{
1
,
1
,
2
,
6
,
24
,
120
,
720
,
5040
,
40320
};
int
d[
362880
], q[
362880
];
int
s[
9
];
int
Encode(
int
*
s)
{
int
i,j,k,x
=
0
;
for
(i
=
0
;i
<
9
;i
++
)
{
k
=
s[i];
for
(j
=
0
;j
<
i;j
++
)
if
(s[j]
<
s[i])
k
--
;
x
+=
k
*
p[
8
-
i];
}
return
x;
}
void
Decode(
int
*
s,
int
x)
{
int
i,j;
for
(i
=
0
;i
<
9
;i
++
)
{
s[i]
=
x
/
p[
8
-
i];
x
%=
p[
8
-
i];
}
for
(i
=
8
;i
>=
0
;i
--
)
for
(j
=
8
;j
>
i;j
--
)
if
(s[j]
>=
s[i])
s[j]
++
;
}
void
Init()
{
int
i,x,y,front,rear,ss[
9
];
memset(d,
-
1
,
sizeof
(d));
for
(i
=
0
;i
<
9
;i
++
)
ss[i]
=
i;
q[
0
]
=
Encode(ss);
d[q[
0
]]
=
0
;
front
=
0
, rear
=
1
;
while
(front
<
rear)
{
x
=
q[front
++
];
Decode(s,x);
{
for
(i
=
0
;i
<
9
;i
++
)
{
if
(s[i]
==
8
)
break
;
}
if
(i
!=
0
&&
i
!=
1
&&
i
!=
2
)
{
s[i]
=
s[i
-
3
];
s[i
-
3
]
=
8
;
y
=
Encode(s);
if
(d[y]
<
0
)
{
d[y]
=
d[x]
+
1
;
q[rear
++
]
=
y;
}
s[i
-
3
]
=
s[i];
s[i]
=
9
;
}
if
(i
!=
2
&&
i
!=
5
&&
i
!=
8
)
{
s[i]
=
s[i
+
1
];
s[i
+
1
]
=
8
;
y
=
Encode(s);
if
(d[y]
<
0
)
{
d[y]
=
d[x]
+
1
;
q[rear
++
]
=
y;
}
s[i
+
1
]
=
s[i];
s[i]
=
8
;
}
if
(i
!=
6
&&
i
!=
7
&&
i
!=
8
)
{
s[i]
=
s[i
+
3
];
s[i
+
3
]
=
8
;
y
=
Encode(s);
if
(d[y]
<
0
)
{
d[y]
=
d[x]
+
1
;
q[rear
++
]
=
y;
}
s[i
+
3
]
=
s[i];
s[i]
=
8
;
}
if
(i
!=
0
&&
i
!=
3
&&
i
!=
6
)
{
s[i]
=
s[i
-
1
];
s[i
-
1
]
=
8
;
y
=
Encode(s);
if
(d[y]
<
0
)
{
d[y]
=
d[x]
+
1
;
q[rear
++
]
=
y;
}
s[i
-
1
]
=
s[i];
s[i]
=
8
;
}
}
}
}
int
main()
{
int
i,T;
char
ch;
Init();
cin
>>
T;
while
(T
--
)
{
for
(i
=
0
;i
<
9
;i
++
)
{
cin
>>
ch;
if
(ch
==
'
#
'
)
s[i]
=
8
;
else
s[i]
=
ch
-
'
1
'
;
}
if
(d[Encode(s)]
!=-
1
)
cout
<<
d[Encode(s)]
<<
endl;
else
cout
<<
"
impossible
"
<<
endl;
}
return
0
;
}