yukicoder : No.331 CodeRunnerでやれ

クエリ数最小を目指すとどんなもんなんだろうな。
http://yukicoder.me/problems/877

問題

N*Mのグリッドからなる迷路がある。

一部のマスは壁であり移動不可能である。
この迷路の外周は1マスを除き壁であり、壁ではない唯一の移動可能マスがゴールである。
プレイヤーはこのゴールに向かって移動したい。

ただし迷路の形状やプレイヤーの現在位置は明には与えられない。
この問題はリアクティブであり、プレイヤーは、前進・後退・右回転・左回転のいずれかを指示するとその通り行動し、その後現在の向きに後何マス前進可能かが返される。
また、プレイヤーがゴールに到達するとメッセージが表示される。

適切な入出力を行い、プレイヤーをゴールに導け。

解法

DFSの要領で探索していく。
回転しながら4方向の進行可能マス数を求め、その方向に進行可能かつ未訪問ならDFSした上、最後に更新で直前のマスに戻る。
もし無限に前進可能な状態になったら、あとはゴールまでひたすら前進しよう。

int ask(char c) {
	string s;
	cout<<c<<endl;
	cin>>s;
	if(s[0]=='M') exit(0);
	return atoi(s.c_str());
}

int vis[50][50];

int dfs(int cy,int cx,int d) {
	int i,x;
	vis[cy][cx]=1;
	
	FOR(i,4) {
		int dx[4]={1,0,-1,0};
		int dy[4]={0,1,0,-1};
		
		x=ask('R');
		while(x>100) ask('F');
		
		d=(d+1)%4;
		int tx=cx+dx[d];
		int ty=cy+dy[d];
		
		if(x>0 && vis[ty][tx]==0) ask('F'), dfs(ty,tx,d);
	}
	ask('B');
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>s;
	dfs(25,25,1);
}

まとめ

ああ　おそろしや　おそろしや
きょだいな　かぶとが　ひをふいて・・・・・・

こういうの見ると昔のコナミゲー思い出す。