TopCoder SRM 590: FoxAndGo

問題文

全探索。

public class FoxAndGo {
    static public int[] dx = { 0, 1, 0, -1 };
    static public int[] dy = { 1, 0, -1, 0 };

    public int FloodFill(char[][] board, int x, int y, ref bool existEmpty){
        if(board[y][x] != 'o') return 0;
        board[y][x] = 'x';
        int val = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            var row = board.ElementAtOrDefault(ny);
            if (row == null) continue;
            var c = row.ElementAtOrDefault(nx);
            if (c == '.') existEmpty = true;
            if (c == 'o') {
                val += FloodFill(board, nx, ny, ref existEmpty);
            }
        }
        return val + 1;
    }

    public int CountRemoveCell(char[][] board) {
        int n = board.Length;
        int total = 0;
        foreach(var x in Enumerable.Range(0, n))
            foreach (var y in Enumerable.Range(0, n)) {
                if (board[y][x] == 'o') {
                    bool existEmpty = false;
                    int value = FloodFill(board, x, y, ref existEmpty);
                    if (!existEmpty)
                        total += value;
                }
            }

        return total;
    }

    public int maxKill(string[] board) {
        int ans = CountRemoveCell(board.Select(s => s.ToCharArray()).ToArray());
        int n = board.Length;
        foreach(var x in Enumerable.Range(0, n))
            foreach (var y in Enumerable.Range(0, n)) {
                var array = board.Select(s => s.ToCharArray()).ToArray();
                if (array[y][x] == '.') {
                    array[y][x] = 'x';
                    ans = Math.Max(ans, CountRemoveCell(array));
                    array[y][x] = '.';
                }
            }

        return ans;
    }
}