Codeforces #416 Div2 D. Vladik and Favorite Game

方針はすぐ立ったけど面倒なことこの上ない。
http://codeforces.com/contest/811/problem/D

問題

二次元のグリッドが与えられる。
ここで左上のマスからゴールマスに隣接マスをたどり移動したい。

この問題はインタラクティブであり、上下左右の移動先を指定するとその隣接マスに移動する。
ただし上下および左右がそれぞれ反転している可能性がある。
一部のマスは穴であり、到達するとそれ以上移動できない。
また、グリッド外に移動しようとすると移動できず今の位置を維持する。
適切に移動指示をだし、ゴールに到達せよ。

解法

マス目はわかっているのでまず探索で経路を求めよう。
以後経路に沿って移動する。
上下または左右に初めて移動する際、その結果を確認することで上下・左右反転の有無を確定できるので、あとはゴールに突き進むだけ。
これから下に移動する際は仮に反転動作によって上に移動するとしても、もともと最上段なので反転のせいで穴に落ちる必要はない。

以下のコードは一旦上下左右を確定させてからゴールに向かっているためちょっと冗長。

int H,W;
string S[101];

int S_LR,S_UD;
int TX,TY;

int vis[101][101];
string from[101][101];


pair<int,int> ask(string s) {
	int r,c;
	cout<<s<<endl;
	cin>>r>>c;
	if(r==TY+1 && c==TX+1) exit(0);
	return {r-1,c-1};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='F') {
			S[y][x]='.';
			TY=y;
			TX=x;
		}
	}
	
	if(TY==0 && TX==0) return;
	
	S_LR=-1,S_UD=-1;
	if(H==1) S_UD=0;
	if(W==1) S_LR=0;
	
	if(W>1 && S[0][1]=='.') {
		auto a=ask("L");
		if(a.second==1) S_LR=1, ask("R");
		else S_LR=0;
	}
	if(H>1 && S[1][0]=='.') {
		auto a=ask("U");
		if(a.first==1) S_UD=1, ask("D");
		else S_UD=0;
	}
	
	int cy=0,cx=0;
	if(S_LR==-1) {
		while(S[cy][1]=='*') {
			ask(S_UD?"U":"D");
			cy++;
		}
		auto a=ask("L");
		if(a.second==1) {
			S_LR=1;
			ask("R");
		}
		else S_LR=0;
	}
	if(S_UD==-1) {
		while(S[1][cx]=='*') {
			ask(S_LR?"L":"R");
			cx++;
		}
		auto a=ask("U");
		if(a.first==1) {
			S_UD=1;
			ask("D");
		}
		else S_UD=0;
	}
	queue<int> Q;
	Q.push(TY*100+TX);
	vis[TY][TX]=1;
	while(Q.size()) {
		int sy=Q.front()/100;
		int sx=Q.front()%100;
		Q.pop();
		FOR(i,4) {
			int dd[4]={1,0,-1,0};
			int ty=sy+dd[i];
			int tx=sx+dd[i^1];
			if(ty<0 || ty>=H || tx<0 || tx>=W || S[ty][tx]=='*' || vis[ty][tx]) continue;
			vis[ty][tx]=1;
			Q.push(ty*100+tx);
			if(i==0) from[ty][tx]=S_UD?"D":"U";
			if(i==1) from[ty][tx]=S_LR?"R":"L";
			if(i==2) from[ty][tx]=S_UD?"U":"D";
			if(i==3) from[ty][tx]=S_LR?"L":"R";
		}
	}
	while(cy!=TY || cx!=TX) {
		auto p=ask(from[cy][cx]);
		cy=p.first;
		cx=p.second;
	}
}

まとめ

もっとシンプルに書けないものか。