19237번 어른 상어

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int shark[20][20];
int shark_next[20][20];
int priority[401][4][4];
int smell[20][20];
int smell_who[20][20];
int dir[401];
int n, m, smell_time;
void shark_move() {
	vector<tuple<int, int, int>> v;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			shark_next[i][j] = 0;
			if (shark[i][j] != 0) {
				v.push_back(make_tuple(shark[i][j], i, j));
			}
		}
	}
	sort(v.begin(), v.end());
	for (auto& t : v) {
		int no, x, y;
		tie(no, x, y) = t;
		bool ok = false;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[priority[no][dir[no]][k]];
			int ny = y + dy[priority[no][dir[no]][k]];
			if (nx < n && nx >= 0 && ny < n && ny >= 0) {
				if (smell[nx][ny] == 0) {
					if (shark_next[nx][ny] == 0|| shark_next[nx][ny] > no) {
						shark_next[nx][ny] = no;
						dir[no] = priority[no][dir[no]][k];
					}
					ok = true;
					break;
				}
			}
			if (ok) break;
		}
		if (!ok) {
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[priority[no][dir[no]][k]];
				int ny = y + dy[priority[no][dir[no]][k]];
				if (nx < n && nx >= 0 && ny < n && ny >= 0) {
					if (smell[nx][ny]>0&&smell_who[nx][ny] == no) {
						shark_next[nx][ny] = no;
						dir[no] = priority[no][dir[no]][k];
						ok = true;
						break;
					}
				}
				if (ok) break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			shark[i][j] = shark_next[i][j];
			if (smell[i][j] > 0) smell[i][j]--;
			if (smell[i][j] == 0) smell_who[i][j] = 0;
			if (shark[i][j] > 0) {
				smell[i][j] = smell_time;
				smell_who[i][j] = shark[i][j];
			}
		}
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	cin >> n >> m >> smell_time;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> shark[i][j];
			if (shark[i][j] != 0) {
				smell[i][j] = smell_time;
				smell_who[i][j] = shark[i][j];
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> dir[i];
		dir[i]--;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> priority[i][j][k];
				priority[i][j][k]--;
			}
		}
	}
	
	int ans = 0;
	for (ans = 1; ans <= 1000; ans++) {
		shark_move();
		bool ok = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (shark[i][j] >1) {
					ok = true;
					break;
				}
			}
			if (ok) break;
		}
		if (ok == false) {
			cout << ans << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
	return 0;
}