C♯の勉強

C♯4.0 で TopCoder の過去問を解きます。

TopCoder SRM594: FoxAndGo2

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