結果

問題 No.3 ビットすごろく
コンテスト
ユーザー fkwnw3_1243
提出日時 2017-05-05 21:53:42
言語 Java
(openjdk 23)
結果
AC  
実行時間 61 ms / 5,000 ms
コード長 2,289 bytes
コンパイル時間 3,565 ms
コンパイル使用メモリ 81,788 KB
実行使用メモリ 37,632 KB
最終ジャッジ日時 2024-07-01 08:42:23
合計ジャッジ時間 5,359 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import static java.lang.System.in;
import static java.lang.System.setOut;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        int N = Integer.parseInt(reader.readLine());
        int[] table = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            table[i] = Integer.MAX_VALUE;
        }

        Queue<Cell> queue = new LinkedList<>();
        Cell first = new Cell(1, 1);
        queue.add(first);
        boolean[] visited = new boolean[N + 1];
        while (!queue.isEmpty()) {
            Cell cell = queue.poll();
            if (cell.position == N) {
            } else {

                int numOfOne = Integer.bitCount(cell.position);

                int nextPosition = cell.position + numOfOne;
                int prevPosition = cell.position - numOfOne;

                if (canMove(nextPosition, N, visited)) {
                    queue.add(new Cell(nextPosition, cell.cost + 1));
                    visited[nextPosition] = true;
                }
                if (canMove(prevPosition, N, visited)) {
                    queue.add(new Cell(prevPosition, cell.cost + 1));
                    visited[prevPosition] = true;
                }
            }
            table[cell.position] = Math.min(table[cell.position], cell.cost);
        }

        if (table[N] != Integer.MAX_VALUE) {
            System.out.println(table[N]);
        } else {
            System.out.println(-1);
        }

    }

    private static boolean canMove(int position, int N, boolean[] visited) {
        if (position < 1 || position >= N + 1 || visited[position]) {
            return false;
        } else {
            return true;
        }
    }
}

class Cell {

    int position;
    int cost;

    public Cell(int position, int cost) {
        this.position = position;
        this.cost = cost;
    }

    @Override
    public String toString() {
        return "Cell{" +
                "position=" + position +
                ", cost=" + cost +
                '}';
    }
}
0