[yukicoder] No.3 ビットすごろく

全数探索？

No.3 ビットすごろく - yukicoder

競技プログラミングを始めたての頃にこの問題を解いたことがありますが、提出したことはありませんでした。そのときの記事は、

yamakasa3.hatenablog.com

になります。そのときの解き方は隣接行列を使って到達可能かどうかを判定していました。

前回の隣接行列を利用した解き方（未提出）

public class SquareA {
    private int [][]A;
    private int [][]A2;
    public SquareA(int [][]A, int [][]A2) {
        this.A = A;
        this.A2=A2;
    }
    public int[][] getA(){
        int N = A.length;
        int[][] B = new int[N][N];
        for(int i=0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                int sum = 0;
                for(int l = 0; l < N; l++) {
                    sum += A[i][l]*A2[l][j];
                }
                B[i][j] = sum;
            }
        }
        return B;
    }
}
public class BitSugoroku {
    public static void main(String[] args) {
        System.out.println("数字");
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();

        int[] [] A = new int[N] [N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                A[i][j] = 0;
            }
        }
        int L;
        int k;
        for(int i = 0; i < N; i++) {
            k = 0;
            String binary = Integer.toBinaryString(i+1);
            L = binary.length();
            for(int j = 0; j < L; j++) {
                if(binary.substring(j, j+1).equals("1")) {
                    k++;
                }
            }
            if(i + k < N) {
                A[i][i+k] = 1;
            }
            if(i - k >=0) {
                A[i][i-k] = 1;

            }
        }
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(A[i][j]+" ");
            }
            System.out.println();
        }

        SquareA sa = new SquareA(A, A);
        int[][] B = sa.getA();
        System.out.println("配列B");
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(B[i][j]+" ");
            }
            System.out.println();
        }
        if(B[0][N-1] != 0) {
            System.out.println("移動数は3");
        }
        int[][] B1 = new int[N][N];

        System.arraycopy(B,0,B1,0,B.length);
        for(int p = 0; p < N-3; p++) {
            SquareA sa1 = new SquareA(B1, A);
            B1 = sa1.getA();
            System.out.println("配列B1");
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    System.out.print(B1[i][j]+" ");
                }
                System.out.println();
            }
            if(B1[0][N-1] != 0) {
                System.out.println("移動数: "+ (p + 4));
                break;
            }
        }
    }
}

この解き方ではタイムアウトになると思います。

今回は多少知識がついたので、幅優先探索？をつかって解きました。キューを使っているので幅優先探索だと思います。ちょっと自信はないですが。

幅優先探索による解法

マス を二進数に変換し、1の数が移動可能なステップ数[tex; t]となります。

移動後のマスは、 または となります。

ここで、マスを訪問したかどうかの状態を表す配列colorと訪問したマスの距離を表す配列dを使います。また、次に訪問すべきマスをキューに入れます。キューの中身が無くなるか、マスNに訪問したら解答が得られます。

おそらく、定番の問題のような気がします。解くことができて嬉しいです

幅優先探索によるコード

public class Exec0003 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();

        // マスの状態 0: 訪れていない 1: 訪れた
        int []color = new int[N];
        Arrays.fill(color, 0);
        color[0] = 1;

        // 次に訪問すべきマス
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(1);

        // 1からの距離
        int []d = new int[N];
        Arrays.fill(d, 0);
        d[0] = 1;
        while(queue.size() > 0){
            // 訪問しているマス
            int k = queue.poll();
            // 移動可能な距離
            int t = bitNum(k);
            // 移動するマス
            int a1 = k + t;
            int a2 = k - t;
            //System.out.println(a1 + " " + a2);
            if(a1 <= N) {
                if(color[a1 - 1] == 0){
                    color[a1 - 1] = 1;
                    d[a1 - 1] = d[k - 1] + 1;
                    queue.add(a1);
                }
            }
            if(a2 >= 2) {
                if(color[a2 - 1] == 0) {
                    color[a2 - 1] = 1;
                    d[a2 - 1] = d[k - 1] + 1;
                    queue.add(a2);
                }
            }
            if(color[N - 1] == 1) {
                System.out.println(d[N - 1]);
                System.exit(0);
            }

        }
        System.out.println(-1);

    }
    public static int bitNum(int a) {
        int cnt = 0;
        String binary = Integer.toBinaryString(a);
        int l = binary.length();
        for(int j = 0; j < l; j++) {
            if(binary.substring(j, j+1).equals("1")) {
                cnt ++;
            }
        }
        return cnt;
    }
}