문제:
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따
www.acmicpc.net
코드:
map 상하좌우에 padding 넣어서 가로 세로 크기가 2씩 증가했지만 배열 크기를 증가시키지 않아 '틀렸습니다'.
/* 1. 좌표 1부터 시작하므로, 뱀 시작 위치는 (1, 1) */
#include <iostream>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef pair<int, int> p;
p hdp, tlp;
int hdd, tld;
int nd[4]['L' + 1];
int len = 1;
int N, K, L;
int map[102][102];
pair<int, char> trn[100]; int lh, lt;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
hdp = tlp = make_pair(1, 1); /* 1 */
map[1][1] = 1;
hdd = tld = 1;
f(d, 4) {
nd[d]['L'] = (d + 3) % 4;
nd[d]['D'] = (d + 1) % 4;
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (auto r : { 0, N + 1 })
fill(map[r], map[r] + N + 2, 1);
for (int r = 1; r <= N; ++r)
map[r][0] = map[r][N + 1] = 1;
while (K--) {
int r, c; cin >> r >> c;
map[r][c] = 2;
}
cin >> L;
f(l, L) {
cin >> trn[l].first;
cin >> trn[l].second;
}
int t;
for (t = 1; ; ++t) {
hdp.first += dr[hdd], hdp.second += dc[hdd]; // 1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
int n = map[hdp.first][hdp.second];
map[hdp.first][hdp.second] = 1; // 그 칸에 있던 사과가 없어지고
switch(n){
case 1: goto out; // 0. 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
case 2: ++len; break; // 2. 만약 이동한 칸에 사과가 있다면, 꼬리는 움직이지 않는다.
default:map[tlp.first][tlp.second] = 0; // 만약 이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비워준다
tlp.first += dr[tld], tlp.second += dc[tld]; // 몸길이를 줄여서
break; // 즉, 몸길이는 변하지 않는다.
}
if (trn[lh].first == t)
hdd = nd[hdd][trn[lh++].second];
if (trn[lt].first == t - len + 1)
tld = nd[tld][trn[lt++].second];
}
out:
cout << t;
return 0;
}