深度优先搜索的用法——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>