Codeforces 132 B. Piet

問題

hxwのグリッドがあり、各マスには'0'-'9'の数字が書かれている。

BP(block pointer)および、DP(direction pointer)とCP(choose pointer)という三つのポインタがある。
BPは現在のブロックを指している。
DPは現在の進む方向を指している。上下左右のいずれかである。
CPは次に曲がる方向を示している。DPに対して右に90度または左に90度のどちらかである。

n回、次の動作を繰り返す。

• 次のブロックが、現在のBPのブロックと同じ色の間、BPはDPの向きへ動き続ける。
• 次のブロックが、現在のBPのブロックと同じ色の間、BPはCPの向きへ動き続ける。
• 動けなくなったら、BPからみてDPの向きの隣のマスを見る。
• それが色つきのマス（'1'-'9'）ならBPをそのマスにする。
• 黒（'0'）のマスあるいはグリッドの外だったら、
  • CPがDPから見て左に90度だったら、右に90度にする
  • CPがDPから見て右に90度だったら、DPを時計回りに90度回転させ、CPをDPから見て左に90度にする

全ての動作を終えたあとにBPが指しているブロックの色を答えよ。

制約条件

h,w≦50
n≦5*10^7

方針

シミュレートする。
BP,DP,CPが一つに定まると、次のBP,DP,CPは一つに定まるので、
あらかじめ全て計算しておく（あるいはメモ化する）

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
int h,w,n;
string in[50];
pair<pi,pi> memo[50][50][4][2];
pair<pi,pi> next(int y,int x,int dp,int cp){
	if(memo[y][x][dp][cp].first.first>=0)return memo[y][x][dp][cp];
	int cy=y, cx=x, cdp=dp, ccp=cp, d=cp?dp+1&3:dp+3&3;
	for(;;){
		int ny=cy+dy[dp], nx=cx+dx[dp];
		if(ny<0||nx<0||nx>=w||ny>=h||in[ny][nx]!=in[cy][cx])break;
		cy=ny; cx=nx;
	}
	for(;;){
		int ny=cy+dy[d], nx=cx+dx[d];
		if(ny<0||nx<0||nx>=w||ny>=h||in[ny][nx]!=in[cy][cx])break;
		cy=ny; cx=nx;
	}
	int ny=cy+dy[dp], nx=cx+dx[dp];
	if(ny<0||nx<0||nx>=w||ny>=h||in[ny][nx]=='0'){
		if(cp)ccp=0, cdp=dp+1&3;
		else ccp=1;
		
		return memo[y][x][dp][cp]=mp(mp(cy,cx),mp(cdp,ccp));
	}
	return memo[y][x][dp][cp]=mp(mp(ny,nx),mp(dp,cp));
}

void run()
{
	cin>>h>>n;
	rep(i,h)cin>>in[i];
	w=in[0].size();
	memset(memo,-1,sizeof(memo));
	int y=0,x=0,dp=1,cp=0;
	rep(i,n){
		pair<pi,pi> nxt=next(y,x,dp,cp);
		y=nxt.first.first; x=nxt.first.second;
		dp=nxt.second.first; cp=nxt.second.second;
	}
	cout<<in[y][x]<<endl;
}