#BOJ 1992四樹
2211 ワード
🎨四叉木
( https://www.acmicpc.net/problem/1992 )시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 24694 15093 11818 60.559%
質問する
白黒ビデオを圧縮することによって表現されるデータ構造である四叉木(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の数字で構成され、画像内の各点を表します.
しゅつりょく
圧縮ビデオの結果を出力します.
入力例1
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
サンプル出力1
((110(0101))(0010)1(0001))
インプリメンテーション
/*
BOJ : https://www.acmicpc.net/problem/1992
Recurssive, Divide & Conquer 쿼드트리
Versatile0010
*/
#include <bits/stdc++.h>
using namespace std;
int pixel[100][100];
bool isitSame(int x, int y, int n)
{
for (int i = x; i < x + n; i++)
for (int j = y; j < y + n; j++)
if (pixel[i][j] != pixel[x][y]) return false;
return true;
}
void solve(int x, int y, int z)
{
if (isitSame(x, y, z))
{
if (pixel[x][y] == 0) cout << '0';
else cout << '1';
return;
}
int n = z / 2; // 반으로 쪼갠다.
cout << '(';
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++) // 4개 구역에 대해서
{
solve(x + i * n, y + j * n, n);
}
}
cout << ')';
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf_s("%1d", &pixel[i][j]);
solve(0, 0, n);
return 0;
}
Github : https://github.com/versatile0010
Reference
この問題について(#BOJ 1992四樹), 我々は、より多くの情報をここで見つけました
https://velog.io/@versatile0010/BOJ-1992-쿼드트리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 24694 15093 11818 60.559%
/*
BOJ : https://www.acmicpc.net/problem/1992
Recurssive, Divide & Conquer 쿼드트리
Versatile0010
*/
#include <bits/stdc++.h>
using namespace std;
int pixel[100][100];
bool isitSame(int x, int y, int n)
{
for (int i = x; i < x + n; i++)
for (int j = y; j < y + n; j++)
if (pixel[i][j] != pixel[x][y]) return false;
return true;
}
void solve(int x, int y, int z)
{
if (isitSame(x, y, z))
{
if (pixel[x][y] == 0) cout << '0';
else cout << '1';
return;
}
int n = z / 2; // 반으로 쪼갠다.
cout << '(';
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++) // 4개 구역에 대해서
{
solve(x + i * n, y + j * n, n);
}
}
cout << ')';
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf_s("%1d", &pixel[i][j]);
solve(0, 0, n);
return 0;
}
Reference
この問題について(#BOJ 1992四樹), 我々は、より多くの情報をここで見つけました https://velog.io/@versatile0010/BOJ-1992-쿼드트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol