CHESSCBG - Bàn cờ thế
Tác giả: ll931110
Ngôn ngữ: Pascal
Program CHESSCBG;
Const
input = '';
output = '';
h: array[1..17] of integer = (0,2,5,8,10,13,17,21,24,27,31,35,38,40,43,46,48);
adj: array[1..48] of integer = (5,2,6,1,3,7,2,4,8,3,9,1,6,10,5,2,7,11,6,3,8,12,7,4,13,5,10,14,9,6,11,15,10,7,12,16,11,8,9,14,13,10,15,14,11,16,15,12);
Var
F,d,queue: array[1..150000] of longint;
free: array[1..150000] of boolean;
p: array[1..16] of longint;
s,t: longint;
Procedure init;
Var
fi: text;
i,j: integer;
ch: char;
Begin
Assign(fi, input);
Reset(fi);
s:= 0;
For i:= 1 to 4 do
Begin
For j:= 1 to 4 do
Begin
Read(fi, ch);
s:= s * 2 + ord(ch) - 48;
End;
Readln(fi);
End;
t:= 0;
For i:= 1 to 4 do
Begin
For j:= 1 to 4 do
Begin
Read(fi, ch);
t:= t * 2 + ord(ch) - 48;
End;
Readln(fi);
End;
Close(fi);
End;
Procedure power;
Var
i: integer;
Begin
p[1]:= 1;
For i:= 2 to 16 do p[i]:= p[i - 1] * 2;
End;
Procedure BFS;
Var
front,rear: longint;
i,u,v,iv,tmp: longint;
Begin
For i:= 1 to 150000 do d[i]:= 1000000;
d[s]:= 0;
Fillchar(free, sizeof(free), true);
front:= 1; rear:= 1; queue[1]:= s;
Repeat
u:= queue[front];
inc(front);
If u = t then break;
For i:= 1 to 16 do if u and p[i] = p[i] then
For iv:= h[i] + 1 to h[i + 1] do
Begin
v:= adj[iv];
If u and p[v] <> p[v] then
Begin
tmp:= u - p[i] + p[v];
If d[tmp] > d[u] + 1 then d[tmp]:= d[u] + 1;
If free[tmp] then
Begin
inc(rear);
queue[rear]:= tmp;
free[tmp]:= false;
End;
End;
End;
Until front > rear;
End;
Procedure solve;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, d[t]);
Close(fo);
End;
Begin
init;
power;
BFS;
solve;
End.