Muscardinus
아기상어 본문
728x90
https://www.acmicpc.net/problem/16236
#include <iostream>
#include <queue>
using namespace std;
int n;
int map[20][20];
int ch[20][20];
int res = 0;
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
struct Shark {
int x, y, s, ate;
void sizeUp() {
s++;
ate = 0;
}
};
struct State {
int x, y, dis;
State(int a, int b, int c) {
y = a; x = b; dis = c;
}
bool operator<(const State &b) const{
if (dis == b.dis) {
if (y == b.y) return x > b.x;
else return y > b.y;
}
else return dis > b.dis;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin >> n;
priority_queue<State> Q;
Shark shark;
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
cin >> map[y][x];
if (map[y][x] == 9) {
shark.y = y; shark.x = x;
map[y][x] = 0;
}
}
}
Q.push(State(shark.y, shark.x, 0));
shark.s = 2;
shark.ate = 0;
while (!Q.empty()) {
State tmp = Q.top();
Q.pop();
int y = tmp.y;
int x = tmp.x;
int dis = tmp.dis;
if (map[y][x] && map[y][x] < shark.s) {
shark.y = y;
shark.x = x;
shark.ate++;
if (shark.ate >= shark.s) shark.sizeUp();
map[y][x] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ch[i][j] = 0;
}
}
while (!Q.empty()) Q.pop();
res = tmp.dis;
}
for (int dir = 0; dir < 4; dir++) {
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny<0 || ny>=n || nx<0 || nx>=n || map[ny][nx] > shark.s || ch[ny][nx]>0) continue;
Q.push(State(ny, nx, dis + 1));
ch[ny][nx] = 1;
}
}
cout << res << "\n";
return 0;
}
728x90
'알고리즘 문제 > [삼성 SW 역량 테스트 기출 문제]' 카테고리의 다른 글
이차원 배열과 연산 (0) | 2020.09.03 |
---|---|
미세먼지 안녕! (0) | 2020.09.02 |
나무 제테크 (0) | 2020.09.01 |
인구 이동 (0) | 2020.08.31 |
치킨 배달 (0) | 2020.08.30 |
Comments