*[[Problem 287:http://projecteuler.net/index.php?section=problems&id=287]] [#lf65c2c1]
*[[Problem 287:http://projecteuler.net/problem=287]] 「4分木符号化(シンプルな圧縮アルゴリズム)」 [#lf65c2c1]

4分木による符号化を用いて、2&sup{N};×2&sup{N}; の白黒の画像を(0 と 1 の)ビット列で表すことができる。このビット列は左から右へ以下のようにして解読する:
4分木による符号化を用いて, 2&sup{N};×2&sup{N}; の白黒の画像を(0 と 1 の)ビット列で表すことができる. このビット列は左から右へ以下のようにして解読する:

- 最初のビットは 2&sup{N};×2&sup{N}; 全体の領域を表し、
- 最初のビットは 2&sup{N};×2&sup{N}; 全体の領域を表し, 
- "0" は分割を意味する:~
対象の 2&sup{n};×2&sup{n}; の領域を 4 つの 2&sup{n-1};×2&sup{n-1}; の領域に分割し、続くビット列は左上、右上、左下、右下の順で分割された領域を表し、
- "10" は対象の領域が黒いピクセルしか含んでいないことを表し、
- "11" は対象の領域が白いピクセルしか含んでいないことを表す。
対象の 2&sup{n};×2&sup{n}; の領域を 4 つの 2&sup{n-1};×2&sup{n-1}; の領域に分割し, 続くビット列は左上, 右上, 左下, 右下の順で分割された領域を表し, 
- "10" は対象の領域が黒いピクセルしか含んでいないことを表し, 
- "11" は対象の領域が白いピクセルしか含んでいないことを表す.

下の 4×4 の画像について考える(色のついた印はどこで分割が起こるかを表す)

CENTER:
&ref(http://projecteuler.net/project/images/p_287_quadtree.gif);
#ref(http://projecteuler.net/project/images/p_287_quadtree.gif,center,nolink);

この画像はいくつかの文字列で表すことができる、例えば:~
"&color(red){''0''};&color(blue){''0''};10101010&color(green){''0''};1011111011&color(orange){''0''};10101010" は長さ 30 であり、または~
"&color(red){''0''};10&color(green){''0''};101111101110", は長さ 16 であり、これはこの画像を表す最短のビット列である。
この画像はいくつかの文字列で表すことができる, 例えば:~
"&color(red){''0''};&color(blue){''0''};10101010&color(green){''0''};1011111011&color(orange){''0''};10101010" は長さ 30 であり, または~
"&color(red){''0''};10&color(green){''0''};101111101110", は長さ 16 であり, これはこの画像を表す最短のビット列である.

正の整数 N に対し、 D&sub{N}; を次の条件を満たす 2&sup{N};×2&sup{N}; の画像と定義する:
正の整数 N に対し, D&sub{N}; を次の条件を満たす 2&sup{N};×2&sup{N}; の画像と定義する:

- 左下のピクセルを座標 x=0, y=0 とし、
- もし (x-2&sup{N-1};)&sup{2};+(y-2&sup{N-1};)&sup{2}; ≤ 2&sup{2N-2}; ならピクセルは黒とし、
- 他の場合はピクセルは白とする。
- 左下のピクセルを座標 x=0, y=0 とし, 
- もし (x-2&sup{N-1};)&sup{2};+(y-2&sup{N-1};)&sup{2}; ≤ 2&sup{2N-2}; ならピクセルは黒とし, 
- 他の場合はピクセルは白とする.

D&sub{24}; を表す最短のビット列の長さを求めよ。
D&sub{24}; を表す最短のビット列の長さを求めよ.


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS