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