1054: [HAOI2008]移动玩具
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1272 Solved: 690
[Submit][Status][Discuss]
Description
在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
Input
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
Output
一个整数，所需要的最少移动次数。
Sample Input
1111
0000
1110
0010
0000
1110
0010
1010
0101
1010
0101
Sample Output
4
HINT
Source
题解：其实是一道水水哒搜索题，只要你知道怎么状压，怎么用一个数组判重同时记录最优值就好了
（PS：其实我WA掉的那一次是没特判开头结尾情况完全一样的情形，应该输出0，而我原来的程序将没有输出= =，注意下）
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
i,j,k,l,m,n,x0,x1,x,y,f,r:longint;
c,d:array[..] of longint;
list:array[..] of longint;ch:char;
function num(x,y:longint):longint;inline;
begin
exit(*(x-)+y);
end;
function getit(x,y:longint):longint;inline;
begin
if odd(x div list[y]) then exit() else exit();
end;
procedure orz(x:longint);inline;
begin
writeln(x);
readln;
halt;
end;
begin
list[]:=;for i:= to do list[i]:=list[i-]*;
x0:=;x1:=;
for i:= to do
begin
for j:= to do
begin
read(ch);
inc(x0,(ord(ch)-)*list[num(i,j)]);
end;
readln;
end;
readln;
for i:= to do
begin
for j:= to do
begin
read(ch);
inc(x1,(ord(ch)-)*list[num(i,j)]);
end;
readln;
end;
if x0=x1 then orz();
for i:= to do c[i]:=maxlongint;
d[]:=x0;f:=;r:=;c[x0]:=;
while f<r do
begin
l:=d[f];i:=;x:=;y:=;
while l> do
begin
x:=x+y div ;y:=y mod +;
if odd(l) then
begin
if x> then
begin
if getit(d[f],i-)= then
begin
d[r]:=d[f]-list[i]+list[i-];
if c[d[r]]=maxlongint then
begin
c[d[r]]:=c[d[f]]+;
if d[r]=x1 then orz(c[d[r]]);
inc(r);
end;
end
end;
if x< then
begin
if getit(d[f],i+)= then
begin
d[r]:=d[f]-list[i]+list[i+];
if c[d[r]]=maxlongint then
begin
c[d[r]]:=c[d[f]]+;
if d[r]=x1 then orz(c[d[r]]);
inc(r);
end;
end;
end;
if y> then
begin
if getit(d[f],i-)= then
begin
d[r]:=d[f]-list[i]+list[i-];
if c[d[r]]=maxlongint then
begin
c[d[r]]:=c[d[f]]+;
if d[r]=x1 then orz(c[d[r]]);
inc(r);
end;
end;
end;
if y< then
begin
if getit(d[f],i+)= then
begin
d[r]:=d[f]-list[i]+list[i+];
if c[d[r]]=maxlongint then
begin
c[d[r]]:=c[d[f]]+;
if d[r]=x1 then orz(c[d[r]]);
inc(r);
end;
end;
end;
end;
inc(i);l:=l div ;
end;
inc(f);
end;
end.