3 条题解

  • 0
    @ 2025-2-23 14:25:41
    #include <bits/stdc++.h>
    using namespace std;
    // 约翰的位置,牛的位置
    int n, k;
    // dis[i] 表示几分钟能走到 i
    // -1 表示没走过
    int dis[200000 + 5];
    // 用来广搜的队列
    queue<int> q;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> k;
        // 起点入队
        for (int i = 0; i <= 200000; i++)
            dis[i] = -1;
        dis[n] = 0;
        q.push(n);
        // 只要队列非空并且还没走到牛,就继续搜
        while (!q.empty() && dis[k] == -1)
        {
            // 取出队头
            int now = q.front();
            q.pop();
            // 检查队头一步能到的位置
            if (now + 1 <= 200000 &&
                dis[now + 1] == -1)
            {
                dis[now + 1] = dis[now] + 1;
                q.push(now + 1);
            }
            if (now - 1 >= 0 &&
                dis[now - 1] == -1)
            {
                dis[now - 1] = dis[now] + 1;
                q.push(now - 1);
            }
            if (now * 2 <= 200000 &&
                dis[now * 2] == -1)
            {
                dis[now * 2] = dis[now] + 1;
                q.push(now * 2);
            }
        }
        cout << dis[k];
        return 0;
    }
    
    • 0
      @ 2023-6-3 10:38:58
      #include <bits/stdc++.h>
      using namespace std;
      //农夫的位置 n
      //牛的位置 k
      int n, k;
      // i的位置有没有走过
      bool vis[2 * 100000 + 10];
      // i的位置几分钟能到达
      int dis[2 * 100000 + 10];
      queue<int> q;
      int main()
      {
          cin >> n >> k;
      
          //起点入队
          q.push(n);
          vis[n] = true;
          dis[n] = 0;
      
          //开始广搜:只要队列非空并且没到终点,就继续搜
          while (!q.empty() && !vis[k])
          {
              //取出队头
              int now = q.front();
              q.pop();
              //考虑从队头一步能走到哪儿
              // now+1:能走且没走过
              if (0 <= now + 1 && now + 1 <= 200000 && !vis[now + 1])
              {
                  q.push(now + 1);
                  vis[now + 1] = true;
                  dis[now + 1] = dis[now] + 1;
              }
              // now-1
              if (0 <= now - 1 && now - 1 <= 200000 && !vis[now - 1])
              {
                  q.push(now - 1);
                  vis[now - 1] = true;
                  dis[now - 1] = dis[now] + 1;
              }
              // now*2
              if (0 <= now * 2 && now * 2 <= 200000 && !vis[now * 2])
              {
                  q.push(now * 2);
                  vis[now * 2] = true;
                  dis[now * 2] = dis[now] + 1;
              }
          }
          
          cout << dis[k] << "\n";
          return 0;
      }
      
      
      • 0
        @ 2022-11-8 16:26:59
        #include <bits/stdc++.h>
        using namespace std;
        //农夫的位置 n
        //牛的位置 k
        int n, k;
        // i的位置有没有走过
        bool vis[2 * 100000 + 10];
        // i的位置几分钟能到达
        int dis[2 * 100000 + 10];
        //广搜
        queue<int> q;
        void bfs(int st, int ed)
        {
            //广搜初始化
            memset(vis, false, sizeof(vis));
            memset(dis, -1, sizeof(dis));
            while (!q.empty())
                q.pop();
            //起点入队
            q.push(st);
            vis[st] = true;
            dis[st] = 0;
            //开始广搜:只要队列非空并且没到终点,就继续搜
            while (!q.empty() && !vis[ed])
            {
                //取出队头
                int now = q.front();
                q.pop();
                //考虑从队头一步能走到哪儿
                // now+1:能走且没走过
                if (0 <= now + 1 && now + 1 <= 200000 && !vis[now + 1])
                {
                    q.push(now + 1);
                    vis[now + 1] = true;
                    dis[now + 1] = dis[now] + 1;
                }
                // now-1
                if (0 <= now - 1 && now - 1 <= 200000 && !vis[now - 1])
                {
                    q.push(now - 1);
                    vis[now - 1] = true;
                    dis[now - 1] = dis[now] + 1;
                }
                // now*2
                if (0 <= now * 2 && now * 2 <= 200000 && !vis[now * 2])
                {
                    q.push(now * 2);
                    vis[now * 2] = true;
                    dis[now * 2] = dis[now] + 1;
                }
            }
        }
        int main()
        {
            cin >> n >> k;
            bfs(n, k);
            cout << dis[k] << "\n";
            return 0;
        }
        
        • 1

        信息

        ID
        472
        时间
        1000ms
        内存
        128MiB
        难度
        4
        标签
        (无)
        递交数
        153
        已通过
        65
        上传者