Java Bfs 哆啦A梦的时光机

Java中的queue用LinkedList实现
que.poll() 删除 que.peek()；返回队首 que.clear()清空队列 que.offer()插入队列
建立四条边即可传送门

package jisuanke;
import java.util.*;
public class BfsTimeMachine {	public static void main(String[] args) {final int Maxn = (int)4e6 + 5;int[]deep = new int[Maxn];Queue<Integer>que = new LinkedList<Integer>();Scanner cin = new Scanner(System.in);int T = cin.nextInt();for(int i = 0;i < T;i++) {int s = cin.nextInt();int t = cin.nextInt();que.clear();que.offer(s);Arrays.fill(deep, 0);while(!que.isEmpty()) {s = que.peek();que.poll();//System.out.println(111);if(s == t) break;if(s + 1 <= 2000005 && deep[s + 1] == 0){que.offer(s + 1);deep[s + 1] = deep[s] + 1;}if(s - 1 > 0 &&  deep[s -1] == 0 ) {que.offer(s - 1);deep[s - 1] = deep[s] + 1;}if(2 * s <= 2000005 && deep[s * 2] == 0) {que.offer(s * 2);deep[s * 2] = deep[s] + 1;}if(s % 2 == 0 && s != 0 && deep[s / 2] == 0) {que.offer(s / 2);deep[s / 2] = deep[s] + 1;}}System.out.println(deep[t] * 2);}
}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！