TopCoder SRM593: HexagonalBoard

最悪なケースでも

1 2 3 1 2 3 ...
 3 1 2 3 1 2 ...
  2 3 1 2 3 1 ...

を置くことで、色の個数は高々３に抑えられる。

したがって２色で交互に深さ優先探索で色分けしていって、失敗したら３を返すようにする。

public class HexagonalBoard {
    static public int[] dx = { -1, 0, 1, 1, 0, -1 };
    static public int[] dy = { 0, -1, -1, 0, 1, 1 };
    static public bool Between(long a, long x, long b) { return a <= x && x < b; }

    bool cover2color(int[,] color, string[] board, int row, int col, int c = 1) {
        if (color[row, col] > 0) {
            if (color[row, col] != c) return false;
            return true;
        }
        color[row, col] = c;
        for (int k = 0; k < 6; k++) {
            int nr = row + dy[k];
            int nc = col + dx[k];
            if (Between(0, nr, board.Length) && Between(0, nc, board.Length)) {
                if (board[nr][nc] == 'X') {
                    if (!cover2color(color, board, nr, nc, c == 1 ? 2 : 1))
                        return false;
                }
            }
        }
        return true;
    }

    public int minColors(string[] board) {
        int N = board.Length;
        int[,] color = new int[N, N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == '-' || color[i, j] > 0) continue;
                if (!cover2color(color, board, i, j))
                    return 3;
            }
        }
        return color.Cast<int>().Max();
    }