3190번-뱀

/*
뱀이 나와서 기어다닌다. 사과를 먹으면 뱀 길이가 늘어난다. 
벽이나 자기 자신의 몸과 부딪히면 게임 끝. 
nxn 정사각 보드 위에서 진행. 
몇몇 칸에는 사과가 놓여져 있다. 
뱀의 길이는 1이다. 
처음엔 오른쪽을 향한다. 

*/
#include<iostream>
#include<queue>
#define X first
#define Y second
using namespace std;

int n;	//보드의 크기
int k;	//사과의 개수
int board[105][105];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int vis[105][105];
queue<pair<int, char>> snake;
queue<pair<int, int>> tail;

int main() {
	cin >> n;
	cin >> k;
	//사과의 위치
	for (int i = 0; i < k; i++) {
		//첫번째 행, 두번쨰 열
		int row, col;
		cin >> row >> col;
		board[row-1][col-1] = 1;
	}

	//뱀의 방향 변환 횟수 L
	int L;
	cin >> L;
	while (L--) {
		//X와 C, X초 끝난 뒤에 왼쪽(L), 오른쪽(D)으로 90도 방향 회전. 
		int x;
		char c;
		cin >> x >> c;
		snake.push({ x,c });
	}

	int curX = 0;
	int curY = 0;
	int dir = 0;

	//뱀이 지나간 자리
	vis[0][0] = 1;
	tail.push({ 0,0 });
	int cnt = 0;
	while (true) {
		int nx = curX + dx[dir];
		int ny = curY + dy[dir];
		cnt++;
		if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] == 1)break;
		//사과가 없다면
		if (board[nx][ny] != 1) {
			auto cur_tail = tail.front();
			vis[cur_tail.X][cur_tail.Y] = 0;
			tail.pop();
		}
		else {
			
			board[nx][ny] = 0;
		}
		curX = nx;
		curY = ny;
		vis[nx][ny] = 1;
		tail.push({ nx,ny });
		if (snake.size()) {
			auto cur = snake.front();
			if (cnt == cur.X) {
				if (cur.Y == 'L') {
					dir = (dir + 3) % 4;
				}
				else {
					dir = (dir + 1) % 4;
				}
				snake.pop();
			}
		}	
	}
	cout << cnt;
}