BOJ3190: 뱀

작성일

https://www.acmicpc.net/problem/14889

  • 100문제 풀기는 1월까지로 변경해야 할듯..
  • 1월동안 100문제 풀기 (8/100)
  • 백트래킹 문제. 걍 시키는 대로 풀면 됨.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

// R, D, L, U
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
int N, K, L, board[102][102], dir, tt, x, y;
const int BLANK = 0, APPLE = 1, BODY = 2, WALL = 3;
char rot[10001];

void turnRight() { dir = (dir+1+4)%4; }
void turnLeft() { dir = (dir-1+4)%4; }
struct Point{ int x, y; };

int main() {
  ios::sync_with_stdio(false);
  cin >> N >> K;
  for(int i = 0; i < K; i++) {
    cin >> x >> y;
    board[x][y] = APPLE;
  }
  cin >> L;
  for(int i = 0; i < L; i++) {
    char r;
    cin >> tt >> r;
    rot[tt] = r;
  }

  //Init
  for(int i = 0; i <= N+1; i++)
    board[i][0] = board[0][i] = board[N+1][i] = board[i][N+1] = WALL;
  board[1][1] = BODY;

  deque<Point> snake;
  snake.push_back({1,1});

  for(tt = 0; ; tt++) {
    if(rot[tt] == 'L') turnLeft();
    else if(rot[tt] == 'D') turnRight();
    int nx = snake.front().x + dx[dir];
    int ny = snake.front().y + dy[dir];
    if(board[nx][ny] == BODY || board[nx][ny] == WALL) break;
    if(board[nx][ny] == BLANK) {
      board[snake.back().x][snake.back().y] = BLANK;
      snake.pop_back();
    }
    board[nx][ny] = BODY;
    snake.push_front({nx,ny});
  }
  cout << tt+1;
}