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