Projecteuler (287) Quadtree - 拼圖

ProjectEuler (287) Quadtree

http://projecteuler.net/index.php?section=problems&id=287

所謂的 Quadtree 編碼可以將一個 2^N x 2^N 的黑白影像編成一系列的位元。

這個序列如下解讀:

* 第一個位元表示整個 2^N x 2^N 影像：
* 若它是 0 則表示分割，將整個 2^N x 2^N 切成相等的 2^(N-1) x 2^(N-1) 四塊，
接下來的序列依序為左上、右上、左下、右下的編碼；
* 若它是 10 則表示這整塊是黑色；
* 若它是 11 則表示這整塊是白色。

例如下面的圖案:

■■■□
■■□■
□□■■
□□■■

它可以由不只一個序列描述，像是: (見右圖分割)
■■■□
001010101001011111011010101010，長度為30，或是 ■■□■
□□■■
0100101111101110，長度是16，也是這個圖案的最短長度。 □□■■


對一個正整數 N，定義 D_N 是以下描述的 2^N x 2^N 圖案：

* 座標 x=0, y=0 代表左下角的點；
* 對某點 (x,y) 若 (x-2^(N-1))^2 + (y-2^(N-1))^2 ≦ 2^(2N-2) 則該點是黑色；
否則該點是白色。

求出 D_24 的最短長度。

--
既然這才是本週的題目就一起貼吧

是說我和 utomaya 在上一題的推文中討論這一題還討論得頗開心 XDrz

--
'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513

--