大きさがNxMの庭があります。そこに雨が降り、水溜まりができました。
水溜りは8近傍で隣接している場合につながっているとみなします。全部でいくつかの水たまりがあるでしょうか?(8近傍とは、次のWに対する*の部分を指します。)
***
*W*
***
制約 N,M ≦ 100
using System;
namespace Program
{
class Program
{
public static int N = 10; // 庭の広さ(縦)
public static int M = 12; // 庭の広さ(横)
public static int MAX_N = 0;
public static int MAX_M = 0;
public static char[][] field =
{
new []{'W', '.', '.', '.', '.', '.', '.', '.', '.', 'W', 'W', '.'},
new []{'.', 'W', 'W', 'W', '.', '.', '.', '.', '.', 'W', 'W', 'W'},
new []{'.', '.', '.', '.', 'W', 'W', '.', '.', '.', 'W', 'W', '.'},
new []{'.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', 'W', '.'},
new []{'.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', '.', '.'},
new []{'.', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.', '.'},
new []{'.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', 'W', '.'},
new []{'W', '.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', '.'},
new []{'.', 'W', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.'},
new []{'.', '.', 'W', '.', '.', '.', '.', '.', '.', '.', 'W', '.'}
};
public static void dfs(int x = 0, int y = 0)
{
field[x][y] = '.';
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 < N && 0 <= ny && ny < M && field[nx][ny] == 'W')
{
dfs(nx, ny);
}
}
}
}
public static void solve()
{
int res = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (field[i][j] == 'W')
{
dfs(i, j);
res++;
}
}
}
Console.WriteLine(res); // 3
}
public static void Main(string[] args)
{
solve();
}
}
}