public class FoxAndGo2 {
static public int[] dx = { 0, 1, 0, -1 };
static public int[] dy = { 1, 0, -1, 0 };
public struct Point { public int Row, Col; }
public class Group {
public List<Point> Points = new List<Point>();
}
public class WhiteGroup : Group {
public bool IsRemoved;
}
public class SpaceGroup : Group {
public bool IsContainBlack;
}
void dfs(char[][] board, int row, int col, char c, List<Point> points) {
if (c != board[row][col]) return;
points.Add(new Point() { Row = row, Col = col });
board[row][col] = ' ';
for (int i = 0; i < 4; i++) {
int nr = row + dy[i];
int nc = col + dx[i];
if (0 <= nr && nr < board.Length && 0 <= nc && nc < board[nr].Length) {
dfs(board, nr, nc, c, points);
}
}
}
bool IsAdjacent(Point p1, Point p2) {
return Math.Abs(p1.Row - p2.Row) + Math.Abs(p1.Col - p2.Col) <= 1;
}
int CountAdjacentCell(WhiteGroup whites, SpaceGroup spaces) {
int count = 0;
foreach (var space in spaces.Points) {
if (whites.Points.Any(white => IsAdjacent(white, space)))
count++;
}
return count;
}
public int maxKill(string[] _board) {
char[][] board = _board.Select(b => b.ToCharArray()).ToArray();
int ans = 0;
var spaceGroup = new List<SpaceGroup>();
var whiteGroup = new List<WhiteGroup>();
for (int r = 0; r < board.Length; r++) {
for (int c = 0; c < board[r].Length; c++) {
var kind = board[r][c];
if (kind == ' ') continue;
var points = new List<Point>();
dfs(board, r, c, kind, points);
if (kind == '.')
spaceGroup.Add(new SpaceGroup() { Points = points });
else
whiteGroup.Add(new WhiteGroup() { Points = points });
}
}
bool yet = true;
while (yet) {
yet = false;
foreach (var white in whiteGroup) {
if (white.IsRemoved) continue;
var adjacentSpaces = spaceGroup.Where(space => CountAdjacentCell(white, space) > 0).ToArray();
if (!adjacentSpaces.Any()) continue;
if (adjacentSpaces.Count(g => !g.IsContainBlack && g.Points.Count() == CountAdjacentCell(white, g)) <= 1) {
white.IsRemoved = true;
foreach (var space in adjacentSpaces) {
space.IsContainBlack = true;
}
ans += white.Points.Count();
yet = true;
}
}
}
return ans;
}
}