TopCoder SRM517 Div1Hard

問題

真っ白な長方形のグリッドに対して次の操作ができる。「ある行か列を選んで、好きな色で全部塗りつぶす」白く塗ることはできない。すでに塗ってあるところの色は変わる。目標の状態にするには最低何回操作する必要があるか？

解法

ある行や列に対して、複数回の操作をする必要がないことは明らか。また、すべての行、列に対して操作をする必要はない（一番最初に塗ったものが無駄になる）。
すると、操作をされない（垂直方向の操作ですべて塗られる）列がある。
それを最初に決めると、垂直方向にどのように塗ったかがわかる。他の列に対して調べると、その列と、各行で、どちらが先に塗られたかがわかる。前後関係をグラフにして、サイクルがないかチェックすればよい。これを、行と列を入れ替えてまた行う。

コード

#include <vector>
#include <string>

using namespace std;

class ColorfulBoard
{
public:
	bool graph[100][100];
	int sz;
	bool visited[100];
	
	bool visit(int p, int q)
	{
		if(p==q&&visited[p]) return true;
		if(visited[p]) return false;
		visited[p] = true;
		for(int i=0;i<sz;i++) if(graph[p][i]&&visit(i, q)) return true;
		return false;
	}
	
	bool check()
	{
		for(int i=0;i<sz;i++){
			for(int j=0;j<sz;j++) visited[j] = false;
			if(visit(i,i)) return false;
		}
		return true;
	}
	
	int test(vector<string> in)
	{
		int W = in.size(), H = in[0].size();
		sz = W+H;
		
		int R = 100000;
		for(int i=0;i<W;i++){
			//in[i] is covered without painting this row
			int ret = H;
			
			for(int j=0;j<H+W;j++){
				for(int k=0;k<H+W;k++) graph[j][k] = false;
			}
			
			for(int j=0;j<W;j++) if(in[i]!=in[j]){
				ret++;
				
				char difC = '.';
				for(int k=0;k<H;k++){
					if(in[j][k] != in[i][k]){
						if(difC=='.' || difC==in[j][k]) difC = in[j][k];
						else difC = '!';
					}
				}
				
				if(difC=='!') goto nex;
				
				for(int k=0;k<H;k++){
					if(in[j][k] == in[i][k]){
						if(in[j][k]!=difC) graph[k+W][j] = true;
					}else{
						graph[j][k+W] = true;
					}
				}
			}
			
			/*for(int j=0;j<sz;j++){
				for(int k=0;k<sz;k++) printf("%d ", graph[j][k]);
				puts("");
			}
			puts("");*/
			if(check()) R = min(R, ret);
nex:
			continue;
		}
		
		return R;
	}
	
	int theMin(vector<string> board)
	{
		int ret = 100000;
		ret = min(ret, test(board));
		
		vector<string> b2;
		for(int i=0;i<board[0].size();i++){
			string s;
			for(int j=0;j<board.size();j++) s.push_back(board[j][i]);
			b2.push_back(s);
		}
		
		//for(int i=0;i<b2.size();i++) printf("%s\n", b2[i].c_str());
		//printf("%d\n", test(b2));
		ret = min(ret, test(b2));
		
		if(ret>1000) return -1;
		return ret;
	}
};