문제 URL : https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
문제 접근법 : 그저 단순 시뮬구현 문제이기때문에
문제설명이 자세하게 나와있어서 쉬운문제입니다. 설명드릴것이 딱히 없고
그저 내가 내가 지나왔던 자리인제 그냄새가 아직까지 남아있는지 확인하는것은
현재시간 - 해당냄새를 뿌렸던시간 > k 이면 남아 있는 시간인것만 아시면 됩니다.
그리고 냄새없는 곳에 이동할때 좌표가 이동해서 해당 좌표가 겹치는게 있다면 가장 작은 상어만 냅두고 나머지는 죽은것을 표시해주면 됩니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define vvvi v<vvi>
#define pii pair<int,int>
int n, m, k,dead;
vvi board,smell;
int dr[5] = { 0,0,2,3,1 };
v<pair<int, int>> sv;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
vvvi pr;
vi dir,isdead;
void input() {
cin >> n >> m >> k;
smell=board = vvi(n, vi(n, -1e8));
pr = vvvi(m + 1, vvi(4, vi(4)));
sv = v<pair<int, int>>(m + 1);
isdead=dir = vi(m + 1);
int a;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a;
if (a) {
sv[a].first = i;
sv[a].second = j;
board[i][j] = 0;
smell[i][j] = a;
}
}
}
for (int i = 1; i <= m; i++) {
cin >> dir[i];
dir[i] = dr[dir[i]];
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
cin >> a;
pr[i][dr[j + 1]][k] = dr[a];
}
}
}
}
bool isrange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < n; }
void move(int cnt) {
map<pii, priority_queue<pii, v<pii>, greater<pii>>> state;
for (int i = 1; i <= m; i++) {
if (isdead[i])continue;
int Dir = dir[i];
int y, x;
tie(y, x) = sv[i];
bool nothing = true;
for (int j = 0; j < 4; j++) {
int d = pr[i][Dir][j];
int ny = y + dy[d];
int nx = x + dx[d];
if (isrange(ny, nx) && cnt - board[ny][nx] > k) {
state[{ny, nx}].push({ i,d });
nothing = false;
break;
}
}
if (nothing) {
for (int j = 0; j < 4; j++) {
int d = pr[i][Dir][j];
int ny = y + dy[d];
int nx = x + dx[d];
if (isrange(ny, nx) && cnt - board[ny][nx] <= k && smell[ny][nx] == i) {
state[{ny, nx}].push({ i,d });
break;
}
}
}
}
for (auto& it : state) {
auto& pq = it.second;
int y, x;
tie(y, x) = it.first;
int shark = pq.top().first;
int Dir = pq.top().second;
pq.pop();
sv[shark] = { y,x };
dir[shark] = Dir;
board[y][x] = cnt;
smell[y][x] = shark;
while (!pq.empty()) {
isdead[pq.top().first] = 1;
pq.pop();
dead++;
}
}
}
void solve() {
int cnt =0;
while (cnt<=1000&&dead<m-1) {
move(++cnt);
}
cout << (cnt > 1000?-1 : cnt) << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 14554 The Other Way (0) | 2022.08.04 |
|---|---|
| 백준 13911 집 구하기 (0) | 2022.07.31 |
| 백준 21611 마법사 상어와 블리자드 (0) | 2022.07.21 |
| 백준 16681 등산 (0) | 2022.07.13 |
| 백준 11952 좀비 (0) | 2022.07.13 |
