深度优先搜索的用法——lake counting

问题主题：Lake Counting

问题描述：

有一个大小为N*M的园子，雨后积了很多水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼？(八连通是指下图中相对+的*部分)

+++

+*+

+++

限制条件：

N,M <= 100

样例：

输入

N=10, M=12

园子如下图(‘+’表示积水，’*’表示没有积水)

+****++*

*+++***+++

**++***++*

*****++*

*****+**

**+****+**

*+*+***++*

+*+*+***+*

*+*+****+*

**+*****+*

输出

3

#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;

}

/**
 * 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();
}
}