기술 블로그

3190번 뱀 본문

알고리즘 문제/BOJ

3190번 뱀

parkit 2019. 10. 10. 00:53
728x90
반응형

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 102
 
int N, K, L, y, x, t, hy, hx, ty, tx, ans, d = 4;
char c;
bool apple[Max][Max];
pair<bool, int> snake[Max][Max];
vector<pair<int, char> > v;
 
// 상1, 하2, 좌3, 우4
 
void print()
{
    printf("\n\n%d초\n", ans);
 
    for (int i = 0; i < N + 2; i++)
    {
        for (int j = 0; j < N + 2; j++)
        {
            if (snake[i][j].first) printf("■");
            else if (apple[i][j]) printf("★");
            else printf("□");
        }
 
        printf("\n");
    }
}
 
void tail_move(int index)
{
    if (index == 1) --ty;
    else if (index == 2) ++ty;
    else if (index == 3) --tx;
    else if (index == 4) ++tx;
}
 
int main(void)
{
    for (int i = 0; i < Max; i++)
    {
        for (int j = 0; j < Max; j++)
        {
            snake[i][j].first = false;
            snake[i][j].second = 0;
        }
    }
 
    cin.tie(0);
    cin >> N >> K;
    snake[1][1].first = true;
    snake[1][1].second = d;
 
    for (int i = 0; i < K; i++)
    {
        cin >> y >> x;
        apple[y][x] = true;
    }
 
    hy = hx = ty = tx = 1;
 
    cin >> L;
 
    for (int i = 0; i < L; i++)
    {
        cin >> t >> c;
        v.push_back({ t, c });
    }
 
    int idx = 0;
 
    while (true)
    {
        //print();
 
        if (d == 1)
        {
            // 상
            if (hy - 1 == 0 || snake[hy - 1][hx].first) break;        
            --hy;
        }
        else if (d == 2)
        {
            // 하
            if (hy + 1 == N + 1 || snake[hy + 1][hx].first) break;
            ++hy;
        }
        else if (d == 3)
        {
            // 좌
            if (hx - 1 == 0 || snake[hy][hx - 1].first) break;
            --hx;
        }
        else if (d == 4)
        {
            // 우
            if (hx + 1 == N + 1 || snake[hy][hx + 1].first) break;
            ++hx;
        }
 
        snake[hy][hx].first = true;
        snake[hy][hx].second = d;
 
        if (apple[hy][hx]) apple[hy][hx] = false;
        else
        {            
            int temp_y = ty, temp_x = tx;
            tail_move(snake[ty][tx].second);
            snake[temp_y][temp_x].first = false;
            snake[temp_y][temp_x].second = 0;            
        }
 
        ++ans;
 
        if (idx < v.size() && ans == v[idx].first)
        {
            if (v[idx].second == 'D')
            {
                if (d == 1) d = 4;
                else if (d == 2) d = 3;
                else if (d == 3) d = 1;
                else if (d == 4) d = 2;            
            }
            else if (v[idx].second == 'L')
            {
                if (d == 1) d = 3;
                else if (d == 2) d = 4;
                else if (d == 3) d = 2;
                else if (d == 4) d = 1;
            }
 
            snake[hy][hx].second = d;
            ++idx;
        }
    }
 
    printf("%d\n", ans + 1);
 
    return 0;
}
cs





















728x90
반응형
저작자표시

'알고리즘 문제 > BOJ' 카테고리의 다른 글

12865번 평범한 배낭  (0) 2019.10.21
17609번 회문  (0) 2019.10.13
2529번 부등호  (0) 2019.10.01
17505번 링고와 순열  (0) 2019.09.30
17412번 도시 왕복하기 1  (0) 2019.09.29
'알고리즘 문제/BOJ' Related Articles more