/* 가로 길이 세로길이 2엘+1 2차원 홀수 격자, 엑스 와이. 가운데 0,0 엑스 와이 방향에대해서 오른쪽, 아래. 뱀의 크기가 격자판의 한 칸의 크기. 뱀의 머리는 격자판의 오른쪽을 보고 있음, 바라보고 있는 방향으로 1초에 한 칸씩 몸을 늘려나감 뱀의 머리는 그 방향의 칸으로 옮겨갑니다. 예를 들어보면, L=3 인 경우를 생각해보면 뱀은 처음에 0,0에 있으며, 격자판 한 칸 만큼, 뱀의 머리가 바라보는 방향 오른쪽 1초가 지나면 두 칸을 차지하게 되며, 애 때 1,0 칸에 뱀의 머리 1초가 더 지나면 세 칸을 차지하게 되고, 뱀의 머리는 2,0 에 놓이게 됩니다. 머리가 향하고 있느 방향을 일정한 규칙에 따라 시계방향, 반시계방향으로 회전 1번째 회전은 뱀이 출발한지 t1초 후에 일어나며, 아이번째 회전은 뱀이 머리가 밖으로 나가거나, 몸에 부딪히면 break 를 겁니다. 와일문으로 구현 하면 됩니다. 출발한지 몇 초에 죽는지 알아내세요. 예제를 통해서 표를 만들고 파악해보도록 하겠습니다. 3*2 -1 판 이 나오게 됩니다. 4번의 회전이 있습니다. 2 L 2 L 1 L 5 R 오케이 7초 후에 죽는 것 오께이 알겠습니다. que 를 사용해서 움직이는 방향에 대해서 파악하도록 하겠습니다. 이제 SIZE 만 넣어주면 되는데, L 이 10^8 입니다. 이것을 어떻게 처리할 수 있나요? */ #include <iostream> #include <queue> using namespace std; #define SIZE 10000 int dx[] = { 0,0,1,-1 }; // 동 서 남 북 x가 왼쪽오른쪽 y가 아래,위 방향 int dy[] = { 1,-1,0,0 }; // 오른쪽회전시 동->서->남->북 왼쪽은 반대 int x, y, nx, ny, L, N, t, n, m, d; int sec, sec_total; char dir; int map[SIZE][SIZE]; struct info { int x; char y; }; queue<info> que; void problemIn() { cin >> L >> N; for (int i = 0; i < N; i++) { cin >> t >> dir; que.push({ t,dir }); } d = 0; } /* 첫번째 큐값을 만나기전까지 반복합니다. sec 값과 같아질때까지 다음칸이 밖이거나, 몸이면 break 하면 됩니다. 맵에 접근할 수 없으니, 행렬에서 한번 양수로 전환하고 시작점을 가운데로 하도록 하는게 좋습니다. 그럼 3,3 에서 시작한다고 가정하고 오께이, 이것 비쥬얼 기준으로 만드는 것이 좋습니다. 그래야 이동할때 편리합니다. */ int turn_left(int dir) { if (dir == 0) return 3; else if (dir == 1) return 2; else if (dir == 2) return 0; else return 1; } int turn_right(int dir) { if (dir == 0) return 2; else if (dir == 1) return 3; else if (dir == 2) return 1; else return 0; } void solve() { x = y = L; map[x][y] = 1; while (1) { nx = x + dx[d]; // 다음칸을 의미합니다. ny = y + dy[d]; sec++; sec_total++; if ((nx < (2*L+1) && ny < (2*L+1) && nx >= 0 && ny >=0) && map[nx][ny]==0) // 다음칸이 밖이 아니고, 몸이 아니면 { map[nx][ny] = 1; // 뱀머리 표시, 이동 x = nx; y = ny; if (sec == que.front().x) { // info 와 만나면 방향 전환 dir = que.front().y; if (dir == 'L') { d = turn_left(d); } else { d = turn_right(d); } que.pop(); // 사용한 정보 날라기. sec = 0; } } else { // 뱀이 죽는 조건 1. 맵을 벗어나거나, 맵[][]==1 을 만나면 break; } }
} int main() { problemIn(); solve(); cout << sec_total << endl; return 0; } |
문제를 풀때 10^8 이것을 먼저 파악하고 다른 방향으로 문제를 풀이해야 합니다. line 풀이를 보았는데 더욱 헷갈리네, 이것은 시간을 두고 나중에 다시 풀어보도록 하겠습니다. |