読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


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;
  }
};
しょげないでよBaby 眠れば治る