#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int ans;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int board[25][25];
int t_board[25][25];
pair<int,int> pheromone[25][25];
pair<int,int> t_pheromone[25][25];
struct shark{
int y;
int x;
int dir;
};
vector<int> shark_pri[4][410];
vector<shark> shark_v(410);
int N,M,k;
int saveDir(int d){
if(d > 3) d-=4;
if(d < 0) d+=4;
return d;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> k;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
cin >> board[i][j];
if(board[i][j] == 0) continue;
shark_v[board[i][j]].y = i;
shark_v[board[i][j]].x = j;
pheromone[i][j] = {board[i][j], k};
}
for(int i=1;i<=M;i++)
{
int d;
cin >> d;
shark_v[i].dir = d-1;
}
for(int i=1;i<=M;i++)
{
for(int j=0;j<4;j++)
{
int p1,p2,p3,p4;
cin >> p1 >> p2 >> p3 >> p4;
shark_pri[j][i].push_back(p1-1);
shark_pri[j][i].push_back(p2-1);
shark_pri[j][i].push_back(p3-1);
shark_pri[j][i].push_back(p4-1);
}
}
while(true)
{
ans++;
for(int i=1;i<=M;i++)
{
bool empty_space = false;
auto cur = shark_v[i];
if(cur.y == -1) continue;
for(int n=0;n<4;n++)
{
int ndir = shark_pri[cur.dir][i][n];
int ny = cur.y + dy[ndir];
int nx = cur.x + dx[ndir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
if(pheromone[ny][nx].second > 0) continue;
if(t_board[ny][nx] != 0 and t_board[ny][nx] < i){
empty_space = true;
shark_v[i].y = -1;
shark_v[i].x = -1;
shark_v[i].dir = -1;
break;
}
t_pheromone[ny][nx] = {i, k};
shark_v[i].y = ny;
shark_v[i].x = nx;
shark_v[i].dir = ndir;
t_board[ny][nx] = i;
empty_space = true;
break;
}
if(empty_space == true) continue;
for(int n=0;n<4;n++)
{
int ndir = shark_pri[cur.dir][i][n];
int ny = cur.y + dy[ndir];
int nx = cur.x + dx[ndir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
if(pheromone[ny][nx].first != i) continue;
t_pheromone[ny][nx] = {i, k};
shark_v[i].y = ny;
shark_v[i].x = nx;
shark_v[i].dir = ndir;
t_board[ny][nx] = i;
break;
}
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(pheromone[i][j].second == 0) continue;
pheromone[i][j].second--;
if(pheromone[i][j].second == 0)
pheromone[i][j] = {0, 0};
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(t_pheromone[i][j].second == 0) continue;
pheromone[i][j] = t_pheromone[i][j];
t_pheromone[i][j] = {0,0};
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
board[i][j] = t_board[i][j];
t_board[i][j] = 0;
}
int cnt=0;
for(int i=1;i<=M;i++)
if(shark_v[i].y != -1) cnt++;
if(cnt == 1) break;
else if(ans >= 1000){
ans = -1;
break;
}
}
cout << ans;
return 0;
}
- 핵심
동시에 일어나는 일
이기 때문에 비어있는 임시배열
을 이용
하는 것
: board[][]
와 pheromone[][]
으로 비교
t_board[][]
와 t_pheromone[][]
에 저장
상어의 정보
를 응집
하기 위해 shark 구조체
사용
- 이상한 점
: 해당 문제에서 1000이 넘으면 종료
된다고 문제에 나와있으나 1000이 되어도 -1로 처리
를 해야함
--> 많은 사람들이 이것으로 오답처리
됨