2015-2016 ACM-ICPC NEERC : J. Cleaner Robot

こちらも単なる実装問題。
http://codeforces.com/contest/589/problem/J

問題

２次元グリッドがあり、各マスの移動可否が与えられる。
また掃除ロボットの初期位置と向きが与えられる。

ロボットは以下のstepに従い動く。

1. 今いるマスを掃除する。
2. 今向いている向きの隣接マスに移動可能なら移動し、step1に戻る。
3. 上記移動が不可の場合、向きを90度変えてstep2に戻る。

ロボットが無限時間動作したとき、掃除されるマスはいくつあるか。

解法

移動条件を素直に実装するだけ。
総マス目数の数倍step分シミュレートすれば十分。

int W,H;
string S[101];

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int cx,cy,dir;
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			if(S[y][x]=='D') dir=1,S[y][x]='.',cy=y,cx=x;
			if(S[y][x]=='U') dir=3,S[y][x]='.',cy=y,cx=x;
			if(S[y][x]=='R') dir=0,S[y][x]='.',cy=y,cx=x;
			if(S[y][x]=='L') dir=2,S[y][x]='.',cy=y,cx=x;
		}
	}
	
	int state=0,cl=0;
	FOR(i,50000) {
		if(state==0) {
			if(S[cy][cx]=='.') S[cy][cx]='+',cl++;
			state=1;
		}
		else if(state==1) {
			int ny=cy+dy[dir];
			int nx=cx+dx[dir];
			if(nx<0 || nx>=W || ny<0 || ny>=H || S[ny][nx]=='*') {
				state=2;
			}
			else {
				cy=ny;
				cx=nx;
				state=0;
			}
		}
		else if(state==2) {
			dir=(dir+1)%4;
			state=1;
		}
	}
	cout<<cl<<endl;
	
}

まとめ

やることは簡単だけど面倒な問題。