[NWPU2016][寒假作业][正常版第三组]搜索和二分 N-白红宇

[NWPU2016][寒假作业][正常版第三组]搜索和二分 N

阅读量：5312 次

发布时间：2019-06-14

本文共 967 字，大约阅读时间需要 3 分钟。

题意，一条数轴上，告诉你起点和终点，只能向前走1，向后走1，或者走到二倍的现在的位置，每次都耗时一分钟。问从起点到终点的最短时长。

简单地bfs

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #define inf 0x7fffffffusing namespace std;int n,k,a[1000010],flag[1000010];int bfs(){ queue
               
                 q; q.push(n); while(q.size()){ int p=q.front(); q.pop(); if(p==k) break; for(int i=0;i<3;i++) { if(!i&&p>0&&!flag[p-1]) { q.push(p-1); a[p-1]=a[p]+1; flag[p-1]=1; } if(i==1&&!flag[p+1]&&p+1<1000010) { q.push(p+1); a[p+1]=a[p]+1; flag[p+1]=1; } if(i==2&&!flag[p*2]&&p*2<1000010) { q.push(p*2); a[p*2]=a[p]+1; flag[p*2]=1; } } } return a[k];}int main(){ while(scanf("%d%d",&n,&k)!=EOF) { memset(a,0,sizeof(a)); memset(flag,0,sizeof(flag)); printf("%d\n",bfs()); } return 0;}

一定要flag数组，因为很有可能好几种走法都能到达终点，导致，终点被加了好几次。而最先走到的，肯定是最短的。还有每次走的时候都要判断有没有越界。。因为这个RE两次。

转载于:https://www.cnblogs.com/GeniusYang/p/5186333.html

你可能感兴趣的文章