1- // Authored by : BaaaaaaaaaaarkingDog
1+ // Authored by : H2ll0World
22// Co-authored by : -
3- // http://boj.kr/****************
3+ // http://boj.kr/2c028878405043a6b1edb0ac2ab67f07
4+
5+ // 어른 상어
46#include < bits/stdc++.h>
57using namespace std ;
68
7- int main (void ){
9+ int dy[] = {-1 , 0 , 1 , 0 };
10+ int dx[] = {0 , 1 , 0 , -1 };
11+ pair<int , int > board[400 ][400 ]; // (냄새 지속시간, 냄새 주인)
12+ int preBoard[400 ][400 ]; //
13+ pair<int , int > pos[1001 ]; // 상어의 위치
14+ bool live[1001 ]; // 상어의 생존여부
15+ int curDir[1001 ]; // 상어의 방향
16+ int dirPriority[1001 ][4 ][4 ]; // 상어의 방향 우선순위
17+
18+ // 북쪽을 기준으로 시계방향으로 변함
19+ int changeDir (int dir){
20+ if (dir == 1 )
21+ return 0 ;
22+ else if (dir == 2 )
23+ return 2 ;
24+ else if (dir == 3 )
25+ return 3 ;
26+ else if (dir == 4 )
27+ return 1 ;
28+ }
29+
30+ int main (){
831 ios::sync_with_stdio (0 );
932 cin.tie (0 );
10-
11- }
33+
34+ for (int i = 0 ; i < 400 ; ++i)
35+ fill (board[i], board[i] + 400 , std::make_pair (0 , 0 ));
36+
37+ for (int i = 0 ; i < 400 ; ++i)
38+ fill (preBoard[i], preBoard[i] + 400 , -1 );
39+
40+ fill (live, live + 1001 , true );
41+
42+ int n, m, k; // n : 격자의 크기 // m : 상어의 숫자 // k : 냄새의 지속 시간
43+ cin >> n >> m >> k;
44+
45+ int tmp;
46+ for (int i = 0 ; i < n; i++)
47+ for (int j = 0 ; j < n; j++){
48+ cin >> tmp;
49+ if (tmp != 0 ) {
50+ pos[tmp] = make_pair (i, j);
51+ board[i][j].first = k; //
52+ board[i][j].second = tmp;
53+ }
54+ }
55+
56+ for (int i = 1 ; i <= m; i++){
57+ cin >> tmp;
58+ curDir[i] = changeDir (tmp);
59+ }
60+
61+ for (int i = 1 ; i <= m; i++)
62+ for (int j = 1 ; j <= 4 ; j++)
63+ for (int z = 0 ; z < 4 ; z++){
64+ cin >> tmp;
65+ dirPriority[i][changeDir (j)][z] = changeDir (tmp);
66+ }
67+
68+ int dir;
69+ int ny, nx;
70+ int liveCnt = m;
71+ int time ;
72+ for (time = 1 ; time <= 1002 ; time ++){
73+ // 상어 이동
74+ if (liveCnt == 1 ) break ;
75+ for (int i = 1 ; i <= m; i++){
76+ if (live[i] == 0 ) continue ; // 나간 경우
77+
78+ int j;
79+ bool fir = 1 ; // 자신의 냄새
80+ int myY, myX;
81+ int myDir;
82+ for (j = 0 ; j < 4 ; j++){
83+ dir = dirPriority[i][curDir[i]][j];
84+ ny = pos[i].first + dy[dir]; nx = pos[i].second + dx[dir];
85+
86+ if (ny < 0 || ny >= n || nx < 0 || nx >= n) // OOB : Out of Bound
87+ continue ;
88+
89+ if (board[ny][nx].first == time + k && time > preBoard[ny][nx]){ // 1. 냄새가 없는 칸이 있는 경우, 우선순위가 높은 상어와 같이 방문한 경우
90+ // 우선순위가 높은 상어가 있음
91+ live[i] = 0 ; // 쫓겨남
92+ liveCnt--;
93+ break ;
94+ }else if (time <= board[ny][nx].first ){ // 냄새가 남아있어서 방문 X
95+ if (fir && board[ny][nx].second == i){ // 그 냄새가 자신의 것인 경우
96+ myY = ny; myX = nx;
97+ myDir = dir;
98+ fir = 0 ;
99+ }
100+ continue ;
101+ }
102+ preBoard[ny][nx] = board[ny][nx].first ;
103+ board[ny][nx].first = time + k;
104+ board[ny][nx].second = i;
105+
106+ pos[i].first = ny;
107+ pos[i].second = nx;
108+ curDir[i] = dir;
109+
110+ break ;
111+ }
112+ if (j == 4 ){ // 2. 냄새가 없는 칸이 없는 경우 -> 자신의 냄새로 이동
113+ preBoard[myY][myX] = board[myY][myX].first ;
114+ board[myY][myX].first = time + k;
115+ pos[i].first = myY; pos[i].second = myX;
116+ curDir[i] = myDir;
117+ }
118+ }
119+ }
120+
121+ time --;
122+ if (time > 1000 ){
123+ cout << -1 << ' \n '
124+ return 0 ;
125+ }
126+
127+ cout << time << ' \n '
128+ return 0 ;
129+ }
0 commit comments