Baekjun-Z[java]

質問元:https://www.acmicpc.net/problem/1074

問題の説明

1つの数の大きさは2 Nです× 2 Nの2次元配列をZ形状として探索する.たとえば、2×2左上、右上、左下、右下の順にアクセスしてZ形に並べます.

Nが与えられた場合、プログラムを記述し、r行c列に何回目のアクセスを出力する.
以下、N=2の場合の例を示す.

以下に、N=3の場合の例を示す.

入力
第1行は整数N,r,cを与える.
しゅつりょく
数回目のアクセスr行c列を出力します.
制限

1 ≤ N ≤ 15

0 ≤ r, c < 2N

入力例
2 3 1
サンプル出力
11
入力例
3 7 7
サンプル出力
63
入力例
10 511 511
サンプル出力
262143

問題を解く

import java.io.*;
import java.util.Arrays;

class Main {

    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = (int) Math.pow(2, input[0]);
        int r = input[1];
        int c = input[2];
        findOrder(r, c, N * N);
        System.out.println(count);
        br.close();
    }

    public static void findOrder(int r, int c, int size) {

        if(size == 1) {
            return;
        } else {
            if(r < size / 2 && c < size / 2) {
                findOrder(r, c , size / 2);
            } else if(r < size / 2 && c >= size / 2) {
                count += size * size / 4;
                findOrder(r, c - size / 2, size / 2);
            } else if(r >= size / 2 && c < size / 2) {
                count += size * size / 4 * 2;
                findOrder(r - size / 2, c, size / 2);
            } else {
                count += size * size / 4 * 3;
                findOrder(r - size / 2, c - size / 2, size / 2);
            }
        }
    }
}

解答方法

上図を参照して、4分間のナビゲーション再帰呼び出しを行い、到着位置の数字を探せばよい.
ex) 3, 7, 7
N = 3
検索する場所row 7、col 7
Nが3の場合,rowとcolの長さはそれぞれ8である.2^3 X 2^3.
最初の再帰呼び出しではrow 7とcol 7のsize/2が4より大きいためcount+=48(size 8 x 8/4 x 3)となり、rowとcolの値からサイズ8/2の4を減算し、サイズ8を半減する.
2番目の再帰呼び出しrow 3、row 3のsize/2はいずれも2より大きいためcount+=12(size 4 x 4/4 x 3)であり、rowとcolの値はsize 4/2の2を減算し、size 4を半減する.
3番目の再帰呼び出しrow 1、row 1は、size/2の両方が1より大きいためcount+=3(size 2 x 2/4 x 3)となり、rowとcolの値からsize 2/2の1を減算してsize 2を半減する.
sizeが1になり、関数呼び出しが終了します.
count=63出力.