Lake Counting(PKU No.2386)
Lake Counting
大きさN×Mの庭がある。庭には水溜りがあり、8近傍で隣接している場合ひとつにつながっていると考える。全部でいくつの水溜りがあるか。(水溜りがあるところがW,水溜りがないところが.となったマップが与えられる。)
制約
アルゴリズム
水溜りがある場所をDFSで探索していく。一度通った場所を.に置換していって、Wがなくなるまで繰り返す。
コード
import java.util.*; public class pku2386 { static Scanner scanner; static char[][] map; public static void main(String[] args) { scanner = new Scanner(System.in); new pku2386(); } pku2386(){ int N = scanner.nextInt(); //height int M = scanner.nextInt(); //width map = new char[N+2][M+2]; //※周りを.で埋めて、番兵的に使う for(int i = 0; i < N+2; i++){ if( i == 0 || i == N+1 ) Arrays.fill(map[i], '.'); else{ String line = scanner.next(); line = "." + line + "."; map[i] = line.toCharArray(); } } System.out.println( solve(N,M) ); } int solve(int N, int M){ int ans = 0; for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ if( map[i][j] == 'W' ){ DFS(i,j); ans++; } } } return ans; } //引数は探索開始位置 void DFS(int i, int j){ map[i][j] = '.'; for(int dy = -1; dy <= 1; dy++){ for(int dx = -1; dx <= 1; dx++){ if( !(dy == 0 && dx == 0) && map[i+dy][j+dx] == 'W' ) DFS(i+dy, j+dx); } } } }