深度優先搜索的用法——lake counting · 算法程序設計

深度優先搜索的用法——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)">問題主題：Lake?Counting</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)">問題描述：有一個大小為N*M的園子，雨后積了很多水。八連通的積水被認為是在一起的。請求出園子里共有多少個水洼？(八連通是指下圖中相對+的*部分)++++*++++限制條件：N,M?<=?100</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)">樣例：輸入N=10,?M=12園子如下圖(‘+’表示積水，’*’表示沒有積水)+****++**+++***+++**++***++******++******+****+****+***+*+***++*+*+*+***+**+*+****+***+*****+*輸出3</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)">?#include?"iostream"?using?namespace?std;?const?int?N?=?10;const?int?M?=?12;?char?garden[N][M+1]?=?{"+****++*","*+++***+++","**++***++*","*****++*","*****+**","**+****+**","*+*+***++*","+*+*+***+*","*+*+****+*","**+*****+*"};?void?dfs(int?x,?int?y);?void?solve()?{int?count?=?0;for(int?j=0;?j<N;?j++)?{for(int?i=0;?i<M;?i++){if(garden[j][i]?==?'+')?{dfs(j,?i);count?++;}}}cout?<<?count?<<?endl;}?void?dfs(int?y,?int?x)?{garden[y][x]?=?'*';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][dx]?==?'+')?{dfs(dy,?dx);}}}}?int?main()?{solve();return?0;}?</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)"><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> </td></tr></tbody></table>