[伯俊]BOJ 1992四叉木JAVA

14260 ワード
アルゴリズム#アルゴリズム# テキストリンク
BOJ 1992四叉木

質問する


白黒ビデオを圧縮することによって表現されるデータ構造である四叉木(Quad Tree)と呼ばれる方法がある.白点を表す0と黒点を表す1からなるビデオ(二次元配列)では、同じ数字の点が一つの場所に集中すると、四叉木で圧縮して簡単に表現できる.
指定されたビデオがすべて0の場合、圧縮結果は「0」、すべてが1の場合、圧縮結果は「1」です.0と1が混在していると、一度に領域全体を表示するのではなく、左上、右上、左下、右下の4つのビデオに分けて圧縮し、この4つの領域の圧縮結果を括弧で囲んで表示します

上図では、左側のビデオは右側の配列のように数字で与えられ、このビデオを四叉木構造で圧縮すると「(0(0011)(0(0111)01)1」と表される.N ×Nサイズのビデオがある場合は、圧縮した結果を出力するプログラムを作成します.

入力


1行目には、画像サイズを表す数字Nが与えられる.Nは常に2の平方数で与えられ,1≦N≦64の範囲である.2行目から、N個の長さの文字列があります.各文字列は0または1の数字で構成され、画像内の各点を表します.

しゅつりょく


圧縮ビデオの結果を出力します.

サンプルI/O



ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int n;
    private static int[][] map;
    private static StringBuilder sb;

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }

        getQuadTree(0, 0, n);
        System.out.println(sb.toString());

    }

    private static void getQuadTree(int row, int col, int size) {

        if (check(row, col, size)) {
            sb.append(map[row][col]);
        } else {
            sb.append("(");

            int half = size / 2;

            /*getQuadTree(row, col, half);
            getQuadTree(row, col + half, half);
            getQuadTree(row + half, col, half);
            getQuadTree(row + half, col + half, half);*/

            for (int i = row; i <= row + half; i += half) {
                for (int j = col; j <= col + half; j += half) {
                    getQuadTree(i, j, half);
                }
            }

            sb.append(")");
        }
    }

    private static boolean check(int row, int col, int size) {
        int temp = map[row][col];

        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (temp != map[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}

Comment


  • 分期征服問題が多ければ多いほど、感じがします.△復帰問題は解決しなければ分からない.
    • デザインモードObserver Pattern
    バックアップ1260:DFSとBFS