어른 상어 C++

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

19237번: 어른 상어

 

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

using namespace std;
const int MAX = 21;
struct MAP_INFO { int num, exist, smell; };
vector<MAP_INFO> map[MAX][MAX]; //상어 넘버, 지금 들어온 애(0:이전, 1:지금), 냄새
int n, m, K;
struct MOVE { int x, y; };
MOVE mv[5] = { { 0,0 },{ -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //1:위,2:아래,3:왼쪽,4:오른쪽
struct INFO { int num, x, y,dir; };
vector<INFO> shark;
int pri[401][5][5];

bool cmp(MAP_INFO a, MAP_INFO b) {
	return a.num < b.num;
}

void MoveShark() {
	vector<INFO> temp_shark;

	for (int i = 0; i < shark.size(); i++) {
		int ii = shark[i].x;
		int jj = shark[i].y;
		int currentdir = shark[i].dir;

		bool flag = false;

		for (int k = 1; k < 5; k++) {
			int movei = ii + mv[pri[shark[i].num][currentdir][k]].x;
			int movej = jj + mv[pri[shark[i].num][currentdir][k]].y;

			if( movei >=0 && movei <n && movej >=0 && movej <n){
				if (map[movei][movej][0].smell == 0) {
					flag = true;
					map[movei][movej].push_back({ shark[i].num,1,K });
					temp_shark.push_back({ shark[i].num,movei,movej,pri[shark[i].num][currentdir][k] });
					break;
				}
			}
		}
		
		if (flag == false) {
			for (int k = 1; k < 5; k++) {
				int movei = ii + mv[pri[shark[i].num][currentdir][k]].x;
				int movej = jj + mv[pri[shark[i].num][currentdir][k]].y;

				if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
					if (map[movei][movej][0].num == shark[i].num) {
						flag = true;
						map[movei][movej].push_back({ shark[i].num,1,K });
						temp_shark.push_back({ shark[i].num,movei,movej,pri[shark[i].num][currentdir][k] });
						break;
					}
				}
			}
		}
	}
	shark = temp_shark;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j].size() > 1) {
				sort(map[i][j].begin(), map[i][j].end(), cmp);
				map[i][j][0] = map[i][j][1];
				for (int k = 2; k < map[i][j].size(); k++) {
					for (int z = 0; z < shark.size(); z++) {
						if (shark[z].num == map[i][j][k].num) {
							shark.erase(shark.begin() + z);
							break;
						}
					}
				}
				map[i][j].erase(map[i][j].begin() + 1, map[i][j].end());
			}
		}
	}
}

void DecreaseSmell() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j][0].smell > 1 && map[i][j][0].exist == 0)
				map[i][j][0].smell -= 1;
			else if (map[i][j][0].smell == 1)
				map[i][j][0] = { 0,0,0 };

			if (map[i][j][0].exist == 1)
				map[i][j][0].exist = 0;
		}
	}
}

int main(void) {
	int answer = 0;

	cin >> n >> m >> K;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			if (num == 0)	map[i][j].push_back({ 0,0,0 });
			else {
				map[i][j].push_back({ num,0,K });
				shark.push_back({ num,i,j,0 });
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		int direction;
		cin >> direction;
		for (int j = 0; j < shark.size(); j++) {
			if (shark[j].num == i) {
				shark[j].dir = direction;
				break;
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j < 5; j++) {
			for (int k = 1; k < 5; k++) {
				cin >> pri[i][j][k];
			}
		}
	}

	while (answer < 1000) {
		MoveShark();
		DecreaseSmell();
		answer += 1;
		if (shark.size() == 1)
			break;
	}
	if (answer <= 1000 && shark.size() == 1)
		cout << answer << endl;
	else
		cout << -1 << endl;
}