poj 2386 水溜まり。
2011/08/28
DFS
java
pku
poj
Javaです。
勉強がてらチャレンジ。探索問題 深さ優先探索(DFS:Depth-First Search)の問題らしい。遷移できなくなるまで調べる。再帰にマッチするらしい。package p2386;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
char[][] cs = new char[n][m];
scanner.skip("\n");
for (int i = 0; i < n; i++) {
// char[] cs2 = new char[m];
cs[i] = scanner.nextLine().toCharArray();
}
System.out.println(solve(cs));
}
/**
* 解く
*
* @param cs
* @return
*/
public static int solve(char[][] cs) {
int c = 0;
for (int y = 0; y < cs.length; y++) {
for (int x = 0; x < cs[y].length; x++) {
if (cs[y][x] == 'W') {
dfs(cs, x, y);
c++;
}
}
}
return c;
}
/**
*
* @param cs
* @param x
* @param y
*/
static void dfs(char[][] cs, int x, int y) {
// 検査済み
cs[y][x] = '.';
/*
* 8方向調べる。水溜まりならそこから調べる。
*/
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx = x + dx;
int ny = y + dy;
if (0 <= nx && nx < cs[y].length && 0 <= ny && ny < cs.length
&& cs[ny][nx] == 'W') {
dfs(cs, nx, ny);
}
}
}
}
}
