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
(문제 요약)
– 상어는 1부터 M까지의 자연수를 가지고 있으며 모든 숫자가 다릅니다.
– 상어는 자신의 영토를 지키기 위해 다른 상어를 겁주려고 하지만, 1번 성체 상어가 가장 강하고 다른 모든 상어를 겁줄 수 있습니다.
– N×N 그리드의 M셀에 상어가 있다.
처음에 모든 상어는 자신의 위치에 자신의 냄새를 뿌립니다.
– 이후 1초마다 모든 상어가 상하좌우로 동시에 인접한 칸으로 이동하며 그 칸에 냄새를 뿌립니다.
상어가 k번 이동하면 냄새가 사라집니다.
– 각각의 상어가 이동 방향을 결정할 때 먼저 냄새가 나지 않는 인접한 공간을 향해 상어를 잡습니다.
– 그런 사각형이 없으면 사각형 방향으로 냄새를 맡아 잡습니다.
이 시점에서 여러 개의 가능한 셀이 있을 수 있으며 이 경우 특정 우선 순위가 따릅니다.
– 우선 순위는 상어마다 다를 수 있으며, 같은 상어라도 현재 어느 방향을 향하고 있는지에 따라 달라질 수 있습니다.
– 상어가 처음에 향하고 있는 방향이 입력으로 주어지고, 그 후에는 방금 이동한 방향이 향하고 있는 방향이 됩니다.
– 모든 상어가 이동한 후 여러 상어가 공간에 남아 있으면 가장 낮은 번호의 상어를 제외한 모든 상어가 그리드에서 추방됩니다.
– 이 과정을 반복하면 Shark 1만 그리드에 남을 때까지 몇 초가 걸리는지 계산하는 프로그램을 작성하세요.
–
– Fig. 5는 최종 상태가 아닌 중간 상태임에 유의한다.
(문제 조건)
– N, M 및 k는 첫 번째 줄에 지정됩니다.
(2≤N≤20, 2≤M≤N2, 1≤k≤1,000)
– 그리드의 모양은 다음 행부터 N행까지 주어진다.
0은 빈 셀이고 0이 아닌 숫자 x는 상어 번호 x를 포함하는 셀입니다.
– 다음 행은 각 상어의 방향을 차례로 보여줍니다.
1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미합니다.
– 다음 줄부터 각 상어의 방향 우선 순위가 차례로 지정되며, 상어당 4줄입니다.
각 행은 4개의 숫자로 구성됩니다.
- 상어를 묘사한 4개의 라인 중 첫 번째 라인은 상어가 위를 향했을 때 방향 우선, 두 번째 라인은 아래를 향했을 때 우선, 세 번째 라인은 왼쪽을 향했을 때 우선, 네 번째 라인은 상어가 아래를 향했을 때 우선입니다.
상어는 왼쪽을 향하고 있고, 오른쪽을 향하고 있을 때 선이 우선합니다. - 1부터 4까지의 자연수가 각 우선순위별로 한번씩 나타나며 먼저 나오는 방향이 우선순위를 가집니다.
예를 들어 우선 순위가 1 3 2 4이면 방향 순서는 위, 왼쪽, 아래, 오른쪽입니다.
– 맨 처음에 각 상어는 인접한 빈 공간을 가지고 있습니다.
그래서 처음부터 움직이지 못하는 경우가 없다.
– 제한 시간: 1초
– 메모리 제한: 512MB
(문제를 해결하다)
이것은 이전에 풀었던 낚시왕(#17143)과 청춘상어(#19236)와 같은 상어 시리즈의 다음 문제입니다.
이 문제는 어왕 문제에 조건을 좀 더 추가한 경우라고 볼 수 있다.
각 상어는 움직일 때마다 움직이고 흔적을 남깁니다.
또한, 상어가 이동하는 방향은 우선적으로 빈 공간으로 이동하고, 빈 공간이 전혀 없으면 궤적 중에서 자신의 궤적 방향으로 움직인다.
확인해야 할 방향의 순서는 작업의 예와 같이 우선 순위에 따라 확인합니다.
이 문제는 조건이 많기 때문에 천천히 하나씩 구현하고 주어진 데이터를 처리하는 방법을 알아봅시다.
먼저 입력으로 제공된 데이터를 처리해 보겠습니다.
typedef struct Shark
{
int num;
int dir;
pii pos;
}Shark;vector<vector<vector<Shark>>> mp;
vector<vector<pii>> trace;
vector<Shark> sharks;
vector<bool> dead_or_live;
vector<vector<vector<int>>> priority;
총 5개의 벡터를 사용했습니다.
mp 배열은 각 위치에 대한 상어와 상어의 수를 관리하는 데 사용되었습니다.
트레이스 어레이는 각 트레이스를 관리하는 데 사용되었습니다.
Sharks 배열은 각 상어를 관리하는 배열입니다.
dead_or_live 인덱스는 각 상어의 번호를 나타내며 죽었는지 살았는지 확인하는 데 사용됩니다.
우선 순위 배열은 각 상어의 우선 순위를 저장하는 배열입니다.
상어에 대한 정보를 입력하세요
//상어 정보
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int tmp;
cin >> tmp;
sharks(tmp).pos = { i,j };
mp(i)(j).push_back({ tmp,-1, {i,j} });
}
}
for (int i = 1; i <= M; i++)
{
int direction;
cin >> direction;
sharks(i).num = i;
sharks(i).dir = direction;
mp(sharks(i).pos.first)(sharks(i).pos.second)(0).dir = direction;
}각 상어에 대한 우선 입장
//우선순위
priority.resize(M + 1);
for (int i = 1; i <= M; i++)
{
priority(i).resize(5);
for (int j = 1; j <= 4; j++)
{
priority(i)(j).resize(4);
for (int h = 0; h < 4; h++)
{
cin >> priority(i)(j)(h);
}
}
}
다음 이슈에서는 1번 상어가 혼자 남을 때까지 상어가 계속 움직이고 1000초를 넘으면 이슈 -1이라고 했다.
for (int i = 1; i <= 1000; i++)
{
move_shark();
bool flag = false;
for (int j = 2; j <= M; j++)
{
if (dead_or_live(j)) { flag = true; break; }
}
if (!
flag) { cout << i; return 0; }
}
cout << "-1";
다음으로 우리는 상어 운동의 핵심 부분을 살펴봅니다.
먼저 요약하자면
- 상어는 지금 있는 곳에 흔적을 남깁니다.
- 우선순위에 따라 방향을 정하고 해당 위치로 이동합니다.
- 한 위치에 두 마리 이상의 상어가 있는 경우 가장 낮은 번호의 상어만 살아남습니다.
이 시점에서 죽은 상어는 흔적을 남기거나 전혀 움직이지 않습니다.
셀에 여러 상어가 있는 경우 정렬 기준은 상어를 내림차순으로 정렬하고 모두 삭제하여 첫 번째 상어만 남깁니다.
void move_shark()
{
vector<vector<vector<Shark>>> tmp;
tmp.resize(N); for (int i = 0; i < N; i++) tmp(i).resize(N);
//흔적 남기기
for (int i = 1; i <= M; i++)
{
if (dead_or_live(i) == false) continue;
int cur_y = sharks(i).pos.first; int cur_x = sharks(i).pos.second;
trace(cur_y)(cur_x) = { i,K };
}
//상어 이동
for (int i = 1; i <= M; i++)
{
if (dead_or_live(i) == false) continue;
int ndir = next_dir(i, sharks(i).pos);
int cur_y = sharks(i).pos.first; int cur_x = sharks(i).pos.second;
int next_y = cur_y + dy(ndir); int next_x = cur_x + dx(ndir);
sharks(i).dir = ndir; sharks(i).pos = { next_y,next_x };
tmp(next_y)(next_x).push_back(sharks(i));
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//흔적들 남은 시간 감소
if (trace(i)(j).first !
= 0)
{
trace(i)(j).second--;
if (trace(i)(j).second == 0)
trace(i)(j) = { 0,0 };
}
//번호가 가장 낮은 상어만 살아남는다.
if (tmp(i)(j).size() > 1)
{
sort(tmp(i)(j).begin(), tmp(i)(j).end(), cmp);
Shark tmp2 = tmp(i)(j)(0);
for (int h = 1; h < tmp(i)(j).size(); h++)
{
dead_or_live(tmp(i)(j)(h).num) = false;
}
tmp(i)(j).clear(); tmp(i)(j).push_back(tmp2);
}
}
}
mp = tmp;
}
이때 남은 방향을 결정하는 next_dir 함수는 다음과 같다.
int next_dir(int shk_num, pii pos)
{
int cur_dir = sharks(shk_num).dir;
bool flag = false;
int ret = 0;
for (int i = 0; i < 4; i++)
{
int next_dir = priority(shk_num)(cur_dir)(i);
int nx = sharks(shk_num).pos.second + dx(next_dir);
int ny = sharks(shk_num).pos.first + dy(next_dir);
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (trace(ny)(nx).first == 0 && trace(ny)(nx).second == 0) return next_dir;
else
{
if (trace(ny)(nx).first == shk_num && !
flag)
{
ret = next_dir; flag = true;
}
}
}
return ret;
}이 경우 반환된 값은 먼저 공백을 검색합니다.
또한 공백이 없을 경우 네 방향으로 탐색하다가 자신의 번호와 같은 번호의 트랙을 처음 찾으면 방향을 반환합니다.
(전체 소스 코드)
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define INF 987654321
#define mod 1000000
#define pii pair<int,int>
using namespace std;
typedef struct Shark
{
int num;
int dir;
pii pos;
}Shark;
int N, M, K;
int dx(5) = { 0,0,0,-1,1 };
int dy(5) = { 0,-1,1,0,0 };
vector<vector<vector<Shark>>> mp;
vector<vector<pii>> trace;
vector<Shark> sharks;
vector<bool> dead_or_live;
vector<vector<vector<int>>> priority;
bool cmp(Shark& a, Shark& b)
{
return a.num < b.num;
}
int next_dir(int shk_num, pii pos)
{
int cur_dir = sharks(shk_num).dir;
bool flag = false;
int ret = 0;
for (int i = 0; i < 4; i++)
{
int next_dir = priority(shk_num)(cur_dir)(i);
int nx = sharks(shk_num).pos.second + dx(next_dir);
int ny = sharks(shk_num).pos.first + dy(next_dir);
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (trace(ny)(nx).first == 0 && trace(ny)(nx).second == 0) return next_dir;
else
{
if (trace(ny)(nx).first == shk_num && !
flag)
{
ret = next_dir; flag = true;
}
}
}
return ret;
}
void move_shark()
{
vector<vector<vector<Shark>>> tmp;
tmp.resize(N); for (int i = 0; i < N; i++) tmp(i).resize(N);
//흔적 남기기
for (int i = 1; i <= M; i++)
{
if (dead_or_live(i) == false) continue;
int cur_y = sharks(i).pos.first; int cur_x = sharks(i).pos.second;
trace(cur_y)(cur_x) = { i,K };
}
//상어 이동
for (int i = 1; i <= M; i++)
{
if (dead_or_live(i) == false) continue;
int ndir = next_dir(i, sharks(i).pos);
int cur_y = sharks(i).pos.first; int cur_x = sharks(i).pos.second;
int next_y = cur_y + dy(ndir); int next_x = cur_x + dx(ndir);
sharks(i).dir = ndir; sharks(i).pos = { next_y,next_x };
tmp(next_y)(next_x).push_back(sharks(i));
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//흔적들 남은 시간 감소
if (trace(i)(j).first !
= 0)
{
trace(i)(j).second--;
if (trace(i)(j).second == 0)
trace(i)(j) = { 0,0 };
}
//번호가 가장 낮은 상어만 살아남는다.
if (tmp(i)(j).size() > 1)
{
sort(tmp(i)(j).begin(), tmp(i)(j).end(), cmp);
Shark tmp2 = tmp(i)(j)(0);
for (int h = 1; h < tmp(i)(j).size(); h++)
{
dead_or_live(tmp(i)(j)(h).num) = false;
}
tmp(i)(j).clear(); tmp(i)(j).push_back(tmp2);
}
}
}
mp = tmp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
mp.resize(N); trace.resize(N);
for (int i = 0; i < N; i++) { mp(i).resize(N); trace(i).resize(N); }
sharks.resize(M + 1); dead_or_live.resize(M + 1);
for (int i = 1; i <= M; i++) dead_or_live(i) = true;
//상어 정보
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int tmp;
cin >> tmp;
sharks(tmp).pos = { i,j };
mp(i)(j).push_back({ tmp,-1, {i,j} });
}
}
for (int i = 1; i <= M; i++)
{
int direction;
cin >> direction;
sharks(i).num = i;
sharks(i).dir = direction;
mp(sharks(i).pos.first)(sharks(i).pos.second)(0).dir = direction;
}
//우선순위
priority.resize(M + 1);
for (int i = 1; i <= M; i++)
{
priority(i).resize(5);
for (int j = 1; j <= 4; j++)
{
priority(i)(j).resize(4);
for (int h = 0; h < 4; h++)
{
cin >> priority(i)(j)(h);
}
}
}
for (int i = 1; i <= 1000; i++)
{
move_shark();
bool flag = false;
for (int j = 2; j <= M; j++)
{
if (dead_or_live(j)) { flag = true; break; }
}
if (!
flag) { cout << i; return 0; }
}
cout << "-1";
}
딱딱한