CHESSCBG - Bàn cờ thế
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
PROGRAM CHESSCBG;
CONST
fi='';
fo='';
max=128700;
oo=65535;
lt2:array[0..15] of word=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768);
VAR
queue:array[0..max] of word;
sl:array[0..max] of longint;
xet:array[0..oo] of word;
s,t:word;
kq,first,last:longint;
procedure readInput;
var
f:text;
i,j:byte;
ch:char;
begin
assign(f,fi); reset(f);
s:=0; t:=0;
for i:=0 to 3 do
begin
for j:=0 to 3 do
begin
read(f,ch);
if ch='1' then
s:=s+lt2[(3-i)*4+3-j];
end;
readln(f);
end;
for i:=0 to 3 do
begin
for j:=0 to 3 do
begin
read(f,ch);
if ch='1' then
t:=t+lt2[(3-i)*4+3-j];
end;
readln(f);
end;
close(f);
end;
procedure solve;
var
u,v,i,k:word;
sb:longint;
begin
first:=1; last:=1;
queue[1]:=s; sl[1]:=0;
xet[s]:=1;
while first<=last do
begin
u:=queue[first]; sb:=sl[first];
inc(first);
for i:=0 to 15 do
if ((u shr i) and 1=1) and ((u shr (i+1)) and 1=0) and (i mod 4<>3) then
begin
v:=u-lt2[i]+lt2[i+1];
if v=t then begin kq:=sb+1; exit; end;
if xet[v]=0 then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
sl[last]:=sb+1;
end;
end;
for i:=1 to 15 do
if ((u shr i) and 1=1) and ((u shr (i-1)) and 1=0) and (i mod 4<>0) then
begin
v:=u-lt2[i]+lt2[i-1];
if v=t then begin kq:=sb+1; exit; end;
if xet[v]=0 then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
sl[last]:=sb+1;
end;
end;
for i:=0 to 11 do
if ((u shr i) and 1=1) and ((u shr (i+4)) and 1=0) then
begin
v:=u-lt2[i]+lt2[i+4];
if v=t then begin kq:=sb+1; exit; end;
if xet[v]=0 then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
sl[last]:=sb+1;
end;
end;
for i:=4 to 15 do
if ((u shr i) and 1=1) and ((u shr (i-4)) and 1=0) then
begin
v:=u-lt2[i]+lt2[i-4];
if v=t then begin kq:=sb+1; exit; end;
if xet[v]=0 then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
sl[last]:=sb+1;
end;
end;
end;
end;
procedure writeOutput;
var
f:text;
begin
assign(f,fo); rewrite(f);
writeln(f,kq);
close(f);
end;
BEGIN
readInput;
solve;
writeOutput;
END.