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