[伯俊]1992四叉樹
2675 ワード
質問する
白黒ビデオを圧縮することによって表現されるデータ構造である四叉木(Quad Tree)と呼ばれる方法がある.白点を表す0と黒点を表す1からなるビデオ(二次元配列)では、同じ数字の点が一つの場所に集中すると、四叉木で圧縮して簡単に表現できる.
指定されたビデオがすべて0の場合、圧縮結果は「0」、すべてが1の場合、圧縮結果は「1」です.0と1が混在していると、一度に領域全体を表示するのではなく、左上、右上、左下、右下の4つのビデオに分けて圧縮し、この4つの領域の圧縮結果を括弧で囲んで表示します
上図では、左側のビデオは右側の配列のように数字で与えられ、このビデオを四叉木構造で圧縮すると「(0(0011)(0(0111)01)1」と表される.N ×Nサイズのビデオがある場合は、圧縮した結果を出力するプログラムを作成します.
https://www.acmicpc.net/problem/1992
入力
1行目には、画像サイズを表す数字Nが与えられる.Nは常に2の平方数で与えられ,1≦N≦64の範囲である.2行目から、N個の長さの文字列があります.各文字列は0または1の数字で構成され、画像内の各点を表します.
しゅつりょく
圧縮ビデオの結果を出力します.
入力例1
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
サンプル出力1
((110(0101))(0010)1(0001))
AOJ四叉木反転とは異なり,これは四叉木を圧縮する問題である.
左上,右上,左下,右下の順に出力されるため,配列サイズのn/2を再帰的に探索し続けるため,分割征服を用いる.
さらに,その寸法のすべての要素が同じbool値であるか否かを返す関数を記述した.
華やかで実在しない典型的な虎頭蛇尾問題.
でもcinget()を使用する場合は、常に改行に注意してください.
白黒ビデオを圧縮することによって表現されるデータ構造である四叉木(Quad Tree)と呼ばれる方法がある.白点を表す0と黒点を表す1からなるビデオ(二次元配列)では、同じ数字の点が一つの場所に集中すると、四叉木で圧縮して簡単に表現できる.
指定されたビデオがすべて0の場合、圧縮結果は「0」、すべてが1の場合、圧縮結果は「1」です.0と1が混在していると、一度に領域全体を表示するのではなく、左上、右上、左下、右下の4つのビデオに分けて圧縮し、この4つの領域の圧縮結果を括弧で囲んで表示します
上図では、左側のビデオは右側の配列のように数字で与えられ、このビデオを四叉木構造で圧縮すると「(0(0011)(0(0111)01)1」と表される.N ×Nサイズのビデオがある場合は、圧縮した結果を出力するプログラムを作成します.
https://www.acmicpc.net/problem/1992
入力
1行目には、画像サイズを表す数字Nが与えられる.Nは常に2の平方数で与えられ,1≦N≦64の範囲である.2行目から、N個の長さの文字列があります.各文字列は0または1の数字で構成され、画像内の各点を表します.
しゅつりょく
圧縮ビデオの結果を出力します.
入力例1
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
サンプル出力1
((110(0101))(0010)1(0001))
Concept
AOJ四叉木反転とは異なり,これは四叉木を圧縮する問題である.
左上,右上,左下,右下の順に出力されるため,配列サイズのn/2を再帰的に探索し続けるため,分割征服を用いる.
さらに,その寸法のすべての要素が同じbool値であるか否かを返す関数を記述した.
Code
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int arr[64][64];
bool allSame(int rowS, int colS, int size) {
int check;
bool same = true;
for (int i = rowS; i < rowS + size; i++) {
for (int j = colS; j < colS+size; j++) {
if (i == rowS && j == colS) check = arr[i][j];
else {
if (check != arr[i][j]) {
same = false;
break;
}
}
}
if (!same) break;
}
return same;
}
void quadtree(int rowS, int colS, int size) {
if (allSame(rowS, colS, size)) cout << arr[rowS][colS];
else {
cout << "(";
quadtree(rowS, colS, size / 2);
quadtree(rowS, colS + (size / 2), size / 2);
quadtree(rowS + (size / 2), colS, size / 2);
quadtree(rowS + (size / 2), colS + (size / 2), size / 2);
cout << ")";
}
}
int main() {
int n;
char tmp;
cin >> n;
cin.get();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin.get(tmp);
arr[i][j] = tmp - 48;
}
cin.get();
}
quadtree(0, 0, n);
}
Comment
華やかで実在しない典型的な虎頭蛇尾問題.
でもcinget()を使用する場合は、常に改行に注意してください.
Reference
この問題について([伯俊]1992四叉樹), 我々は、より多くの情報をここで見つけました https://velog.io/@yoonjong/BOJ-쿼드트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol