[3190] 뱀

풀이

1. 뱀이 보고 있는 방향을 체크해주고 나아갈 방향을 구조화 하면 됩니다.
2. 사과를 먹으면 없애줘야합니다.
3. 자신의 몸에 닿아서 종료되는 경우를 추가해야합니다.
4. 맵 밖을 벗어나면 종료합니다.

코드

#include <cstdio>
#include <deque>
#include <queue>
using namespace std;

#define MAX 100
#define LOOK_RIGHT 0
#define LOOK_LEFT 1
#define LOOK_DOWN 2
#define LOOK_UP 3

deque<pair<int, int> > dq;
queue<pair<int, int> > time;
int map[MAX+1][MAX+1];
bool check[MAX + 1][MAX + 1];
int n = 0, k=0;
int ret = 0;
int ans = 0xFFFFFFF;
//오른쪽, 왼쪽, 아래, 위
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0};
int orient = LOOK_RIGHT;
void dfs(void) {
	int nx = 0, ny = 0;
	while (true) {
		ret += 1;
		pair<int, int> curr = dq.front();
		nx = curr.first;
		ny = curr.second;
		switch (orient) {
		case LOOK_RIGHT:
			nx += dx[0];
			ny += dy[0];
			break;
		case LOOK_LEFT:
			nx += dx[1];
			ny += dy[1];
			break;
		case LOOK_DOWN:
			nx += dx[2];
			ny += dy[2];
			break;
		case LOOK_UP:
			nx += dx[3];
			ny += dy[3];
			break;
		}
		//경계를 벗어나는 경우
		if (nx <1 || nx >n) return;
		if (ny <1 || ny >n) return;
		//자신의 몸에 닿는 경우
		if (check[nx][ny]) return;
		//머리 전진
		dq.push_front(make_pair(nx, ny));
		check[nx][ny] = true;
		//머리 위치에 사과가 없으면 꼬리 당기기
		if (map[nx][ny] != 1) {
			check[dq.back().first][dq.back().second] = false;
			dq.pop_back();
		}
		else {
			//사과 먹으면 없애기!!
			map[nx][ny] = 0;
		}
		//머리 회전
		if (!time.empty() && time.front().first == ret) {
			if (time.front().second == 'L') {
				//좌회전
				switch (orient) {
				case LOOK_LEFT:
					orient = LOOK_DOWN;
					break;
				case LOOK_RIGHT:
					orient = LOOK_UP;
					break;
				case LOOK_DOWN:
					orient = LOOK_RIGHT;
					break;
				case LOOK_UP:
					orient = LOOK_LEFT;
					break;
				}
			}
			else {
				//우회전
				switch (orient) {
				case LOOK_LEFT:
					orient = LOOK_UP;
					break;
				case LOOK_RIGHT:
					orient = LOOK_DOWN;
					break;
				case LOOK_DOWN:
					orient = LOOK_LEFT;
					break;
				case LOOK_UP:
					orient = LOOK_RIGHT;
					break;
				}
			}
			time.pop();
		}
	}
}

int main(void) {
	scanf("%d", &n);
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		int a = 0, b = 0;
		scanf("%d%d", &a, &b);
		map[a][b] = 1;
	}
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		int a = 0; char b = 0;
		scanf("%d", &a); getchar();
		scanf("%c", &b); getchar();
		time.push(make_pair(a, b));
	}
	dq.push_back(make_pair(1, 1));
	check[1][1] = true;
	dfs();
	printf("%d\n", ret);
	return 0;
}