首页 > 其他 > 详细

codeforces two buttons

时间:2021-08-06 23:58:18      阅读:23      评论:0      收藏:0      [点我收藏+]
import java.util.*;

public class Main {
    static int[] vis = new int[100005];
    static int[] dis = new int[100005];

    static int n;
    static int m;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        if (n > m) {
            System.out.printf("%d%n", n-m);
            return;
        }

        Arrays.fill(vis, 0);
        Arrays.fill(dis, 0);

        bfs();
    }

    public static void bfs() {
        Deque<Integer> que = new LinkedList<>();
        // Deque是接口,既可以做为栈,又可以作为队列,取决于调用的API

        que.offer(n);
        vis[n] = 1;
        dis[n] = 0;

        while(!que.isEmpty()) {
            int tmp = que.poll();

            if (tmp == m) {
                System.out.printf("%d%n", dis[tmp]);
                return ;
            } else {
                // n-1
                if (tmp-1 > 0 && vis[tmp-1] == 0) {
                    vis[tmp-1] = 1;
                    que.offer(tmp-1);
                    dis[tmp-1] = dis[tmp] + 1;

                }

                // n*2
                if (tmp <= m && vis[tmp*2] == 0) {
                    vis[tmp*2] = 1;
                    que.offer(tmp*2);
                    dis[tmp*2] = dis[tmp] + 1;
                }

                // n+1
                if (tmp+1 <= m && vis[tmp+1] == 0) {
                    vis[tmp+1] = 1;
                    que.push(tmp+1);
                    dis[tmp+1] = dis[tmp] + 1;
                }
            }
        }
    }
}

 

codeforces two buttons

原文:https://www.cnblogs.com/xiazhenbin/p/15110578.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!