现在的位置: 首页 > 综合 > 正文

poj3278解题报告

2018年01月20日 ⁄ 综合 ⁄ 共 926字 ⁄ 字号 评论关闭

题目的要求是求到达目标位置的最少步数,根据题目特点,很显然应该用广度优先搜索来解决。根据广度搜索的特点,广搜最先扫描到得点所需要的步数即为最小步数。

提到最小步数,可能有些人会想到dp或者最短路径,用他们的确可以解决,但是dp明显比较繁琐,且写的不好还容易超时,计算了很多不必要的信息,而最短路径多是用来解决加权图的问题,对于这种最小步数的问题,广度搜索往往是最好的方法之一。下面给出源码:

#include <iostream>
using namespace std;
#define max 100001
long n,k,f[max],d[max];
bool visit[max];
void bfs()
{
  long head,tail,x,y;
  head=tail=0;
  d[0]=n;
  f[n]=0;
  visit[n]=true;
  while(head<=tail)
  {
    x=d[head];
    y=x-1;
    if(y>=0&&!visit[y])
    {
      tail++;
      d[tail]=y;
      f[y]=f[x]+1;
      visit[y]=true;                      
    }
    y=x+1;
    if(y<=max&&!visit[y])
    {
      tail++;
      d[tail]=y;
      f[y]=f[x]+1;
      visit[y]=true;                      
    } 
    y=x*2;
    if(y<=max&&!visit[y])
    {
      tail++;
      d[tail]=y;
      f[y]=f[x]+1;
      visit[y]=true;                      
    }
    if(visit[k])
      break;
    head++;           
  }  
      
}
int main()
{
  int i;
  cin>>n>>k;
  memset(visit,false,sizeof(visit));
  bfs();
  cout<<f[k]<<endl;
  return 0;
}

 

 

 

 

 

【上篇】
【下篇】

抱歉!评论已关闭.