在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=)