SRM 593 div1 easy: HexagonalBoard

問題

TopCoder Statistics - Problem Statement

解法

4 色定理とかあるので, せいぜい 4 色あれば塗りきれることがわかりますが, 実は今回の場合はせいぜい 3 色あれば塗りきれることがわかります。

例えば n = 4 の場合は, 以下のようにすれば良いです。

RBGR
GRBG
BGRB
RBGR

一番上の辺を RBG を繰り返すように塗って, そこから下は 上, 左と色が異なるように塗ると, OK です。

• 0 色で足りるのは何も塗らない場合
• 1 色で足りるのはどの頂点も隣接していない場合
• 2 色で足りるのは貪欲に頂点の色を入れ替えして OK な場合

で, 以上の場合でダメな場合は 3 が答えになります。

int color[55*55];

bool dfs(int v, int c, const vector<vi>& G) {
    color[v] = c;
    for (int ch : G[v]) {
        if (color[ch] == 0) {
            if (!dfs(ch, -c, G)) return false;
        } else if (color[ch] == c) return false;
    }
    return true;
}

class HexagonalBoard {
public:
    int minColors(vector <string> board) {
        int n = board.size();
        vector<vi> G(n*n);
        bool is0 = true;
        for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) {
            if (board[y][x] == 'X') {
                is0 = false;
                for (int k = 0; k < 6; k++) {
                    int ny = y+dy[k], nx = x+dx[k];
                    if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                    if (board[ny][nx] == 'X') {
                        G[y*n+x].push_back(ny*n+nx);
                    }
                }
            }
        }
        if (is0) return 0;
        bool is1 = true;
        for (int i = 0; i < n*n; i++) if (G[i].size() > 0) is1 = false;
        if (is1) return 1;
        memset(color, 0, sizeof(color));
        for (int i = 0; i < n*n; i++) {
            if (G[i].size() > 0 && color[i] == 0) {
                if (!dfs(i, 1, G)) return 3;
            }
        }
        return 2;
    }
};