본 문제는 시뮬레이션으로 문제 해석을 잘해서 코드로 옮기면 풀 수 있는 문제이다.
조건 중 별거 아닌 것 같지만 중요한 조건이 있었다. '먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다'이다. 처음에 구현 코드는 뒤의 꼬리부터 한 칸 씩 땡겼다. 이 경우, 1초뒤 머리를 다음칸에 위치시킬 때 그 곳에 꼬리가 있다면 게임이 종료되어야하는데 그렇지 못한다.
#include <iostream>
#include <vector>
using namespace std;
int T, N, K, L;
vector<vector<int>> table;
vector<vector<int>> snake;
vector<vector<int>> apple;
vector<vector<int>> moves;
int mvIdx;
int dir;
int nxt[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int solver(int time, int x, int y)
{
if(L != 0 && mvIdx < L && time == moves[mvIdx][0]) {
if(moves[mvIdx][1] == 0) {
dir++;
}
else {
dir--;
}
if(dir > 3)
dir = 0;
if(dir < 0)
dir = 3;
mvIdx++;
}
int nxtX = snake[0][0] + nxt[dir][0];
int nxtY = snake[0][1] + nxt[dir][1];
if(nxtX < 0 || nxtX >= N || nxtY < 0 || nxtY >= N)
return time + 1;
if(table[nxtX][nxtY] == 1) {
vector<int> temp(2, 0);
temp[0] = nxtX;
temp[1] = nxtY;
snake.insert(snake.begin(), temp);
table[nxtX][nxtY] = 0;
}
else {
for(int i = snake.size() - 1; i > 0; i--) {
if(nxtX == snake[i][0] && nxtY == snake[i][1])
return time + 1;
snake[i][0] = snake[i - 1][0];
snake[i][1] = snake[i - 1][1];
}
snake[0][0] = nxtX;
snake[0][1] = nxtY;
}
return solver(time + 1, nxtX, nxtY);
}
int main() {
T = 1;
for(int tc = 0; tc < T; tc++) {
scanf("%d", &N);
table.resize(N);
table.clear();
for(int i = 0; i < N; i++) {
vector<int> tmp(N, 0);
table.push_back(tmp);
}
scanf("%d", &K);
apple.resize(K);
apple.clear();
int x, y;
for(int i = 0; i < K; i++) {
scanf("%d %d", &x, &y);
table[x - 1][y - 1] = 1;
}
mvIdx = 0;
scanf("%d", &L);
char z;
moves.resize(L);
moves.clear();
for(int i = 0; i < L; i++) {
vector<int> tmp(2, 0);
scanf("%d %c", &x, &z);
tmp[0] = x;
if(z == 'D') {
tmp[1] = 0;
}
else if(z == 'L') {
tmp[1] = 1;
}
else {}
moves.push_back(tmp);
}
snake.resize(1);
snake.clear();
vector<int> tmp(2, 0);
snake.push_back(tmp);
dir = 0;
printf("%d\n", solver(0, 0, 0));
}
return 0;
}