読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Lake Counting(PKU No.2386)

Lake Counting

大きさN×Mの庭がある。庭には水溜りがあり、8近傍で隣接している場合ひとつにつながっていると考える。全部でいくつの水溜りがあるか。(水溜りがあるところがW,水溜りがないところが.となったマップが与えられる。)
制約
N,M\leq 100

アルゴリズム

水溜りがある場所を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);
			}
		}
	}
}