※ 引述《timeregorge (vincent)》之銘言:
: http://imgur.com/JrrL7NU
: 小弟練習一個例題
: 這個例題的目的是計算陸地的尺寸
: 但不重複計算
: 我左看右看完全不知道他到底是如何計算的
: 或是為什麼在if那邊要用[y] [x] != 'land'
: 等等的
: 請問有人可以完整的幫我解釋一下嗎?
: 謝謝您!
這例題還蠻有趣的。
首先 contient_size 函式包含了 world, x, y 這三個參數,
表示它會讀入一個地圖跟一組 (x, y) 座標,之所以會需要這組座標,
是因為此函式並不是計算地圖的"全部"陸地尺寸,而是計算在給定的座標上,
所存在的"相連"陸地尺寸。舉例來說 contient_size(world, 5, 5) 就是計算
在 (5, 5) 座標上的相連陸地尺寸。
問題麻煩的地方就在於如何計算"相連"的陸地,這邊的做法是採用遞迴,
最常用來介紹遞迴的例子就是費式數列:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n - 1) + Fib(n - 2)
藉由把 Fib(n) 分解成 Fib(n - 1) + Fib(n - 2),直到 n == 0 或 1 再加總起來。
計算相連的陸地的算法也是類似,假設想計算 (x, y) 座標的陸地,可以先算出周圍
陸地的尺寸,再把結果跟它本身加總起來:
(x - 1, y + 1) | (x, y + 1) | (x + 1, y + 1)