結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-01-13 06:45:47 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 147 ms / 5,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 2,124 ms |
コンパイル使用メモリ | 77,868 KB |
実行使用メモリ | 54,544 KB |
最終ジャッジ日時 | 2024-07-01 07:40:15 |
合計ジャッジ時間 | 7,955 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.*; import java.math.*; import java.io.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(bfs(N)); } static int bfs(int N) { ArrayDeque<Data> queue = new ArrayDeque<Data>(); boolean[] visit = new boolean[N]; queue.add(new Data(1,1)); while(!queue.isEmpty()) { Data tmp = queue.poll(); if(tmp.now == N) return tmp.count; if(visit[tmp.now]) continue; visit[tmp.now] = true; int next = Integer.bitCount(tmp.now); if(tmp.now - next > 0) { queue.add(new Data(tmp.now - next,tmp.count+1)); } if(tmp.now + next <= N) { queue.add(new Data(tmp.now + next,tmp.count+1)); } } return -1; } static class Data { int now; int count; Data(int n, int c) { now = n; count = c; } } }