【问题描述】
黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。
【样例输入】
1111
0000
1110
0010
1010
0101
1010
0101
【样例输出】
4
1222
1424
3242
4344
【解题思路】
看到最少步数，果断广搜。不过状态太多，需要判重。大家可以看到，出题人在数据一栏写了必须用状态压缩，不能用康托展开和hash，他说往东走，咱们偏往西走，就用hash优化。（别想从我嘴里套出我不会状态压缩和康托展开）不过hash函数会很不好找，这里我用的是二进制转十进制的方法存hash，这样的话保证每种状态下只有一个hash函数，就不需要挂链表了，主要的是比较目前状态与目标状态是否相同时会耗费点时间，不过1s还是能过的，然后一个关键的地方就是存储哪两个坐标换了位置，我是用的字符来存的，详见代码。
【代码实现】
type arr=array[..,..] of char;
rec=record
m:arr;
step:longint;
ans:array[..,..] of char;
end;
const dx:array[..] of longint=(,-,,);
dy:array[..] of longint=(,,-,);
var start,ans:rec;
f:array[..] of boolean;
spos,epos:arr;
fr,r,i,j:longint;
a:array[..] of rec;
function equal(m:arr):boolean;
var i,j:longint;
begin
for i:= to do
for j:= to do
if m[i,j]<>epos[i,j] then exit(false);
exit(true);
end;
function hash(m:arr):longint;//二进制转十进制，用位运算，效率高
var res,i,j:longint;
begin
res:=;
for i:= to do
for j:= to do
begin
res:=(res shl );
res:=res+ord(m[i,j])-ord('');
end;
exit(res);
end;
procedure bfs;
var t,i,j,k,x,y:longint;
now,next:rec;
temp:char;
begin
fillchar(f,sizeof(f),true);
t:=hash(spos);
f[t]:=false;
fr:=;r:=;
while fr<>r do
begin
inc(fr);
now:=a[fr];
if equal(now.m) then
begin
ans:=now;
exit;
end;
for i:= to do
for j:= to do
for k:= to do
begin
next:=now;
inc(next.step);
x:=i+dx[k];
y:=j+dy[k];
if (x>=)and(x<=)and(y>=)and(y<=) then
begin
temp:=next.m[i,j];
next.m[i,j]:=next.m[x,y];
next.m[x,y]:=temp;
next.ans[next.step,]:=chr(ord('')+i);
next.ans[next.step,]:=chr(ord('')+j);
next.ans[next.step,]:=chr(ord('')+x);
next.ans[next.step,]:=chr(ord('')+y);
next.ans[next.step,]:=#;//存储哪两个坐标换了位置
if equal(next.m) then
begin
ans:=next;
exit;
end;
t:=hash(next.m);
if f[t] then
begin
f[t]:=false;
inc(r);
a[r]:=next;
end;
end;
end;
end;
end;
begin
for i:= to do
begin
for j:= to do
read(spos[i,j]);
readln;
end;
for i:= to do
begin
for j:= to do
read(epos[i,j]);
readln;
end;
for i:= to do
for j:= to do
start.m[i,j]:=spos[i,j];
start.step:=;
a[]:=start;
bfs;
writeln(ans.step);
for i:= to ans.step do
begin
for j:= to do
write(ans.ans[i,j]);
writeln;
end;
end.