어른 상어 C++

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

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

using namespace std;
const int MAX = 25;
int map[MAX][MAX];
pair<int, int> info[MAX][MAX]; //상어 번호(없으면 -1), 냄새 시간
int n, m, k;
struct MOVE { int x, y; };
MOVE mv[4] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<pair<int, int>> shark; //상어 위치
struct INFO { int cur, dir[4][4]; };
vector<INFO> d;
int answer = 0;

bool checkEmpty() {
	bool flag = false;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] > 1) {
				flag = true;
				break;
			}
		}
	}

	return flag;
}

void MoveShark() {
	vector<int> tmp[MAX][MAX];

	for (int i = 0; i < shark.size(); i++) {
		int mysmell = -1;
		int mi = shark[i].first;
		int mj = shark[i].second;
		int num = map[mi][mj];
		int cur_dir = d[num].cur;
		bool flag = false;
		
		for (int k = 0; k < 4; k++) {
			int movei = mi + mv[d[num].dir[cur_dir][k]].x;
			int movej = mj + mv[d[num].dir[cur_dir][k]].y;

			if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
				if (info[movei][movej] == make_pair(-1, -1)) {
					tmp[movei][movej].push_back(num);
					shark[i] = make_pair(movei, movej);
					d[num].cur = d[num].dir[cur_dir][k];
					flag = true;
					break;
				}
				else if (info[movei][movej].first == num && mysmell == -1) {
					mysmell = k;
				}
			}
		}

		if (flag == false) {
			int movei = mi + mv[d[num].dir[cur_dir][mysmell]].x;
			int movej = mj + mv[d[num].dir[cur_dir][mysmell]].y;

			tmp[movei][movej].push_back(num);
			shark[i] = make_pair(movei, movej);
			d[num].cur = d[num].dir[cur_dir][mysmell];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (tmp[i][j].size() > 1) {
				int min_index;
				int value = 987654321;
				for (int k = 0; k < tmp[i][j].size(); k++) {
					if (tmp[i][j][k] < value) {
						min_index = k;
						value = tmp[i][j][k];
					}
				}
				map[i][j] = value;
				for (int k = 0; k < tmp[i][j].size(); k++) {
					if (k != min_index) {
						int v = find(shark.begin(), shark.end(), make_pair(i, j))-shark.begin();
						shark.erase(shark.begin() + v);
					}
				}
			}
			else {
				if (tmp[i][j].size() == 1) {
					map[i][j] = tmp[i][j][0];
				}
				else {
					map[i][j] = 0;
				}
			}
		}
	}
}

void MoveSmell() {
	//지금자리에 냄새 뿌리고, 냄새 -1 해주기

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (info[i][j] != make_pair(-1, -1)) {
				info[i][j].second -= 1;
				if (info[i][j].second <= 0) {
					info[i][j] = make_pair(-1, -1);
				}
			}
		}
	}

	for (int i = 0; i < shark.size(); i++) {
		int mi = shark[i].first;
		int mj = shark[i].second;
		int num = map[mi][mj];

		info[mi][mj] = make_pair(num, k);
	}
}

int main(void) {
	cin >> n >> m >> k;

	d.resize(m+1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			info[i][j] = make_pair(-1, -1);
			cin >> map[i][j];
			if (map[i][j] != 0) {
				shark.push_back(make_pair(i, j));
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		int direciton;
		cin >> direciton;
		d[i].cur = direciton-1;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				int K;
				cin >> K;
				d[i].dir[j][k] = K - 1;
			}
		}
	}


	while (checkEmpty()) {
		MoveSmell();
		MoveShark();
		answer++;
		if (answer == 1001) {
			break;
		}
	}

	if (answer > 1000)	cout << -1 << endl;
	else cout << answer << endl;
}