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
--
All Comments