2 条题解

  • 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
      难度
      5
      标签
      (无)
      递交数
      147
      已通过
      62
      上传者