結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2016-02-12 04:02:12 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,688 ms / 5,000 ms |
コード長 | 1,088 bytes |
コンパイル時間 | 2,866 ms |
コンパイル使用メモリ | 77,920 KB |
実行使用メモリ | 98,276 KB |
最終ジャッジ日時 | 2024-07-01 07:45:04 |
合計ジャッジ時間 | 18,838 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N; static int ans = Integer.MAX_VALUE; public static void main(String[] args) { Scanner scan = new Scanner(System.in); N = scan.nextInt(); scan.close(); boolean flag[] = new boolean[N+1]; Queue<Node> q = new LinkedList<>(); q.add(new Node(1,1)); while(!q.isEmpty()) { Node v = q.poll(); if(v.number == N) { ans = Math.min(ans, v.steps); continue; } flag[v.number] = true; int nextRight = v.number + (Integer.bitCount(v.number)); if(nextRight <= N && !flag[nextRight]) { q.add(new Node(nextRight, v.steps+1)); } int nextLeft = v.number - (Integer.bitCount(v.number)); if(nextLeft >= 1 && !flag[nextLeft]) { q.add(new Node(nextLeft, v.steps+1)); } } if(ans == Integer.MAX_VALUE) { System.out.println("-1"); } else { System.out.println(ans); } } } class Node { int number; int steps; Node(int number , int steps) { this.number = number; this.steps = steps; } }