首页 > 代码库 > ACM-BFS之Open the Lock——hdu1195（双向BFS）
ACM-BFS之Open the Lock——hdu1195（双向BFS）
这道题的初级版本，暴力BFS及题目详情请戳：http://blog.csdn.net/lttree/article/details/24658031
上回书说道，要用双向BFS来尝试一下。
终于AC了，
双向BFS，就是从两个点寻找一个共同的中间点。
然后把各自到这个中间点的步数加起来，及为最短步数。
肯定有人问了，双向BFS有啥好处捏？
鄙人，有图有真相！
单BFS：
双向BFS：
发现了不？
尤其是随着搜索广度的增大，那个范围是相当di啊！
双向BFS做法其实不难，两个队列。
一个从头开始搜，一个从尾开始搜。
但是要注意一点，要逐层搜索，不要逐点搜索呀~
要在 正向的同一层搜索完后，再去搜索反向的相应层！
什么叫逐层搜索呢？
对于这道题而言，VIS数组需要记录到达该点的步数，
对于每层搜索要把，同一步数的点全出队列遍历一遍，再进行反向搜索。
OK，这是对于这道题的双向广搜代码（感觉就是把两个广搜叠起来就OK了）
/**************************************
***************************************
* Author：Tree *
*From ：http://blog.csdn.net/lttree *
* Title : Scrambled Polygon *
*Source: hdu 1195 *
* Hint : 双向BFS *
***************************************
**************************************/
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
struct VIS
{
int flag,step;
}vis[10001];
struct Key
{
int k[4],step;
friend bool operator <(Key a,Key b)
{
return a.step<b.step;
}
};
int ini[4],ans[4],dis[2]={-1,1};
int solu[9]={9,1,2,3,4,5,6,7,8};
bool judge(Key a)
{
for(int i=0;i<4;++i)
if( a.k[i]!=ans[i] )
return false;
return true;
}
// 用来做VIS数组
int total(Key a)
{
int i,sum;
sum=0;
for(i=0;i<4;++i)
sum=sum*10+a.k[i];
return sum;
}
int bfs(void)
{
memset(vis,0,sizeof(vis));
queue <Key> q;
queue <Key> p;
Key pre,lst;
int i,t,sum,sp=0;
// 初始化。。。
for(i=0;i<4;++i)
pre.k[i]=ini[i];
sum=total(pre);
vis[sum].flag=1;
vis[sum].step=0;
pre.step=0;
q.push(pre);
for(i=0;i<4;++i)
lst.k[i]=ans[i];
sum=total(lst);
vis[sum].flag=2;
vis[sum].step=0;
lst.step=0;
p.push(lst);
while( !q.empty() && !p.empty() )
{
// 为了遍历每一层的情况，所以用sp来控制层数
// 正向搜索
while( q.front().step==sp )
{
pre=q.front();
q.pop();
for(i=0; i<4; ++i)
{
if( pre.k[i]!=ans[i] )
{
for(t=0; t<2; ++t)
{
lst=pre;
lst.k[i]=solu[(pre.k[i]+dis[t])%9];
sum=total(lst);
lst.step=pre.step+1;
if( vis[sum].flag==1 ) continue;
if( vis[sum].flag==2 ) return lst.step+vis[sum].step;
vis[sum].flag=1;
vis[sum].step=lst.step;
q.push(lst);
}
}
}
for(i=0; i<3; ++i)
{
lst=pre;
lst.k[i]=pre.k[i+1];
lst.k[i+1]=pre.k[i];
sum=total(lst);
lst.step=pre.step+1;
if( vis[sum].flag==1 ) continue;
if( vis[sum].flag==2 ) return lst.step+vis[sum].step;
vis[sum].flag=1;
vis[sum].step=lst.step;
q.push(lst);
}
}
// 反向搜索
while( p.front().step==sp )
{
pre=p.front();
p.pop();
for(i=0; i<4; ++i)
{
if( pre.k[i]!=ini[i] )
{
for(t=0; t<2; ++t)
{
lst=pre;
lst.k[i]=solu[(pre.k[i]+dis[t])%9];
sum=total(lst);
lst.step=pre.step+1;
if( vis[sum].flag==2 ) continue;
if( vis[sum].flag==1 ) return lst.step+vis[sum].step;
vis[sum].flag=2;
vis[sum].step=lst.step;
p.push(lst);
}
}
}
for(i=0; i<3; ++i)
{
lst=pre;
lst.k[i]=pre.k[i+1];
lst.k[i+1]=pre.k[i];
sum=total(lst);
lst.step=pre.step+1;
if( vis[sum].flag==2 ) continue;
if( vis[sum].flag==1 ) return lst.step+vis[sum].step;
vis[sum].flag=2;
vis[sum].step=lst.step;
p.push(lst);
}
}
++sp;
}
}
int main()
{
int i,s,test;
char c;
cin>>test;
while( test-- )
{
// 输入数据
for(i=0;i<4;++i)
{
cin>>c;
ini[i]=c-‘0‘;
}
for(i=0;i<4;++i)
{
cin>>c;
ans[i]=c-‘0‘;
}
s=bfs();
cout<<s<<endl;
}
return 0;
}
ACM-BFS之Open the Lock——hdu1195（双向BFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。