1054: [HAOI2008]移动玩具 - BZOJ

 1 const
 2     fx:array[1..4]of longint=(-4,4,1,-1);
 3 var
 4     f,q:array[0..1 shl 16]of longint;
 5     start,goal,head,tail:longint;
 6  
 7 procedure bfs;
 8 var
 9     i,j,s:longint;
10 begin
11     head:=1;
12     tail:=1;
13     q[1]:=start;
14     while f[goal]>1<<20 do
15       begin
16         for i:=1 to 16 do
17           for j:=1 to 4 do
18             if (i+fx[j]>0) and (i+fx[j]<17) and ((i and 3<>0) or (fx[j]<>1)) and ((i and 3<>1) or (fx[j]<>-1)) then
19             if (q[head] and (1<<(i-1))>0) and (q[head] and (1<<(i+fx[j]-1))=0) then
20             begin
21               s:=q[head]-(1<<(i-1))+(1<<(i+fx[j]-1));
22               if f[s]>1<<20 then
23               begin
24                 f[s]:=f[q[head]]+1;
25                 inc(tail);
26                 q[tail]:=s;
27               end;
28             end;
29         inc(head);
30       end;
31 end;
32  
33 procedure main;
34 var
35     i,j:longint;
36     s:char;
37 begin
38     for i:=1 to 4 do
39       for j:=1 to 4 do
40         begin
41           repeat
42             read(s);
43           until (s=‘1‘) or (s=‘0‘);
44           start:=(start<<1)+ord(s)-ord(‘0‘);
45         end;
46     for i:=1 to 4 do
47       for j:=1 to 4 do
48         begin
49           repeat
50             read(s);
51           until (s=‘1‘) or (s=‘0‘);
52           goal:=(goal<<1)+ord(s)-ord(‘0‘);
53         end;
54     fillchar(f,sizeof(f),1);
55     f[start]:=0;
56     bfs;
57     write(f[goal]);
58 end;
59  
60 begin
61     main;
62 end.