[伯俊]1992号四叉樹
[伯俊]1992号四叉樹
質問リンク: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サイズのビデオがある場合は、圧縮した結果を出力するプログラムを作成します.
入力
1行目には、画像サイズを表す数字Nが与えられる.Nは常に2の平方数で与えられ,1≦N≦64の範囲である.2行目から、N個の長さの文字列があります.各文字列は0または1の数字で構成され、画像内の各点を表します.
しゅつりょく
圧縮ビデオの結果を出力します.
問題を理解する
これは分割征服問題である.
領域が同じ番号で構成されている場合は、同じ領域とみなされます.だから番号になりました.同じ領域でない場合は、その領域の終わりを(先頭で示す数字)で表します.同じ領域でなければ領域を4つに分ける.
コード実装(C++)
#include <iostream>
#include <string>
using namespace std;
int map[64][64];
bool check(int x, int y, int n){
int temp = map[y][x];
for(int i = y ; i < y+n ; i++){
for(int j = x ; j < x+n ; j++){
if(map[i][j] != temp) return false;
}
}
return true;
}
string divide(int x, int y, int n){
string temp = "";
if(!check(x, y, n)){
temp += "(";
temp += divide(x, y, n/2); //left
temp += divide(x + n/2, y, n/2); // right
temp += divide(x, y + n/2, n/2); //low
temp += divide(x + n/2, y + n/2, n/2); //cross
temp += ")";
return temp;
}
else return temp += to_string(map[y][x]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int num;
string temp;
cin >> num;
for(int i = 0 ; i < num ; i++){
cin >> temp;
for(int j = 0 ; j < num ; j++){
map[i][j] = temp[j] - '0';
}
}
cout << divide(0, 0, num) << "\n";
}
Reference
この問題について([伯俊]1992号四叉樹), 我々は、より多くの情報をここで見つけました
https://velog.io/@kpg0518/백준-1992번-쿼드트리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
#include <string>
using namespace std;
int map[64][64];
bool check(int x, int y, int n){
int temp = map[y][x];
for(int i = y ; i < y+n ; i++){
for(int j = x ; j < x+n ; j++){
if(map[i][j] != temp) return false;
}
}
return true;
}
string divide(int x, int y, int n){
string temp = "";
if(!check(x, y, n)){
temp += "(";
temp += divide(x, y, n/2); //left
temp += divide(x + n/2, y, n/2); // right
temp += divide(x, y + n/2, n/2); //low
temp += divide(x + n/2, y + n/2, n/2); //cross
temp += ")";
return temp;
}
else return temp += to_string(map[y][x]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int num;
string temp;
cin >> num;
for(int i = 0 ; i < num ; i++){
cin >> temp;
for(int j = 0 ; j < num ; j++){
map[i][j] = temp[j] - '0';
}
}
cout << divide(0, 0, num) << "\n";
}
Reference
この問題について([伯俊]1992号四叉樹), 我々は、より多くの情報をここで見つけました https://velog.io/@kpg0518/백준-1992번-쿼드트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol