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.

Download