1054: [HAOI2008]移动玩具

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了

好吧我还是写广搜吧

 const

     fx:array[..]of longint=(-,,,-);

 var

     f,q:array[.. shl ]of longint;

     start,goal,head,tail:longint;

 procedure bfs;

 var

     i,j,s:longint;

 begin

     head:=;

     tail:=;

     q[]:=start;

     while f[goal]><< do

       begin

         for i:= to  do

           for j:= to  do

             if (i+fx[j]>) and (i+fx[j]<) and ((i and <>) or (fx[j]<>)) and ((i and <>) or (fx[j]<>-)) then

             if (q[head] and (<<(i-))>) and (q[head] and (<<(i+fx[j]-))=) then

             begin

               s:=q[head]-(<<(i-))+(<<(i+fx[j]-));

               if f[s]><< then

               begin

                 f[s]:=f[q[head]]+;

                 inc(tail);

                 q[tail]:=s;

               end;

             end;

         inc(head);

       end;

 end;

 procedure main;

 var

     i,j:longint;

     s:char;

 begin

     for i:= to  do

       for j:= to  do

         begin

           repeat

             read(s);

           until (s='') or (s='');

           start:=(start<<)+ord(s)-ord('');

         end;

     for i:= to  do

       for j:= to  do

         begin

           repeat

             read(s);

           until (s='') or (s='');

           goal:=(goal<<)+ord(s)-ord('');

         end;

     fillchar(f,sizeof(f),);

     f[start]:=;

     bfs;

     write(f[goal]);

 end;

 begin

     main;

 end.

巴特西

1054: [HAOI2008]移动玩具 - BZOJ

最新文章

热门文章