在photoshop中我們常用的一個功能就是選擇區域，用魔法棒選擇工具點選圖檔上的一個點就會選中跟該點顔色一樣的連續或非連續區域。這是怎麼做到的呢？下面是我用php實生的區域生長算法。
<code><?php</code>
<code>/**</code>
<code> </code><code>* 找到生長區域</code>
<code> </code><code>*</code>
<code> </code><code>* @param array $arr 資料數組</code>
<code> </code><code>* @param array $seed 種子點</code>
<code> </code><code>* @return array</code>
<code> </code><code>*/</code>
<code>function</code> <code>getGrowRegion(</code><code>$arr</code><code>, </code><code>$seed</code><code>, </code><code>$mode</code><code>=4)</code>
<code>{</code>
<code> </code><code>$seed_value</code> <code>= </code><code>$seed</code><code>[</code><code>'value'</code><code>];</code>
<code> </code><code>$queue</code> <code>= </code><code>array</code><code>();</code>
<code> </code><code>$label</code> <code>= </code><code>array</code><code>();</code>
<code> </code><code>if</code> <code>(</code><code>$arr</code><code>[</code><code>$seed</code><code>[</code><code>'y'</code><code>]][</code><code>$seed</code><code>[</code><code>'x'</code><code>]] == </code><code>$seed_value</code><code>)</code>
<code> </code><code>{</code>
<code> </code><code>$queue</code><code>[] = </code><code>$seed</code><code>;</code>
<code> </code><code>$label</code><code>[</code><code>$seed</code><code>[</code><code>'y'</code><code>]][</code><code>$seed</code><code>[</code><code>'x'</code><code>]] = 1;</code><code>// 标記</code>
<code> </code><code>}</code>
<code> </code><code>// 判斷該點4或8個方向上的值,如果未被标記就标記，并加入到隊列中</code>
<code> </code><code>switch</code> <code>(</code><code>$mode</code><code>)</code>
<code> </code><code>case</code> <code>4:</code>
<code> </code><code>default</code><code>:</code>
<code> </code><code>$directions</code> <code>= </code><code>array</code><code>(</code>
<code> </code><code>array</code><code>(-1, 0),</code>
<code> </code><code>array</code><code>(1, 0),</code>
<code> </code><code>array</code><code>(0, -1),</code>
<code> </code><code>array</code><code>(0, 1)</code>
<code> </code><code>);</code>
<code> </code><code>break</code><code>;</code>
<code> </code><code>case</code> <code>8:</code>
<code> </code><code>array</code><code>(0, 1),</code>
<code> </code><code>array</code><code>(-1, -1),</code>
<code> </code><code>array</code><code>(-1, 1),</code>
<code> </code><code>array</code><code>(1, -1),</code>
<code> </code><code>array</code><code>(1, 1),</code>
<code> </code><code>while</code><code>(!</code><code>empty</code><code>(</code><code>$queue</code><code>))</code>
<code> </code><code>$current</code> <code>= </code><code>array_shift</code><code>(</code><code>$queue</code><code>);</code>
<code> </code><code>foreach</code> <code>(</code><code>$directions</code> <code>as</code> <code>$key</code> <code>=> </code><code>$val</code><code>)</code>
<code> </code><code>{</code>
<code> </code><code>$y_idx</code> <code>= </code><code>$current</code><code>[</code><code>'y'</code><code>] + </code><code>$val</code><code>[0];</code>
<code> </code><code>$x_idx</code> <code>= </code><code>$current</code><code>[</code><code>'x'</code><code>] + </code><code>$val</code><code>[1];</code>
<code> </code><code>if</code> <code>(isset(</code><code>$arr</code><code>[</code><code>$y_idx</code><code>][</code><code>$x_idx</code><code>]) && </code><code>$arr</code><code>[</code><code>$y_idx</code><code>][</code><code>$x_idx</code><code>] == </code><code>$seed_value</code> <code>&& !isset(</code><code>$label</code><code>[</code><code>$y_idx</code><code>][</code><code>$x_idx</code><code>]))</code>
<code> </code><code>{</code>
<code> </code><code>$label</code><code>[</code><code>$y_idx</code><code>][</code><code>$x_idx</code><code>] = 1;</code>
<code> </code><code>$queue</code><code>[] = </code><code>array</code><code>(</code><code>'y'</code> <code>=> </code><code>$y_idx</code><code>, </code><code>'x'</code> <code>=> </code><code>$x_idx</code><code>);</code>
<code> </code><code>}</code>
<code> </code><code>}</code>
<code> </code><code>return</code> <code>$label</code><code>;</code>
<code>}</code>
<code>// 生長區域測試</code>
<code>$str</code> <code>= <<<EOT</code>
<code>000000000000000000000000000000</code>
<code>000000000000011100000000000000</code>
<code>000000000000011110000000000000</code>
<code>000000000000111110000000000000</code>
<code>000000000000110111000000000000</code>
<code>000000000001110011000000000000</code>
<code>000000000001111111100000000000</code>
<code>000000000011111111100000000000</code>
<code>000000000011111111110000000000</code>
<code>000000000011000001110000000000</code>
<code>000000000111000000110000000000</code>
<code>000000000111000000111000000000</code>
<code>EOT;</code>
<code>$data</code> <code>= preg_split(</code><code>'/[\r\n]+/'</code><code>, </code><code>$str</code><code>);</code><code>// 切分成行數組</code>
<code>// 處理成二維坐标數組</code>
<code>$arr</code> <code>= </code><code>array</code><code>();</code>
<code>foreach</code> <code>(</code><code>$data</code> <code>as</code> <code>$y</code> <code>=> </code><code>$val</code><code>)</code>
<code> </code><code>$x_len</code> <code>= </code><code>strlen</code><code>(</code><code>$val</code><code>);</code>
<code> </code><code>for</code> <code>(</code><code>$x</code> <code>= 0; </code><code>$x</code> <code>< </code><code>$x_len</code><code>; </code><code>$x</code><code>++)</code>
<code> </code><code>$arr</code><code>[</code><code>$y</code><code>][</code><code>$x</code><code>] = </code><code>$val</code><code>{</code><code>$x</code><code>};</code>
<code>// 設定種子點，這裡取左上角，value是要比對的值</code>
<code>// 這裡的意思就是以左上角為起點，所有值為0的點全部作為要比對的區域</code>
<code>$seed</code> <code>= </code><code>array</code><code>(</code><code>'y'</code> <code>=> 0, </code><code>'x'</code> <code>=> 0, </code><code>'value'</code> <code>=> </code><code>'0'</code><code>);</code>
<code>$result</code> <code>= getGrowRegion(</code><code>$arr</code><code>, </code><code>$seed</code><code>);</code>
<code>// 輸出反轉之後的字元串</code>
<code>foreach</code> <code>(</code><code>$arr</code> <code>as</code> <code>$y</code> <code>=> </code><code>$rows</code><code>)</code>
<code> </code><code>foreach</code> <code>(</code><code>$rows</code> <code>as</code> <code>$x</code> <code>=> </code><code>$val</code><code>)</code>
<code> </code><code>if</code> <code>(isset(</code><code>$result</code><code>[</code><code>$y</code><code>][</code><code>$x</code><code>]))</code>
<code> </code><code>echo</code> <code>$result</code><code>[</code><code>$y</code><code>][</code><code>$x</code><code>];</code>
<code> </code><code>else</code>
<code> </code><code>echo</code> <code>$val</code><code>==1? 0 : 2;</code><code>// 非生長點</code>
<code> </code><code>echo</code> <code>"\n"</code><code>;</code>
運作後的輸出結果如下：
<code>111111111111111111111111111111</code>
<code>111111111111100011111111111111</code>
<code>111111111111100001111111111111</code>
<code>111111111111000001111111111111</code>
<code>111111111111002000111111111111</code>
<code>111111111110002200111111111111</code>
<code>111111111110000000011111111111</code>
<code>111111111100000000011111111111</code>
<code>111111111100000000001111111111</code>
<code>111111111100111110001111111111</code>
<code>111111111000111111001111111111</code>
<code>111111111000111111000111111111</code>
可以看到原來為0的點全換成了1，但圖形中間的點不受影響，我将其标記成了2。
本文轉自 ustb80 51CTO部落格，原文連結：http://blog.51cto.com/ustb80/1569590，如需轉載請自行聯系原作者
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)