SRM 593 Div1 Easy HexagonalBoard
問題
正六角形を組み合わせたボードがある(問題文図参照)。
このボードのタテヨコのサイズに対応したvector string boardが与えられる。board[i][j]が'X'の時、対応する正六角形に色を塗るとする。'-'の時は塗らないものとする。隣接する正六角形は異なる色で塗るとすると、色を塗るために最低何色必要か。
やりかた
. 赤
青緑
上のような状態がもっとも色を使う時で、せいぜい3色。これ以上複雑でも3色あれば十分。なのでまず、深さ優先探索にて、色を塗るべき場所でかつ隣接する座標に白、黒、白、黒、、、、と交互に色を塗っていき、もし一度白く塗った座標に、黒を塗ろうとして戻るようなら2色では塗れない(つまり色を塗りたい座標をつなげたグラフが2部グラフになっていない)ので3色必要。
最後まできちんと塗れるなら、2色以下でOK。
2色以下の場合で色を塗るべき場所が隣接していれば2色必要。隣接していなければ1色でOK。
色を塗る座標がないなら0色。
以下ソース。
class HexagonalBoard { public: int col[60][60]; int N, M; vector<string> b; bool dfs(int y, int x, int c){ if(col[y][x] != -2 && col[y][x] != c) return false; if(col[y][x] != -2 && col[y][x] == c) return true; col[y][x] = c; bool ret = true; for(int i = -1; i <= 1; i++){ for(int j = -1; j <= 1; j++){ if(i == j) continue; if(0 <= y + i && y + i < N && 0 <= x + j && x + j < M) if(b[y + i][x + j] == 'X') ret &= dfs(y + i, x + j, -c); } } return ret; } int minColors(vector <string> board) { b = board; N = board.size(), M = board[0].length(); for(int y = 0; y < N; y++) for(int x = 0; x < M; x++) col[y][x] = -2; //2色では塗れなければ3色必要 for(int y = 0; y < N; y++) for(int x = 0; x < M; x++) if(board[y][x] == 'X' && col[y][x] == -2) if(!dfs(y, x, 1)) return 3; //2色で塗れるか for(int y = 0; y < N; y++) for(int x = 0; x < M; x++) for(int i = -1; i <= 1; i++) for(int j = -1; j <= 1; j++) if(i != j && 0 <= y + i && y + i < N && 0 <= x + j && x + j < M) if(board[y][x] == 'X' && board[y + i][x + j] == 'X') return 2; //1色で塗れるか for(int y = 0; y < N; y++) for(int x = 0; x < M; x++) if(board[y][x] == 'X') return 1; return 0; } };
Get up! 明日のSUPER ST@R!