Google Code Jam 2015 Round 2 : A. Pegman

Aだけ完答、あとB,CはSmallだけ解いてまさかの500位フィニッシュです。
https://code.google.com/codejam/contest/8234486/dashboard#s=p0

問題

2次元グリッドがある。
一部のマスには上下左右の矢印がある。

このグリッドのどこかのマスに駒を置いたとき、矢印のあるマスの場合はその方向に駒が動いていく。
駒は矢印のあるマスに乗るまで動き、矢印のあるマスに乗るとその向きに動く向きを変えて動き続ける。

ここで、矢印があるマスについて矢印の向きを変えることができるとする。
グリッドで駒を最初どこに置いてもグリッド外に駒が飛び出さないようにしたい。
向きを変えなければいけない矢印マスの最小値を答えよ。

解法

「どこかにループを作ってそこに行くようにしよう…」と考えると複雑になる。

この問題はもっと簡単に解くことが出来て、各矢印マスについて：

• 今矢印を向いている方向に他の矢印があれば、そのマスはいじる必要はない。
• 今矢印を向いている方向に他の矢印がない場合：
  • 他の向きに矢印マスがあるなら、そちらを向けばよい
  • 他の向きに矢印マスがない場合、条件を満たすグリッドは作れない。

非常にシンプルだが、矢印の向きに常に他の矢印マスがあるということは、結局いつまでもグリッド外に飛び出さないことになる。
以下のコードでは、まず上下左右に他の矢印マスがあるか判定してから、上記処理を行っている。

int H,W;
string S[101];
int cost;
int L[101][101];
int R[101][101];
int T[101][101];
int B[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	FOR(y,H) {
		L[y][0]=0;
		for(x=1;x<W;x++)  L[y][x]=(S[y][x-1]!='.')|L[y][x-1];
		R[y][W-1]=0;
		for(x=W-2;x>=0;x--) R[y][x]=(S[y][x+1]!='.')|R[y][x+1];
	}
	FOR(x,W) {
		T[0][x]=0;
		for(y=1;y<H;y++) T[y][x]=(S[y-1][x]!='.')|T[y-1][x];
		B[H-1][x]=0;
		for(y=H-2;y>=0;y--) B[y][x]=(S[y+1][x]!='.') | B[y+1][x];
	}
	cost=0;
	FOR(y,H) FOR(x,W) if(S[y][x]!='.') {
		if(S[y][x]=='^' && T[y][x]) continue;
		else if(S[y][x]=='v' && B[y][x]) continue;
		else if(S[y][x]=='<' && L[y][x]) continue;
		else if(S[y][x]=='>' && R[y][x]) continue;
		
		if(L[y][x] || R[y][x] || T[y][x] || B[y][x]) {
			cost++;
		}
		else {
			return _P("Case #%d: IMPOSSIBLE\n",_loop);
		}
	}
	
	_P("Case #%d: %d\n",_loop,cost);
}

まとめ

気づいてしまえばあっさりなんだよなぁ。