어른상어

www.acmicpc.net/problem/19237

19237번: 어른 상어

#include <iostream>

using namespace std;

int n, m, k, ret;
int board[20][20][3]; // 위치 상어 번호 / 냄새의 상어 번호 / 냄새 강도
struct SHARK {
	int y, x, d;
	int priority[4][4];
};
SHARK shark[400];

int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

void solve() {
	int time = 0;
	int kill_shark = 0;
	while (time <= 1000) {
		time++;
		int new_board[20][20][3] = { 0, };
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				new_board[y][x][0] = board[y][x][0];
				new_board[y][x][2] = board[y][x][2];
				if (new_board[y][x][2] > 0) { new_board[y][x][2]--; }
				if (new_board[y][x][2] > 0) { new_board[y][x][1] = board[y][x][1]; }
			}
		}
		for (int i = 0; i < m; i++) {
			int cy = shark[i].y;
			int cx = shark[i].x;
			int cd = shark[i].d;
			if (cy == -1) continue;
			bool is_move = false;
			for (int d = 0; d < 4; d++) {
				int nd = shark[i].priority[cd][d];
				int ny = cy + dy[nd];
				int nx = cx + dx[nd];
				if (ny < 0 || ny >= n || nx < 0 || nx >= n || board[ny][nx][2]) continue;
				is_move = true;
				new_board[cy][cx][0] = 0;
				if (new_board[ny][nx][0] == 0) {
					new_board[ny][nx][0] = i + 1;
					new_board[ny][nx][1] = i + 1;
					new_board[ny][nx][2] = k;
					shark[i].y = ny;
					shark[i].x = nx;
					shark[i].d = nd;
				}
				else {
					kill_shark++;
					shark[i].y = -1;
				}
				break;
			}
			if (is_move == false) {
				for (int d = 0; d < 4; d++) {
					int nd = shark[i].priority[cd][d];
					int ny = cy+dy[nd];
					int nx = cx+dx[nd];
					if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
					if (board[ny][nx][2] && board[ny][nx][1] != i + 1) continue;
					new_board[cy][cx][0] = 0;
					if (new_board[ny][nx][0] == 0) {
						new_board[ny][nx][0] = i + 1;
						new_board[ny][nx][1] = i + 1;
						new_board[ny][nx][2] = k;
						shark[i].y = ny;
						shark[i].x = nx;
						shark[i].d = nd;
					}
					else {
						kill_shark++;
						shark[i].y = -1;
					}
					break;
				}
			}
		}
		if (kill_shark == m - 1) break;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				board[y][x][0] = new_board[y][x][0];
				board[y][x][1] = new_board[y][x][1];
				board[y][x][2] = new_board[y][x][2];
			}
		}
	}
	if (time <= 1000) ret = time;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	ret = -1;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> board[y][x][0];
			if (board[y][x][0]) {
				int shark_number = board[y][x][0] - 1;
				shark[shark_number].y = y;
				shark[shark_number].x = x;
				board[y][x][1] = board[y][x][0];
				board[y][x][2] = k;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> shark[i].d;
		shark[i].d--;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> shark[i].priority[j][0] >> shark[i].priority[j][1] >> shark[i].priority[j][2] >> shark[i].priority[j][3];
			shark[i].priority[j][0]--;
			shark[i].priority[j][1]--;
			shark[i].priority[j][2]--;
			shark[i].priority[j][3]--;
		}
	}
	solve();
	cout << ret << "\n";
	return 0;
}