TopCoder SRM 559 Div2 Hard ToyTrain

Div2 Hardが面白そうなので解いてみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12177

レールの部品を組み合わせてループを作った場合、いくつかコストを払わないと通れないマスがあるのでコストを最小化する問題。

90度回るレールは４方向を向けるため、一見適切な方向にレールを回転させて最小のコストを探索する問題に見える。
ただ、空白地点に追加できるレールは直線レールだけなので、一部レールは自明に決まることがわかる。
たとえば左上角にあるレールは自然に右・下向けのレールになる。

…ここでhttp://apps.topcoder.com/wiki/display/tc/SRM+559:Editorialを見ると、実は全レールの向きは一意に決まることがわかる。
ある１列を左から見た場合、途中でAが来たらそのあとBが来なくてはならず、Bが来たら次はAでなければならない。
各列について、AとBがペアになるように配線されている必要がある。

また、縦方向も同様にAとBをペアにして配線していく。
結果、縦も横も配線されるので、向きは確定される。
あとは、縦線と横線が重なる点が無いことを確認し、通った点のコストを加算すればよい。
ループは複数できても良いので、そこは特に考慮しない。

class ToyTrain {
	public:
	int R,C;
	char str[60][60];
	char rail[60][60];
	int use[10];
	int getMinCost(vector <string> field) {
		int i,x,y,c;
		R=field.size();
		C=field[0].size();
		FOR(y,R) strcpy(str[y],field[y].c_str());
		
		ZERO(rail);
		ZERO(use);
		//横
		FOR(y,R) {
			c=0;
			FOR(x,C) {
				if(str[y][x]=='A') {
					if(c==1) return -1;
					rail[y][x] = 1;
					c=(c==0)?1:0;
				}
				else if(str[y][x]=='B') {
					if(c==2) return -1;
					rail[y][x] = 1;
					c=(c==0)?2:0;
				}
				else if(c!=0) {
					rail[y][x] = 1;
					if(str[y][x]>='1' && str[y][x]<='9') use[str[y][x]-'0']=1;
				}
				
			}
			if(c!=0) return -1;
		}
		
		//縦
		FOR(x,C) {
			c=0;
			FOR(y,R) {
				if(str[y][x]=='A') {
					if(c==1) return -1;
					rail[y][x] = 1;
					c=(c==0)?1:0;
				}
				else if(str[y][x]=='B') {
					if(c==2) return -1;
					rail[y][x] = 1;
					c=(c==0)?2:0;
				}
				else if(c!=0) {
					if(rail[y][x]) return -1;
					rail[y][x] = 1;
					if(str[y][x]>='1' && str[y][x]<='9') use[str[y][x]-'0']=1;
				}
			}
			if(c!=0) return -1;
		}
		
		c=1;
		FOR(y,R) FOR(x,C) {
			if(rail[y][x]) c=0;
			if(str[y][x]=='S' && rail[y][x]==0) return -1;
		}
		
		if(c) return -1;
		FOR(i,10) if(use[i]) c+=i;
		
		return c;
	}

};

まとめ

一見コスト最小化の問題に見せかけておいて、実は一意にルートが決まるという問題。
実装は容易だけど解答を考えるのが面白い問題だね。