高级算法--广搜

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了高级算法--广搜，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3691字，纯文字阅读大概需要6分钟。

内容图文

下面是一本通OJ上题目和代码

·例一：

题目描述：

　　在一个4*4的棋盘上有8个黑棋和8个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

代码实现：

 1 #include<iostream>
 2 #include<queue>
 3 #define FOR(a,b,c) for(int a=(b);a<(c);a++)
 4 using namespace std;
 5 
 6 const int maxn = 16;
 7 struct Node{   // 结构体存棋盘的二进制序列和步数
 8     int num,d;
 9 };
10 int A,B;
11 int vis[100000];
12 
13 void BFS() {
14 queue<Node> q;
15     q.push((Node){A,0});
16     while(!q.empty()) 
17     {
18         Node u=q.front(); q.pop();
19         int tmp=u.num;
20         if(tmp==B) { cout<<u.d; return ; }
21         for(int i=15;i>=0;i--)   // 棋盘对应的二进制序列，从高到低依次枚举每个位置
22         {
23             int x=(15-i)/4,y=(15-i)%4,w=1<<i,z;  //计算该位置在棋盘上的x和y坐标值
24             if(y<3 && (tmp&(1<<i))!=(tmp&(1<<i-1)))   //向右交换，二进制序列的i和i-1交换
25             {
26                 z=1<<i-1;
27                 if(!vis[tmp^z^w]) {
28                     vis[tmp^z^w]=1;
29                     q.push((Node){tmp^z^w,u.d+1});
30                 }
31             }
32             if(x<3 && (tmp&(1<<i))!=(tmp&(1<<i-4)))  //向下交换，二进制序列的i和i-4交换
33             {
34                 z=1<<i-4;
35                 if(!vis[tmp^z^w]) {
36                     vis[tmp^z^w]=1;
37                     q.push((Node){tmp^z^w,u.d+1});
38                 }
39             }
40         }
41     }
42 }
43 
44 int main() 
45 {
46     char c;
47     for(int i=15;i>=0;i--) {
48         cin>>c;
49         if(c!='0')  A += 1<<i;
50     }
51     for(int i=15;i>=0;i--) {
52         cin>>c;
53         if(c!='0')  B += 1<<i;
54     }
55     if(A==B) cout<<0;
56     else BFS();
57 }

·例二：

题目描述：

原题来自：HAOI 2008

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

代码实现;

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int dx[]={0,0,1,-1};
 4 const int dy[]={1,-1,0,0};
 5 
 6 char s[10];
 7 int mp[66000],state[5][5],st[5][5],ed[5][5],e;
 8 
 9 int get_hash(int a[5][5]){
10     int tot=0,p=1;
11     for(int i=1;i<=4;i++)
12         for(int j=1;j<=4;j++)
13             tot+=a[i][j]*p,p<<=1;
14     return tot;
15 }
16 
17 void get_state(int x){
18     for(int i=1;i<=4;i++)
19         for(int j=1;j<=4;j++)
20             state[i][j]=x&1,x>>=1;
21 }
22 
23 void read_and_parse(){
24     for(int i=1;i<=4;i++){
25         scanf("%s",s+1);
26         for(int j=1;j<=4;j++)st[i][j]=s[j]-'0';
27     }
28     for(int i=1;i<=4;i++){
29         scanf("%s",s+1);
30         for(int j=1;j<=4;j++)ed[i][j]=s[j]-'0';
31     }
32     memset(mp,-1,sizeof(mp));
33     e=get_hash(ed);
34 }
35 
36 void solve(){
37     queue<int> q;
38     q.push(get_hash(st)),mp[get_hash(st)]=0;
39     while(q.size()){
40         int u=q.front();q.pop();
41         if(u==e)break;
42         get_state(u);
43         for(int i=1;i<=4;i++)
44             for(int j=1;j<=4;j++)
45                 if(state[i][j])
46                     for(int k=0;k<4;k++){
47                         int x=i+dx[k],y=j+dy[k];
48                         if(x<1||y<1||x>4||y>4)continue;
49                         swap(state[i][j],state[x][y]);
50                         int v=get_hash(state);
51                         if(mp[v]==-1){
52                             q.push(v);
53                             mp[v]=mp[u]+1;
54                         }
55                         swap(state[i][j],state[x][y]);
56                     }
57     }
58     printf("%d\n",mp[e]);
59 }
60 
61 int main(){
62     read_and_parse();
63     solve();
64     return 0;
65 }

 

内容总结

以上是互联网集市为您收集整理的高级算法--广搜全部内容，希望文章能够帮你解决高级算法--广搜所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---