結果

問題 No.3 ビットすごろく
ユーザー fkwnw3_1243fkwnw3_1243
提出日時 2017-05-05 21:53:42
言語 Java21
(openjdk 21)
結果
AC  
実行時間 54 ms / 5,000 ms
コード長 2,289 bytes
コンパイル時間 3,889 ms
コンパイル使用メモリ 76,820 KB
実行使用メモリ 51,064 KB
最終ジャッジ日時 2023-09-14 00:42:40
合計ジャッジ時間 6,850 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
49,752 KB
testcase_01 AC 45 ms
49,540 KB
testcase_02 AC 46 ms
49,732 KB
testcase_03 AC 48 ms
49,656 KB
testcase_04 AC 49 ms
49,624 KB
testcase_05 AC 49 ms
49,760 KB
testcase_06 AC 47 ms
49,932 KB
testcase_07 AC 47 ms
50,000 KB
testcase_08 AC 48 ms
49,788 KB
testcase_09 AC 50 ms
49,476 KB
testcase_10 AC 51 ms
49,640 KB
testcase_11 AC 49 ms
49,644 KB
testcase_12 AC 49 ms
49,928 KB
testcase_13 AC 46 ms
49,576 KB
testcase_14 AC 49 ms
49,636 KB
testcase_15 AC 50 ms
49,692 KB
testcase_16 AC 50 ms
49,720 KB
testcase_17 AC 50 ms
49,704 KB
testcase_18 AC 46 ms
49,612 KB
testcase_19 AC 51 ms
51,064 KB
testcase_20 AC 44 ms
49,492 KB
testcase_21 AC 43 ms
49,532 KB
testcase_22 AC 49 ms
49,488 KB
testcase_23 AC 51 ms
49,748 KB
testcase_24 AC 54 ms
50,656 KB
testcase_25 AC 51 ms
49,612 KB
testcase_26 AC 44 ms
49,556 KB
testcase_27 AC 47 ms
49,600 KB
testcase_28 AC 50 ms
50,028 KB
testcase_29 AC 49 ms
49,488 KB
testcase_30 AC 44 ms
49,532 KB
testcase_31 AC 44 ms
49,576 KB
testcase_32 AC 49 ms
49,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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