UVa-118 : Mutant Flatworld Explorers

問題概要

ロボットの動き(右を向く、左を向く、前進する)をシミュレートする。ただし、ロボットは枠から落ちることがある。枠から落ちたロボットは最後にいた位置に匂いを残す。その匂いによって、それ以降のロボットはそのマスから落ちることを防ぐことができる。

解法

題意が正確に把握できれば後はやるだけ。

acceptされたコード

計算量O(strlen)。

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_L = 100;
const int MAX_W = 50;
const int dy[] = {1,0,-1,0}, dx[] = {0,1,0,-1};
const char direction[] = "NESW";

int dir; //0:N, 1:E, 2:S, 3:W
int H, W;
char cmd[MAX_L + 10];
bool prohibit[MAX_W+1][MAX_W+1];

void solve(int x, int y, char d){
	for(int i=0; i<4; i++)if(d == direction[i]){
		dir = i;
	}

	for(int i=0, L=strlen(cmd); i<L; i++){
		if(cmd[i] == 'R'){
			dir = (dir+1)&3;
		}
		else if(cmd[i] == 'L'){
			dir = (dir-1)&3;
		}
		else{
			int nx = x + dx[dir], ny = y + dy[dir];
			if(0<=nx && nx<=W && 0<=ny && ny<=H){
				x = nx;
				y = ny;
			}
			else if(!prohibit[x][y]){
				printf("%d %d %c LOST\n", x, y, direction[dir]);
				prohibit[x][y] = true;
				return ;
			}
		}
	}

	printf("%d %d %c\n", x, y, direction[dir]);
}

int main(){
	scanf("%d%d",&W, &H);
	int x, y;
	char d;
	while(scanf(" %d %d %c ", &x, &y, &d) != EOF){
		scanf("%[^\n]%*c", cmd);
		solve(x, y, d);
	}

	return 0;
}