Back Jun-1992号(四叉木)

13835 ワード
baekjoon テキストリンク
質問元:https://www.acmicpc.net/problem/1992
質問する

  • 白黒ビデオを圧縮することによって表現されるデータ構造である四叉木(Quad Tree)と呼ばれる方法がある.白点を表す0と黒点を表す1からなるビデオ(二次元配列)では、同じ数字の点が一つの場所に集中すると、四叉木で圧縮して簡単に表現できる.

  • 指定されたビデオがすべて0の場合、圧縮結果は「0」、すべてが1の場合、圧縮結果は「1」です.0と1が混在していると、一度に領域全体を表示するのではなく、左上、右上、左下、右下の4つのビデオに分けて圧縮し、この4つの領域の圧縮結果を括弧で囲んで表示します
  • 上図において、左側のビデオは、右側の配列のように数値的に与えられ、このビデオを四叉木構造で圧縮すると、「(0(0011)(0(0111)01)1」と表される.N ×Nサイズのビデオがある場合は、圧縮した結果を出力するプログラムを作成します.
    • import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        char[][] matrix = new char[N][N];

        for (int i = 0; i < N; i++) {
            matrix[i] = reader.readLine().toCharArray();
        }

        recursive(matrix, N, 0, 0);

        System.out.println(sb);
    }

    private static void recursive(char[][] matrix, int N, int startRow, int startCol) {
        if (N == 1) {
            sb.append(matrix[startRow][startCol]);
            return;
        }

        char check = matrix[startRow][startCol];
        boolean flag = true;

        Outer: for (int i = startRow; i < N + startRow; i++) {
            for (int j = startCol; j < N + startCol; j++) {
                if (matrix[i][j] != check) {
                    flag = false; // 통합 불가
                    break Outer;
                }
            }
        }

        if (flag) {
            sb.append(check);
            return;
        }

        sb.append("(");
        recursive(matrix, N / 2, startRow, startCol);
        recursive(matrix, N / 2, startRow, startCol + N / 2);
        recursive(matrix, N / 2, startRow + N / 2, startCol);
        recursive(matrix, N / 2, startRow + N / 2, startCol + N / 2);
        sb.append(")");
    }

}
  • 基本解答の方法は1074号(Z)と同じである.長方形を4つの長方形に分割し、条件が満たされるまですべての部分を再帰的に処理します.各座標の最初の値をchar配列に保存し、繰り返し文を実行するときに要素が存在する場合はbooleanflagで繰り返しを終了し、矩形分割を再実行します.すべての要素が同じ場合は、長方形の要素を1つに結合してStringBuilderに保存し、終了します.
    • Redisメモリ管理ソース分析
    asp.Netはどのようにピクチャーの上で透かしの文字をプラスします