poj3278简单的广搜入门

这道题是一道最基础的广度优先搜索题，需要剪枝，否则超时，剪枝时剪掉已经计算过的数，否则会式计算次数成幂指数增长。广度搜索最基本的思想就是遍历每一层，之后遍历下一层，因此剪枝十分重要。我开始考虑用数组来存放到达y所需步数a[y]，后发现用队列实现更好，由于队列先入先出的特点，所以使用了stl中的队列实现。

stl中队列基本用法：

头文件：

#include
基本函数：

建立队列：queue+队列名;

向队列中(末尾)添加元素：队列名+.push(元素名);

去掉队列头元素：队列名+.pop();

队列头元素：队列名+.front();

返回队尾元素的引用：队列名+.back();

判断是否为空：队列名+.empty();

队列大小：队列名+.size();

代码：

#include
#include
using namespace std;
int a[100001],b[100001];
int main()
{
int m,n,y;
queuex;//建立名为x的队列
cin>>m>>n;
x.push(m);//在队列后加入m
a[m]=0;
while(x.size()!=0)//队列大小不为0
{
  y=x.front();//y取队列首位
  x.pop();//去掉队列首位
  b[y]=1;
  if(y==n)
   break;
  if(y-1>=0&&b[y-1]==0)
  {
   x.push(y-1);
   a[y-1]=a[y]+1;
   b[y-1]=1;
  }
  if(y+1<=100000&&b[y+1]==0)
  {
   x.push(y+1);
   a[y+1]=a[y]+1;
   b[y+1]=1;
  }
  if(2*y<=100000&&b[2*y]==0)
  {
   x.push(2*y);
   a[2*y]=a[y]+1;
   b[2*y]=1;
  }
}
cout< return 0;
}

上面是别人的代码，写的很好。下面是我自己仿写的代码和找的一篇不用stl 的更高效代码

这是自己写的  memory 1196K    time   141Ms

#include
#include
#include
#include
using namespace std;
int a[100001],v[100001];
int main()
{
int n,m,u,i=0,j;
memset(v,0,sizeof(v));
queue x;
scanf("%d%d",&n,&m);
x.push(n);
a[n]=0;
while(!x.empty())
{
  u=x.front();
  x.pop();
  v[u]=1;
  if(u==m)
   break;
  if(u-1>=0&&v[u-1]==0)
  {
   x.push(u-1);
   v[u-1]=1;
   a[u-1]=a[u]+1;
  }
  if(u+1<=100000&&v[u+1]==0)
  {
   x.push(u+1);
   v[u+1]=1;
   a[u+1]=a[u]+1;
  }
  if(2*u<=100000&&v[2*u]==0)
  {
   x.push(2*u);
   v[2*u]=1;
   a[2*u]=a[u]+1;
  }
}
printf("%d\n",a[m]);
return 0;
}

SOU DI不用stl 的算法

memory   980K  time 16Ms

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
bool data[100005] = {0};  
int que[100005] = {0};  
int tnum[100005] = {0};  
void bfs(int n, int k)  
{  
   int frOnt= 0, rear = 0;  
    que[0] = n;  
    data[n] = true;  
    tnum[0] = 0;  
    rear++;  
      
    while (front != rear)  
    {  
        int t = que[front];  
        int tn = tnum[front];  
        if (t == k)  
        {  
            printf("%d\n", tn);  
            return;  
        }  
          
        if (t > 0 && !data[t-1])  
        {  
            data[t-1] = true;  
            que[rear] = t-1;  
            tnum[rear] = tn+1;  
            rear++;  
        }  
          
        if (t <100000 && !data[t+1])  
        {  
            data[t+1] = true;  
            que[rear] = t+1;  
            tnum[rear] = tn+1;  
            rear++;  
        }  
        if (t <= 50000 && !data[t*2])  
        {  
            data[t*2] = true;  
            que[rear] = t*2;  
            tnum[rear] = tn+1;  
            rear++;  
        }  
        front++;  
    }  
    printf("0\n");  
}  
      
int main()  
{  
    int n, k;  
    scanf("%d%d", &n, &k);  
    memset(data, 0, sizeof(data));  
    bfs(n, k);  
    return 0;  
}