Description
在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
Input
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
Output
一个整数，所需要的最少移动次数。
Sample
Input
1111
0000
1110
0010
1010
0101
1010
0101
Sample
Output
4
直接搜就行了
囧，本来以为迭代深搜可以行的，但是悲剧的TLE了
好吧我还是写广搜吧
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.