UVa-11953 : Battleships

問題概要

4近傍でflood fillして池の数を数える問題。

#include <cstdio>
using namespace std;

const int MAX_W = 100;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1};

int W;
char board[MAX_W][MAX_W+1];

void init(){
	scanf("%d ", &W);
	for(int i=0; i<W; i++){
		scanf("%[^\n]%*c", board[i]);
	}
}

void dfs(int y, int x){
	board[y][x] = '.';
	for(int k=0; k<4; k++){
		int ny = y + dy[k], nx = x + dx[k];
		if(0<=ny && ny<W && 0<=nx && nx<W && board[ny][nx] != '.'){
			dfs(ny, nx);
		}
	}
}

int solve(){
	int ans = 0;

	for(int i=0; i<W; i++){
		for(int j=0; j<W; j++)if(board[i][j] == 'x'){
			ans++;
			dfs(i, j);
		}
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);

	for(int i=0; i<T; i++){
		init();
		printf("Case %d: %d\n", i+1, solve());
	}

	return 0;
}