TopCoder SRM 593, Division 1, Level 1 : HexagonalBoard

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12784&rd=15705

概要

ハニカム構造の盤面があり、いくつかのセルには印がつけてある。
次のようなグラフを考える。

• 印の付いたセルを頂点とする
• 印の付いた二つのセルが辺を共有するとき、その二頂点間に辺を張る

このグラフの彩色数を求めよ。

解法

実際に塗ってみると分かりますが、三色あれば塗ることができます。
3 以下の k について k- 彩色可能かどうかは簡単に求めることができます。

• k = 0 のとき、頂点が存在しなければ可能
• k = 1 のとき、辺が存在しなければ可能
• k = 2 のとき、一つの連結成分について、その内一つの頂点の色を決めると他が確定するので、矛盾が無いか DFS で調べられる
• k = 3 のとき、常に可能

彩色可能となる最小の k が答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

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

class HexagonalBoard
{
public:
	int H, W;
	VS board;

	VVI color;
	
	int minColors( vector <string> board )
	{
		this -> H = board.size();
		this -> W = board[0].size();
		this -> board = board;
		this -> color = VVI( H, VI( W, -1 ) );

		bool res0 = true, res1 = true, res2 = true;

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] == '-' )
				{
					continue;
				}				
				res0 &= false;
				res1 &= paint1( i, j );
				res2 &= paint2( i, j, color[i][j] != -1 ? color[i][j] : 0 );
			}
		}

		if ( res0 )
		{
			return 0;
		}
		if ( res1 )
		{
			return 1;
		}
		if ( res2 )
		{
			return 2;
		}
		return 3;
	}

	bool paint1( const int y, const int x )
	{	
		REP( d, 0, 6 )
		{
			const int ny = y + dy[d];
			const int nx = x + dx[d];
			if ( inside( ny, nx ) && board[ ny ][ nx ] == 'X' )
			{
				return false;
			}
		}
		return true;
	}

	bool paint2( const int y, const int x, const int c = 0 )
	{
		if ( color[y][x] != -1 )
		{
			return color[y][x] == c;
		}
		color[y][x] = c;

		bool res = true;
		REP( d, 0, 6 )
		{
			const int ny = y + dy[d];
			const int nx = x + dx[d];
			if ( inside( ny, nx ) && board[ ny ][ nx ] == 'X' )
			{
				res &= paint2( ny, nx, 1 - c );
			}
		}
		return res;
	}

	bool inside( const int y, const int x ) const
	{
		return 0 <= y && y < H && 0 <= x && x < W;
	}
};