[3190번] 뱀

3190번: 뱀

 

www.acmicpc.net

뱀이 사과를 먹으면 길이가 늘어나는 게임이다.

규칙은 아래와 같다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct pnt { int r, c; };
int Map[101][101];
int visit[101][101];
int time_ = 0;
int N, k, L;
pnt dir[4] = { {0,1},{1,0},{0,-1},{-1,0} };
queue<pair<int, char>>cmd;
queue<pnt>snake;
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        Map[r][c] = 1;
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        pair<int, char> tmp;
        cin >> tmp.first >> tmp.second;
        cmd.push(tmp);
    }
    int snake_dir = 0;
    snake.push({ 1,1 });
    visit[1][1] = 1;
    while (1) {
        int nr = snake.back().r + dir[snake_dir].r;
        int nc = snake.back().c + dir[snake_dir].c;
        if (!(nr < 1 || nr>N || nc<1 || nc > N) && visit[nr][nc] == 0) {
            snake.push({ nr,nc });
            visit[nr][nc] = 1;
            if (Map[nr][nc] == 0) {
                visit[snake.front().r][snake.front().c] = 0;
                snake.pop();
            }
            Map[nr][nc] = 0;
            time_++;
        }
        else break;
        if (!cmd.empty() && cmd.front().first == time_) {
            if (cmd.front().second == 'D') {
                snake_dir = (snake_dir + 1) % 4;
            }
            else if (cmd.front().second == 'L') {
                snake_dir--;
                if (snake_dir < 0) {
                    snake_dir = 4 + snake_dir;
                }
            }
            cmd.pop();
        }
    }
    cout << time_ + 1;
    return 0;
}