2014年2月27日2,1820

题目描述Description

Description

在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

Input

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

Output

一个整数,所需要的最少移动次数。

输入描述Input Description

Sample Input

1111
0000
1110
0010 

 

1010
0101
1010
0101

输入初试状态,一行九个数字,空格用0表示

Sample Output

4

这是一道bfs的题目,hash去重,然后就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int NN=(1<<17)+7;
 7 const int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
 8 
 9 int bg,ed,h;
10 bool ans[5][5],mark[NN];
11 struct Node
12 {
13     bool a[5][5];
14     int step;
15 }q[NN];
16 
17 int hash(bool a[5][5])
18 {
19     int k=1,s=0;
20     for(int i=1;i<=4;i++)
21        for(int j=1;j<=4;j++)
22           {s+=k*a[i][j];k<<=1;}
23     return s;//hash记录 
24 }
25 void bfs()
26 {
27     int t=0,w=1;
28     char ch[5];
29     for(int i=1;i<=4;i++)
30     {
31         scanf("%s",ch);
32         for(int j=1;j<=4;j++)
33            q[0].a[i][j]=ch[j-1]-'0';
34     }  
35     for(int i=1;i<=4;i++)
36     {
37         scanf("%s",ch);
38         for(int j=1;j<=4;j++)
39            ans[i][j]=ch[j-1]-'0';
40     }
41     bg=hash(q[t].a);
42     ed=hash(ans);
43     if(bg==ed){printf("0");return;}//特殊考虑
44      
45     mark[bg]=1;
46     int x,y;
47     while(t<w)
48     {
49         for(int i=1;i<=4;i++)
50            for(int j=1;j<=4;j++)
51               if(q[t].a[i][j])
52               for(int k=0;k<4;k++)
53               {
54                     x=i+xx[k],y=j+yy[k];
55                     if(q[t].a[x][y]||x>4||y>4||x<1||y<1)continue;
56                     swap(q[t].a[i][j],q[t].a[x][y]);
57                     h=hash(q[t].a);
58                     if(!mark[h]){
59                     if(h==ed){printf("%d",q[t].step+1);return;}
60                     mark[h]=1;
61                     memcpy(q[w].a,q[t].a,sizeof(q[w].a));
62                     q[w].step=q[t].step+1;
63                     w++;
64                     }
65                    swap(q[t].a[i][j],q[t].a[x][y]);
66               }
67         t++;
68     }//简单宽搜,时间复杂度一千万。 
69 }
70 int main()
71 {
72     bfs();
73 }

 

输出描述Output Description

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入Sample Input

283104765

样例输出Sample Output

4

数据范围及提示Data Size & Hint

详见试题

分类标签Tags点此展开

广搜+hash判重

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstdlib>  4 using namespace std;  5 const int MAXN=5;  6 int xx[5]={-1,+1,0,0};  7 int yy[5]={0,0,-1,+1};  8 struct node  9 { 10     int mp[MAXN][MAXN]; 11 }a[100001]; 12 int hashfind[3733801]; 13 int step[200]; 14 int h=0,t=1; 15 int bc[MAXN][MAXN]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}}; 16 int hash() 17 { 18     int s=0; 19     int k=1; 20     for(int i=1;i<=3;i++) 21     { 22         for(int j=1;j<=3;j++) 23         { 24             s=s+a[t].mp[i][j]*k; 25             k=k*7; 26         } 27     } 28     s=s%3733801; 29     if(hashfind[s]==0) 30     { 31         hashfind[s]=1; 32         return 1; 33     } 34     else 35     { 36         return 0; 37     } 38 } 39 int check() 40 { 41     for(int i=1;i<=3;i++) 42     { 43         for(int j=1;j<=3;j++) 44         { 45             if(a[t].mp[i][j]!=bc[i][j]) 46             return 0; 47         } 48     } 49     return 1; 50 } 51 void move(int x,int y) 52 { 53      54     for(int i=0;i<4;i++) 55     { 56         int wx=x+xx[i]; 57         int wy=y+yy[i]; 58         if(wx>=1&&wx<=3&&wy>=1&&wy<=3) 59         { 60             for(int j=1;j<=3;j++) 61             { 62                 for(int k=1;k<=3;k++) 63                     { 64                         a[t].mp[j][k]=a[h].mp[j][k]; 65                     } 66             } 67             swap(a[t].mp[wx][wy],a[t].mp[x][y]); 68             step[t]=step[h]+1; 69             if==1) 70             { 71                 printf("%d",step[t]); 72                 exit(0);// end 73             } 74             if==1) 75             t++; 76         } 77     } 78 } 79 void bfs() 80 { 81     while(h<t) 82     { 83         for(int i=1;i<=3;i++) 84         { 85             for(int j=1;j<=3;j++) 86             { 87                 if(a[h].mp[i][j]==0) 88                 { 89                     move; 90                 } 91             } 92         } 93         h++; 94     } 95 } 96 int main() 97 { 98     char dr[10]; 99     int bgx=0;100     int bgy=0;101     gets;102     int now=0;103     for(int i=1;i<=3;i++)104     {105         for(int j=1;j<=3;j++)106         {107             a[0].mp[i][j]=dr[now]-48;108             if(a[0].mp[i][j]==0)109             {110                 bgx=i;111                 bgy=j;112             }113             now++;114         }115     }116     bfs();117     return 0;118 }
admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注