1- // Authored by : BaaaaaaaaaaarkingDog
1+ // Authored by : sukam09
22// Co-authored by : -
3- // http://boj.kr/****************
3+ // http://boj.kr/430a59896f24436bb00c38ad66dfce55
44#include < bits/stdc++.h>
55using namespace std ;
66
7- int main (void ){
7+ int m, s;
8+ int x, y; // 상어 위치
9+ // ↑, ←, ↓, →(사전순)
10+ int dx1[4 ] = {-1 , 0 , 1 , 0 };
11+ int dy1[4 ] = {0 , -1 , 0 , 1 };
12+ // ←, ↖, ↑, ↗, →, ↘, ↓, ↙
13+ int dx2[8 ] = {0 , -1 , -1 , -1 , 0 , 1 , 1 , 1 };
14+ int dy2[8 ] = {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1 };
15+ vector<int > fish[4 ][4 ];
16+ int smell[4 ][4 ]; // 가장 최근에 물고기 냄새가 생성된 턴, 없으면 0
17+ int turn = 1 ;
18+
19+ bool OOB (int x, int y) {
20+ return x < 0 || x >= 4 || y < 0 || y >= 4 ;
21+ }
22+
23+ // 상어가 i, j, k 방향으로 이동했을 때 제외되는 물고기의 수를 구하는 함수
24+ int move (int i, int j, int k) {
25+ // 상어가 갔던 칸을 다시 방문할 경우 수를 잘못 셀 수 있으므로
26+ // 남은 물고기의 수를 나타내는 임시 격자를 사용
27+ vector<vector<int >> tmp (4 , vector<int >(4 ));
28+ for (int i = 0 ; i < 4 ; i++)
29+ for (int j = 0 ; j < 4 ; j++)
30+ tmp[i][j] = (int )fish[i][j].size ();
31+ int cnt = 0 ;
32+ int xx = x;
33+ int yy = y;
34+ for (auto z : {i, j, k}) {
35+ int nx = xx + dx1[z];
36+ int ny = yy + dy1[z];
37+ if (OOB (nx, ny)) return -1 ;
38+ cnt += tmp[nx][ny];
39+ tmp[nx][ny] = 0 ;
40+ xx = nx;
41+ yy = ny;
42+ }
43+ return cnt;
44+ }
45+
46+ // 제외되는 물고기가 가장 많은 방향을 구하는 함수
47+ tuple<int , int , int > brute () {
48+ vector<tuple<int , int , int , int >> ret;
49+ for (int i = 0 ; i < 4 ; i++) {
50+ for (int j = 0 ; j < 4 ; j++) {
51+ for (int k = 0 ; k < 4 ; k++) {
52+ int cnt = move (i, j, k);
53+ if (cnt == -1 ) continue ; // OOB
54+ // cnt를 음수로 넣어줌으로써 오름차순으로 정렬해도 되게끔 함
55+ ret.push_back ({ -cnt, i, j, k });
56+ }
57+ }
58+ }
59+ sort (ret.begin (), ret.end ());
60+ int cnt, i, j, k;
61+ tie (cnt, i, j, k) = ret[0 ];
62+ return { i, j, k };
63+ }
64+
65+ void solve () {
66+ // 1
67+ vector<tuple<int , int , int >> copied;
68+ for (int i = 0 ; i < 4 ; i++)
69+ for (int j = 0 ; j < 4 ; j++)
70+ for (auto d : fish[i][j])
71+ copied.push_back ({ i, j, d });
72+ // 2
73+ vector<int > nxt[4 ][4 ]; // 물고기가 이동을 완료한 상태의 격자
74+ for (int i = 0 ; i < 4 ; i++) {
75+ for (int j = 0 ; j < 4 ; j++) {
76+ for (auto d : fish[i][j]) {
77+ bool chk = false ;
78+ for (int dir = 0 ; dir < 8 ; dir++) {
79+ int nd = (d - dir + 8 ) % 8 ;
80+ int nx = i + dx2[nd];
81+ int ny = j + dy2[nd];
82+ if (OOB (nx, ny) || smell[nx][ny] != 0 || (nx == x && ny == y))
83+ continue ;
84+ nxt[nx][ny].push_back (nd);
85+ chk = true ;
86+ break ;
87+ }
88+ // 물고기가 움직이지 않을 경우에도 똑같은 위치에 넣어줘야함
89+ if (!chk) nxt[i][j].push_back (d);
90+ }
91+ }
92+ }
93+ for (int i = 0 ; i < 4 ; i++)
94+ for (int j = 0 ; j < 4 ; j++)
95+ fish[i][j] = nxt[i][j];
96+ // 3
97+ int i, j, k;
98+ tie (i, j, k) = brute ();
99+ // 상어 이동
100+ for (auto z : { i, j, k }) {
101+ int nx = x + dx1[z];
102+ int ny = y + dy1[z];
103+ // 물고기가 존재할 경우에만 물고기 냄새를 남김
104+ if (!fish[nx][ny].empty ()) {
105+ smell[nx][ny] = turn;
106+ fish[nx][ny].clear ();
107+ }
108+ x = nx;
109+ y = ny;
110+ }
111+ // 4
112+ for (int i = 0 ; i < 4 ; i++)
113+ for (int j = 0 ; j < 4 ; j++)
114+ if (smell[i][j] + 2 == turn)
115+ smell[i][j] = 0 ;
116+ // 5
117+ for (auto & x : copied) {
118+ int r, c, d;
119+ tie (r, c, d) = x;
120+ fish[r][c].push_back (d);
121+ }
122+ }
123+
124+ int main (void ) {
8125 ios::sync_with_stdio (0 );
9126 cin.tie (0 );
10-
127+ cin >> m >> s;
128+ for (int i = 0 ; i < m; i++) {
129+ int r, c, d;
130+ cin >> r >> c >> d;
131+ r--; c--; d--; // 0-index
132+ fish[r][c].push_back (d);
133+ }
134+ cin >> x >> y;
135+ x--; y--; // 0-index
136+ while (s--) {
137+ solve ();
138+ turn++;
139+ }
140+ int ans = 0 ;
141+ for (int i = 0 ; i < 4 ; i++)
142+ for (int j = 0 ; j < 4 ; j++)
143+ ans += (int )fish[i][j].size ();
144+ cout << ans;
11145}
0 commit comments