POJ2386:Lake Counting
深度优先搜索:
题意:“W"代表池塘,”.“代表旱地。给出一张地图,问有多少个池塘。(每个正方形被认为与它的八个邻居相邻。)

思路:遍历整个图,遇到"W"就进行深度搜索,把能够搜索到的"W"全部替换为”.",进行了多少次深度搜索就是题目的解。

代码:

package ACM_深搜dfs;

//搜索池塘
import java.util.Scanner;

public class poj2386 {
	static int N, M;
	static String[] s;
	static int vis[][];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			N = in.nextInt();
			M = in.nextInt();
			if (N == 0 && M == 0)
				break;
			s = new String[N];
			vis = new int[N][M];
			int ans = 0;
			for (int i = 0; i < N; i++) {
				s[i] = in.next();
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (s[i].charAt(j) == 'W' && vis[i][j] == 0) {
						ans++;
						dfs(i, j);
					}
				}
			}
			System.out.println(ans);
		}
	}

	private static void dfs(int i, int j) {
		if (i < 0 || i >= N || j < 0 || j >= M || vis[i][j] == 1) {
			return;
		} else if (s[i].charAt(j) == '.') {
			return;
		} else {
			vis[i][j] = 1;
			dfs(i - 1, j + 1);
			dfs(i - 1, j);
			dfs(i - 1, j - 1);
			dfs(i, j + 1);
			dfs(i, j - 1);
			dfs(i + 1, j + 1);
			dfs(i + 1, j);
			dfs(i + 1, j - 1);
		}
	}
}

C++版:

#include<iostream>

using namespace std;

int N,M;
char mapp[101][101];
int nextt[8][2]={//八个方向 
					{ 0, 1}
,					{ 1, 1}
,					{ 1, 0}
,					{ 1,-1}
,					{ 0,-1}
,					{-1,-1}
,					{-1, 0}
,					{-1, 1}
,								};

void dfs(int x,int y)
{

	for(int i=0;i<8;i++)
	{
		int gx=x+nextt[i][0];
		int gy=y+nextt[i][1];
		if(gx>=0 && gx<N && gy>=0 && gy<M && mapp[gx][gy]=='W')
		{
			mapp[gx][gy]='.';    //如果该点是“W”,就修改为“.”,防止重复计数 
			dfs(gx,gy);							
		}
	}	
}

int main()
{
	int count=0;
	cin >> N >> M;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			cin >> mapp[i][j];				
		}
	
	}

	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(mapp[i][j]=='W')
			{
				count++;	
				dfs(i,j);
			}
		}
	}
	cout << count << endl;
	return 0;
}