BZOJ1054: [HAOI2008]移动玩具

浏览数：24 / 时间：2015年06月11日

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1028 Solved: 555
[Submit][Status]

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

HINT

Source

题解：

爆搜。。。

代码：

1.自己写的一直WA，不知道为什么

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #define inf 1000000000
12 #define maxn 30000000+1000
13 #define maxm 1000000
14 #define eps 1e-10
15 #define ll long long
16 using namespace std;
17 inline int read()
18 {
19     int x=0,f=1;char ch=getchar();
20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
21     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}
22     return x*f;
23 }
24 int s=0,t=0,q[maxn],d[maxm],m[20];
25 char ch;
26 int main()
27 {
28     freopen("input.txt","r",stdin);
29     freopen("output.txt","w",stdout);
30     m[0]=1;
31     for(int i=1;i<=16;i++)m[i]=m[i-1]*2;
32     for(int i=1;i<=16;i++)
33     {
34         ch=‘ ‘;
35         while(ch<‘0‘||ch>‘9‘)ch=getchar();
36         if(ch==‘1‘)s+=m[i];
37     }
38     for(int i=1;i<=16;i++)
39     {
40         ch=‘ ‘;
41         while(ch<‘0‘||ch>‘9‘)ch=getchar();
42         if(ch==‘1‘)t+=m[i];
43     }
44     int l=0,r=1;q[1]=s;d[s]=0;
45     memset(d,0,sizeof(d));
46     while(l<r)
47     {
48         int x=q[++l],y;
49         for(int i=1;i<=16;i++)
50         if((1<<i)&x)
51         {
52             if(i%4!=1&&!(m[i-1]&x))
53             {
54                 y=x-m[i];y+=m[i-1];
55                 if(d[y]==0)q[++r]=y,d[y]=d[x]+1;
56                 if(y==t)
57                 {cout<<d[y]<<endl;return 0;}
58             }
59             if(i%4!=0&&!(m[i+1]&x))
60             {
61                 y=x-m[i];y+=m[i+1];
62                 if(d[y]==0)q[++r]=y,d[y]=d[x]+1;
63                 if(y==t)
64                 {cout<<d[y]<<endl;return 0;}
65             }
66             if((i-1)/4!=0&&!(m[i-4]&x))
67             {
68                 y=x-m[i];y+=m[i-4];
69                 if(d[y]==0)q[++r]=y,d[y]=d[x]+1;
70                 if(y==t)
71                 {cout<<d[y]<<endl;return 0;}
72             }
73             if((i-1)/4!=3&&!((m[i+4]&x)))
74             {
75                 y=x-m[i];y+=m[i+4];
76                 if(d[y]==0)q[++r]=y,d[y]=d[x]+1;
77                 if(y==t)
78                 {cout<<d[y]<<endl;return 0;}
79             }
80         }
81     }
82     return 0;
83 }

View Code

2.别人的pascal

 1 var
 2 i,j,a,y,min:longint;
 3 s:string;
 4 m:array[0..5,0..5] of boolean;
 5 o:array[0..65535] of longint;
 6 
 7 function js:longint;
 8 var
 9 i,j,a:longint;
10 begin
11 a:=0;
12 for i:=1 to 4 do
13   for j:=1 to 4 do
14     if m[i,j] then a:=(a shl 1)+1 else a:=a shl 1;
15 exit(a);
16 end;
17 
18 procedure bfs(x,t:longint);
19 var
20 i,j:longint;
21 begin
22 if t>=min then exit;
23 if x=y then
24   begin
25   min:=t;
26   exit;
27   end;
28 if t>=o[x] then exit;
29 o[x]:=t;
30 for i:=1 to 4 do
31   for j:=1 to 4 do
32     if m[i,j] then
33       begin
34       if m[i-1,j]=false then
35         begin
36         m[i-1,j]:=true;
37         m[i,j]:=false;
38         bfs(js,t+1);
39         m[i,j]:=true;
40         m[i-1,j]:=false;
41         end;
42       if m[i+1,j]=false then
43         begin
44         m[i+1,j]:=true;
45         m[i,j]:=false;
46         bfs(js,t+1);
47         m[i,j]:=true;
48         m[i+1,j]:=false;
49         end;
50       if m[i,j-1]=false then
51         begin
52         m[i,j-1]:=true;
53         m[i,j]:=false;
54         bfs(js,t+1);
55         m[i,j]:=true;
56         m[i,j-1]:=false;
57         end;
58       if m[i,j+1]=false then
59         begin
60         m[i,j+1]:=true;
61         m[i,j]:=false;
62         bfs(js,t+1);
63         m[i,j]:=true;
64         m[i,j+1]:=false;
65         end;
66       end;
67 end;
68 
69 begin
70 min:=100;
71 for i:=0 to 5 do
72   begin
73   m[i,0]:=true;
74   m[i,5]:=true;
75   m[0,i]:=true;
76   m[5,i]:=true;
77   end;
78 for i:=0 to 65535 do o[i]:=1 shl 31-1;
79 for i:=1 to 4 do
80   begin
81   readln(s);
82   for j:=1 to 4 do
83     if s[j]=‘1‘ then m[i,j]:=true else m[i,j]:=false;
84   end;
85 readln;
86 for i:=1 to 4 do
87   begin
88   readln(s);
89   for j:=1 to 4 do
90     if s[j]=‘1‘ then y:=(y shl 1)+1 else y:=y shl 1;
91   end;
92 bfs(js,0);
93 writeln(min);
94 end.