이동 우선순위 정보를 저장하기 위해 각 상어의 구조체 내에 우선순위 정보를 저장하기 위한 배열을 두고 문제를 풀었다.
여러 마리의 상어가 한 격자 위에 존재할 수 있는 경우는 빈 격자에 동시에 여러 마리의 상어가 위치할 때다.
이때 기존의 map을 실시간으로 업데이트 하게 되면, 동시에 이동 이라는 조건을 충족시키지 못하므로 n_map 을 두어 n_map에 업데이트된 상어의 정보를 저장하였다.
즉, map을 기반으로 상어의 이동 여부를 결정하며, 이동 후 정보는 n_map에 저장했다.
가장 작은 번호를 가진 상어만 생존하므로, n_map을 업데이트 할 때 이미 상어에 대한 정보가 있는지 확인한 후, 현재 이동시키고자 하는 상어의 번호가 더 적을 경우에만 업데이트 해주었다.
격자 밖으로 쫓겨나는 상어에 대해서는 상어의 live를 false로 업데이트 해주었다.
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct intfo {
int s_num;
int k;
} info;
info map[21][21];
typedef struct shark {
int x;
int y;
int dir;
int pri[5][5];
bool live;
};
shark Shark[401];
int N, M, k, rst;
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 };
void input() {
cin >> N >> M >> k;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int s_num;
cin >> s_num;
if (s_num > 0) {
map[i][j].s_num = s_num;
Shark[s_num].x = i;
Shark[s_num].y = j;
Shark[s_num].live = true;
}
else {
map[i][j].s_num = -1;
}
map[i][j].k = 0;
}
}
for (int s_num = 1; s_num <= M; s_num++){
cin >> Shark[s_num].dir;
}
for (int s_num = 1; s_num <= M; s_num++) {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
cin >> Shark[s_num].pri[i][j];
}
}
}
rst = 0;
}
int is_left_one() {
for (int i = 2; i <= M; i++) {
if (Shark[i].live) return false;
}
return true;
}
int is_range(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N) return true;
return false;
}
void move_shark() {
info n_map[21][21];
for (int i = 0; i < N; i++) { //copy map
for (int j = 0; j < N; j++) {
n_map[i][j] = map[i][j];
}
}
for (int s_num = 1; s_num <= M; s_num++) {
if (!Shark[s_num].live) continue;
int x = Shark[s_num].x;
int y = Shark[s_num].y;
int dir = Shark[s_num].dir;
bool move_done = false;
for (int i = 1; i <= 4; i++) { // no smell
int ndir = Shark[s_num].pri[dir][i];
int nx = x + dx[ndir];
int ny = y + dy[ndir];
if (!is_range(nx, ny)) continue;
if (map[nx][ny].s_num == -1) { // can go
move_done = true;
if (n_map[nx][ny].s_num != -1) { // shark already exists
if (s_num < n_map[nx][ny].s_num) { // my number is smaller than old one
Shark[n_map[nx][ny].s_num].live = false; // kill the old shrak
}
else { // my number is bigger than old one
Shark[s_num].live = false;
break;
}
}
n_map[nx][ny].s_num = s_num;
n_map[nx][ny].k = k;
Shark[s_num].dir = ndir;
Shark[s_num].x = nx;
Shark[s_num].y = ny;
break;
}
}
if (move_done) continue;
for (int i = 1; i <= 4; i++) { // own smell
int ndir = Shark[s_num].pri[dir][i];
int nx = x + dx[ndir];
int ny = y + dy[ndir];
if (!is_range(nx, ny)) continue;
if (map[nx][ny].s_num == s_num) {
n_map[nx][ny].s_num = s_num;
n_map[nx][ny].k = k;
Shark[s_num].dir = ndir;
Shark[s_num].x = nx;
Shark[s_num].y = ny;
break;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = n_map[i][j];
}
}
}
void decrease_k() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j].k > 0) map[i][j].k--;
if (map[i][j].k == 0) map[i][j].s_num = -1;
}
}
for (int s_num = 1; s_num <= M; s_num++) {
if (!Shark[s_num].live) continue;
int x = Shark[s_num].x;
int y = Shark[s_num].y;
map[x][y].k = k;
}
}
void solve() {
for (int i = 1; i <= M; i++) {
int x = Shark[i].x;
int y = Shark[i].y;
map[x][y].k = k;
}
while (!is_left_one()) {
if (rst == 1000) {
rst = -1;
break;
}
rst++;
move_shark();
decrease_k();
}
}
int main() {
input();
solve();
cout << rst << endl;
}
1) 상어를 이동시킨다. 이동 위치를 저장하는 구조체를 따로 만들어 정보를 저장해 둔다.
2) 전체적으로 k를 감소시킨다.
3) 가장 적은 번호의 상어부터 map에 update를 시킨다. 이때 k가 세팅된다.
4) update하고자 하는 위치에 상어가 없다면, 상어 정보를 해당 위치에 update 한다.
5) update하고자 하는 위치에 상어가 이미 있고(상어 번호가 이미 세팅된 상태), 나의 번호와 같을 경우 상어는 자신이 냄새를 뿌린 곳으로 간 것이다.
6) update하고자 하는 위치에 상어가 이미 있고, 나의 번호와 다를 경우 그 상어는 격자 밖으로 쫓겨난다. (가장 작은 번호의 상어부터 update를 하는데 이미 자신보다 더 작은 번호의 상어가 도달했다는 뜻이므로)