SRM 593 Div1 250 HexagonalBoard

2013-10-06

18:08 |

縦横 N 個の蜂の巣状のマスがあり、いくつかに印がついている。隣り合った印は違う色で塗りたい。最低何色必要か求めよ。
1≦N≦50

左上から色を決めていく（間違い）
各マスの色は、その左、左上、右上に使われている色のどれとも違う色にする
提出
嫌な予感がする
U 字状に印が繋がってた場合、一番下で合流するまで上端右側の色は決められないのでだめだ
これはあかんやつや

wikipediaとかで調査。どうも一般グラフの効率的な彩色アルゴリズムはないっぽい
蜂の巣状というのがヒントかも
全部に印がある場合、3色で塗れる

1 2 3 1 2 3
 3 1 2 3 1 2
  2 3 1 2 3 1
   ....

というわけで答えは0,1,2,3色のどれかなので泥臭く決めるのだろう
印がなければ0色
edgeがなければ1色
2色で済む場合は、DFSして交互に決めていけば色は自動的に決まる。
具体的には、グラフが森の場合と、閉路はあるんだけどすでに訪れたとこの色が自動的に決まる色と一致している場合。

// 左上の 1 から DFS 開始
- 1 ?
 2 - ?
  1 ? -
↓ 1に戻ってきたけど2の隣なので1で良かった、結果オーライ！的な
- 1 2
 2 - 1
  1 2 -

戻ってきた時に第3の色が必要なら return 3, そういうことが無かった場合は使った色数を返す。
ていうのを実装。なんかコードが汚い。75.97点。
accepted

vector <string> B;
VVI vis;
ll ans;
int N;
class HexagonalBoard {
	public:
	void dfs(int x, int y, int col) {
		if(vis[y][x]) {
			if(vis[y][x]!=col) {ans=3;return;}
			return;
		}
		vis[y][x]=col;
		int dx[] = {-1,0,1,1,0,-1};
		int dy[] = {0,-1,-1,0,1,1};
		REP(i, 6) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(0<=nx&&nx<N && 0<=ny&&ny<N && B[ny][nx]=='X') dfs(nx, ny, col==1?2:1);
		}
	}
	
	int minColors(vector <string> BB) {
		B=BB;
		N=B.size();
		vis = VVI(N, VI(N));
		ans = 0;
		REP(y, N) REP(x, N) {
			if(!vis[y][x] && B[y][x]=='X') dfs(x, y, 1);
			if(ans==3) return 3;
		}
		REP(y, N) REP(x, N) {
			ans=max(ans, vis[y][x]);
		}
		//cout<<w<<endl;
		return ans;
	}
};