TopCoder SRM610: TheMatrix

あらかじめ、市松模様上に色を反転させておく。

すると後は、黒一色の長方形と白一色の長方形の面積の最大値を求める問題になる。

最大の長方形面積を求める問題は \( O(WH) \) の解法があるが、そこまでに頑張らなくても \( O(W^2H^2/4) \) の全探索で十分間に合う。（500ms程度）

public class TheMatrix {
    public int MaxArea(string[] _board) {
        var board = _board.Select(b => b.ToCharArray()).ToArray();
        int H = board.Length;
        int W = board[0].Length;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if ((i + j) % 2 == 0) {
                    board[i][j] = board[i][j] == '1' ? '0' : '1';
                }
            }
        }
        var sum = new int[H + 1, W + 1];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                sum[i + 1, j + 1] = sum[i, j + 1] + sum[i + 1, j] - sum[i, j] + (board[i][j] == '1' ? 1 : 0);
            }
        }

        int ans = 0;

        for (int sy = 0; sy < H; sy++) {
            for (int ty = sy; ty < H; ty++) {
                for (int sx = 0; sx < W; sx++) {
                    for (int tx = sx; tx < W; tx++) {
                        int area = (ty - sy + 1) * (tx - sx + 1);
                        int count = sum[ty + 1, tx + 1] - sum[sy, tx + 1] - sum[ty + 1, sx] + sum[sy, sx];
                        if (count == 0 || area == count) {
                            ans = Math.Max(ans, area);
                        }
                    }
                }
            }
        }

        return ans;
    }
}