1.6.1 抓住那头牛

刚刚讲了bfs，那下面我们就来搞一个bfs的应用

同样先复习bfs模板。

 

宽度优先遍历
    
        queue<int> q;
        st[1] = true; // 表示1号点已经被遍历过
        q.push(1);

        while (q.size())
        {
            int t = q.front();
            q.pop();

            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (!s[j])
                {
                    st[j] = true; // 表示点j已经被遍历过
                    q.push(j);
                }
            }
        }

这道题目相当于是一个以2的指数级不断扩展的满二叉树，逐渐枚举出所有情况，直到有一次情况满足即可。

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int N = 200010;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int st[N], n, k;
     
    
   

    

     

    
    

     

      int q[N];
     
    
   

    

     

    
    

     

      void bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          memset(st, -1, sizeof st);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    int hh = 0, tt = -1;
     
    
   

    

     

    
    

     
    q[++ tt] = n;
     
    
   

    

     

    
    

     

          st[n] = 0;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    while(hh <= tt)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        int u = q[hh ++];
     
    
   

    

     

    
    

     
        if(u == k)  return;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if(u * 2 <= k * 2 && st[u * 2] == -1)
     
    
   

    

     

    
    

     
            q[++ tt] = u * 2, st[u * 2] = st[u] + 1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if(u + 1 <= k * 2 && st[u + 1] == -1)
     
    
   

    

     

    
    

     
            q[++ tt] = u + 1, st[u + 1] = st[u] + 1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if(u - 1 >= 0 && st[u - 1] == -1)
     
    
   

    

     

    
    

     
            q[++ tt] = u - 1, st[u - 1] = st[u] + 1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          scanf("%d%d", &n, &k);
     
    
   

    

     

    
    

     

          bfs();
     
    
   

    

     

    
    

     
    printf("%d", st[k]);
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

st记录距离

q记录层数

欢迎提问~

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120604909