Description:
0,1からなる N x N の配列がある。(N<=512, Nは2冪)
この配列に対し、次のように再帰的にツリーを構成する。
* 配列が全て同じ要素からなるなら、ツリーは(0,その要素)とラベル付けされた子供無しのノードとなる。
* 1つでも異なるなら、ツリーのルートは(1)とラベル付けされたノードとなり、子供に「左上、右上、左下、右下」と四等分した配列から構成したツリーを持つ。
ツリーを図(d)の様に表示し、浅い方から、深さが同じなら左から順番にノードを並べ、ラベルを連結し、二進数として読む。
その値を十六進数で表示せよ。
Answer:
幅優先探索でノードを辿るか、深さ優先での各ノードを列挙し、「配列の大きさ、y座標の小ささ、x座標の小ささ」の辞書式順で並び替える。
探索は、ナイーブに組めば、N^2*log(N)だけの時間がかかるが、N^2で作ることも出来る。
Source: