[伯俊]1780-用紙数(java)

質問する
N×nサイズのマトリクスで表される紙があります.紙の各格には-1,0,1の3つの値の1つが格納されている.このマトリクスを適当な大きさに切ります.このとき、以下の規則に従って切ります.

紙が同じ数であれば、そのままこの紙を使います.

(1)でなければ、用紙を9個の同じ大きさの用紙に切り、各用紙に対して(1)の過程を繰り返す.

このように紙を切る場合は、-1のみで充填された紙の個数、0で充填された紙の個数、1で充填された紙の個数を求めるプログラムを作成してください.
入力
第1行はN(1≦N≦37,Nは3^k)を与える.次のN行は、N個の整数から行列を与える.
しゅつりょく
1行目-1充填の用紙数、2行目0充填の用紙数、3行目1充填の用紙数を出力します.
入力例

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

サンプル出力

10
12
11

コード#コード#

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

public class Main {
    static int[][] num;
    static int[] cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        num = new int[N][N];
        cnt = new int[3];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                num[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        divide(0, 0, N);

        bw.write(cnt[0] + "\n");
        bw.write(cnt[1] + "\n");
        bw.write(cnt[2] + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean check(int row, int col, int len) {
        int tmp = num[row][col];
        for (int i = row; i < row + len; i++) {
            for (int j = col; j < col + len; j++) {
                if (tmp != num[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void divide(int row, int col, int len) {
        if (check(row, col, len)) { // 같은 수로 되어 있을 때
            cnt[num[row][col] + 1]++;
        } else {    // 같은 수로 되어있지 않을 때
            int newLen = len / 3;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    divide(row + newLen * i, col + newLen * j, newLen);
                }
            }
        }
    }
}

整理する

알고리즘
1. 모두 같은 수로 되어 있다면 cnt 값을 증가시킨다.
2. 아닌 경우에는 3으로 나눈 후, 각 범위마다 (1)의 과정을 반복한다.