https://www.acmicpc.net/problem/3190
이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.
이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.
(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include <iostream>
#include <vector>
using namespace std;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int n, k;
//사과의 좌표를 저장
bool apple[100][100];
//머리가 위치한 시간을 저장
int headtime[100][100];
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cin >> n >> k;
//사과정보 저장
int ax, ay;
for (int i = 0; i < k; i++) {
cin >> ax >> ay;
apple[ax - 1][ay - 1] = true;
}
int l;
cin >> l;
int t;
char c;
//방향 회전 정보를 저장
vector<pair<int, char>> vt;
for (int i = 0; i < l; i++) {
cin >> t;
cin >> c;
vt.push_back(make_pair(t,c));
}
int time = 0;
//방향 회전정보를 이용하기 위한 인덱스
int index = 0;
//초기 방향
int dir = 0;
//초기 길이
int len = 1;
//초기 위치는 좌측 맨위쪽
int x = 0;
int y = 0;
while (true) {
//먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
time++;
len += 1;
int nx = x + dx[dir];
int ny = y + dy[dir];
//벽에 부딪힘
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
//몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
//이동한 칸에 현재 시간을 저장
headtime[nx][ny] = time;
//사과가 있는지 검사
if (apple[nx][ny]) {
apple[nx][ny] = false;
}
else {
len -= 1;
}
//l번만큼 방향이동을 한다.
if (index < l) {
//현재시간이 방향을 회전해야하는 시간이다
if (time == vt[index].first) {
if (vt[index].second == 'D') {
dir = (dir + 1) % 4;
}
else if (vt[index].second == 'L') {
dir = (dir + 3) % 4;
}
//방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
index++;
}
}
//현재 좌표를 머리가 이동한 칸의 좌표로 변경
x = nx;
y = ny;
}
cout << time << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
[BOJ] 2234. 성곽 (0) | 2019.08.13 |
---|---|
[BOJ] 11559. Puyo Puyo (0) | 2019.08.08 |
[BOJ] 15683. 감시 (0) | 2019.08.05 |
[BOJ] 14500. 테트로미노 (0) | 2019.08.04 |
[BOJ] 14499. 주사위 굴리기 (0) | 2019.08.04 |