SRM 593 DIV1 easy : HexagonalBoard

問題概要：
6角座標のグラフがvectorで与えられる
グラフは'X'と'-'の二種類の要素からなる
自分はグラフ上の全ての'X'に色を塗る
ただし色を塗る際に6角の一辺が接していて要素が'X'であるような場所はそれぞれ異なる色にしなければならない
最小で何色必要か？

解法：
与えられたグラフは６角なので全て異なる色で塗ったとしても４色が必要となることはない

なので０から３色でそれぞれ考える

彩色数が０の時 : そもそもグラフ上に'X'が存在しない場合

彩色数が１の時 : 'X'のセルに隣接するセルは全て'-'の場合

彩色数が２の時 : 今みている'X'のセルに色０を、隣接する'X'のセルに色１を塗っていく（前の段階ですでに色が付けられている場合は何もしない）
　　　　　　　　 この処理が終わった時、隣接するセル同士が同じ色をもっていない場合

彩色数が３の時 : それ以外の場合

彩色数が２の時に行った処理の結果、隣接するセル同士が同じ色をもつ場合が存在するならばそれらは異なる色にする必要がある
なのでそういった場合には３を返す
そうでないのであれば２色でよかったという事なので２色を返す

コード：

  int dx[] = {-1,+0,+1,+1,+0,-1};
  int dy[] = {+1,+1,+0,-1,-1,+0};


class HexagonalBoard {
public:
  
  int color[MAX];

  void dfs(vvi &G,int cur,int c)
  {
    if(color[cur])return;
    color[cur] = c;
    rep(i,G[cur].size())if(!color[G[cur][i]])dfs(G,G[cur][i],3-c);
  }

  int minColors(vector <string> board) {
    int N = 0;
    int h = board.size(), w = board[0].size();
    int dex = 0,id[h][w];
    rep(i,h)rep(j,w)id[i][j] = inf;
    rep(i,h)rep(j,w)if(board[i][j] == 'X')
      {
	N++;
	id[i][j] = dex++;
      }

    if(N == 0)return 0;

    rep(i,N)color[i] = 0;

    vvi G(N);
    bool one = true;
    
    rep(i,board.size())rep(j,board[i].size())
      {
	if(board[i][j] != 'X')continue;
	rep(k,6)
	  {
	    int nx = j + dx[k];
	    int ny = i + dy[k];
	    if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;	
	    if(board[ny][nx] == 'X')
	      {
		assert(id[i][j] != inf);
		assert(id[ny][nx] != inf);
		G[id[i][j]].push_back(id[ny][nx]);
		one = false;
	      }
	  }
      }

    if(one)return 1;

    rep(i,N)
      {
	if(color[i])continue;
	dfs(G,i,1);
      }

    rep(i,N)rep(j,G[i].size())if(color[i] == color[G[i][j]])
      return 3;

    return 2;
    
  }
};