深度優先搜索的用法——lake?counting
<table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體"><strong>問題主題:</strong></span><span style="font-size:14pt; font-family:'Times New Roman'">Lake?Counting</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p></td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體"><strong>問題描述:</strong></span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:28pt"><span style="font-size:14pt; font-family:宋體">有一個大小為</span><span style="font-size:14pt; font-family:'Times New Roman'">N*M</span><span style="font-size:14pt; font-family:宋體">的園子,雨后積了很多水。八連通的積水被認為是在一起的。請求出園子里共有多少個水洼?</span><span style="font-size:14pt; font-family:'Times New Roman'">(</span><span style="font-size:14pt; font-family:宋體">八連通是指下圖中相對</span><span style="font-size:14pt; font-family:'Times New Roman'">+</span><span style="font-size:14pt; font-family:宋體">的</span><span style="font-size:14pt; font-family:'Times New Roman'">*</span><span style="font-size:14pt; font-family:宋體">部分</span><span style="font-size:14pt; font-family:'Times New Roman'">)</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:28pt"><span style="font-size:14pt; font-family:'Times New Roman'">+++</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:28pt"><span style="font-size:14pt; font-family:'Times New Roman'">+*+</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:28pt"><span style="font-size:14pt; font-family:'Times New Roman'">+++</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體"><strong>限制條件:</strong></span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:28pt"><span style="font-size:14pt; font-family:'Times New Roman'">N,M?<=?100</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p></td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體"><strong>樣例:</strong></span><span style="font-size:14pt; font-family:'Times New Roman'"><strong/></span></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體">輸入</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">N=10,?M=12</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:宋體">園子如下圖</span><span style="font-size:14pt; font-family:'Times New Roman'">(‘+’</span><span style="font-size:14pt; font-family:宋體">表示積水,</span><span style="font-size:14pt; font-family:'Times New Roman'">’*’</span><span style="font-size:14pt; font-family:宋體">表示沒有積水</span><span style="font-size:14pt; font-family:'Times New Roman'">)</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">+****++*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">*+++***+++</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">**++***++*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">*****++*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">*****+**</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">**+****+**</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">*+*+***++*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">+*+*+***+*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">*+*+****+*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">**+*****+*</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:14pt; font-family:宋體">輸出</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'; text-indent:27pt"><span style="font-size:14pt; font-family:'Times New Roman'">3</span><span style="font-size:14pt; font-family:'Times New Roman'"/></p></td></tr></tbody></table>
### 【解法一】
### 解題分析:
???從任意的’+’開始,不停地把鄰接的部分用’*’代替,一次dfs(深度優先遍歷)遍歷后,與初始的這個+所連接的所有+都會被替換成*,因此直到圖中沒有+為止,總共進行dfs的次數即為積水的次數。
### 程序實現:
**C++**
<table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">#include</span><span style="font-size:9.5pt; font-family:新宋體">?</span><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"iostream"</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">using</span><span style="font-size:9.5pt; font-family:新宋體">?</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">namespace</span><span style="font-size:9.5pt; font-family:新宋體">?std;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">const</span><span style="font-size:9.5pt; font-family:新宋體">?</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?N?=?10;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">const</span><span style="font-size:9.5pt; font-family:新宋體">?</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?M?=?12;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">char</span><span style="font-size:9.5pt; font-family:新宋體">?garden[N][M+1]?=?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"+****++*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"*+++***+++"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"**++***++*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"*****++*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"*****+**"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"**+****+**"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"*+*+***++*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"+*+*+***+*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"*+*+****+*"</span><span style="font-size:9.5pt; font-family:新宋體">,</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">"**+*****+*"</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體">;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">void</span><span style="font-size:9.5pt; font-family:新宋體">?dfs(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?x,?</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?y);</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">void</span><span style="font-size:9.5pt; font-family:新宋體">?solve()?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?count?=?0;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">for</span><span style="font-size:9.5pt; font-family:新宋體">(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?j=0;?j<N;?j++)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">for</span><span style="font-size:9.5pt; font-family:新宋體">(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?i=0;?i<M;?i++){</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">if</span><span style="font-size:9.5pt; font-family:新宋體">(garden[j][i]?==?</span><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">'+'</span><span style="font-size:9.5pt; font-family:新宋體">)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">dfs(j,?i);</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">count?++;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">cout?<<?count?<<?endl;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">void</span><span style="font-size:9.5pt; font-family:新宋體">?dfs(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?y,?</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?x)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">garden[y][x]?=?</span><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">'*'</span><span style="font-size:9.5pt; font-family:新宋體">;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">for</span><span style="font-size:9.5pt; font-family:新宋體">(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?dy=y-1;?dy<=y+1;?dy++)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">for</span><span style="font-size:9.5pt; font-family:新宋體">(</span><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?dx=x-1;?dx<=x+1;?dx++)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">if</span><span style="font-size:9.5pt; font-family:新宋體">(dx?>=0?&&?dy?>=?0?&&?dx?<?M?&&?dy?<?N?&&?garden[dy][dx]?==?</span><span style="color:rgb(163,21,21); font-size:9.5pt; font-family:新宋體">'+'</span><span style="font-size:9.5pt; font-family:新宋體">)?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">dfs(dy,?dx);</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">?</span></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">int</span><span style="font-size:9.5pt; font-family:新宋體">?main()?{</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="font-size:9.5pt; font-family:新宋體">solve();</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體"/><span style="color:rgb(0,0,255); font-size:9.5pt; font-family:新宋體">return</span><span style="font-size:9.5pt; font-family:新宋體">?0;</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:9.5pt; font-family:新宋體">}</span><span style="font-size:9.5pt; font-family:新宋體"/></p><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"><span style="font-size:10.5pt; font-family:'Times New Roman'">?</span></p></td></tr></tbody></table>
**Java**
<table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'&#23435;&#20307;'"/><pre code_snippet_id="143244" snippet_file_name="blog_20140105_1_3080505" name="code" class="java">/**
* User: luoweifu
* Date: 14-1-7
* Time: 下午4:53
*/
public class LakeCounting {
public static final int N = 10;
public static final int M = 12;
private String garden[] = {
"+****++*",
"*+++***+++",
"**++***++*",
"*****++*",
"*****+**",
"**+****+**",
"*+*+***++*",
"+*+*+***+*",
"*+*+****+*",
"**+*****+*"
};
public void solve() {
int count = 0;
for(int j=0; j<N; j++) {
for(int i=0; i<M; i++){
if(garden[j].charAt(i) == '+') {
dfs(j, i);
count ++;
}
}
}
System.out.println(count);
}
public void dfs(int y, int x) {
StringBuilder stringY = new StringBuilder(garden[y]);
stringY.setCharAt(x, '*');
garden[y] = stringY.toString();
for(int dy=y-1; dy<=y+1; dy++) {
for(int dx=x-1; dx<=x+1; dx++) {
if(dx >=0 && dy >= 0 && dx < M && dy < N && garden[dy].charAt(dx) == '+') {
dfs(dy, dx);
}
}
}
}
public static void main(String args[]) {
LakeCounting lakeCounting = new LakeCounting();
lakeCounting.solve();
}
}</pre><br/><p/></td></tr></tbody></table>