어른상어/ 시뮬레이션

www.acmicpc.net/problem/19237

19237번: 어른 상어

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>
using namespace std;

struct shark {

	int num;
	int dir; //-1 die
	int x;
	int y;

};
int n, m, k;
int dirlookup[5][5][5]; 
vector<vector<pair<int,int>>>arr(21, vector<pair<int,int>>(21, make_pair(0,0)));

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

bool cango(int x, int y)
{
	return x >= 0 && y >= 0 && x < m && y < n;
}

void searchNewDir(shark & shark) {
		
	int num = shark.num;
	int dir = shark.dir;
	int x = shark.x;
	int y = shark.y;
	
	int canddir = 0;

	bool toggle = false;

	for (int i = 0; i < 4; i++) {
		
		int ndir = dirlookup[num][dir][i];
		int nx = x+dx[ndir];
		int ny = y+dy[ndir];

		if (cango(nx,ny)&& (arr[nx][ny].first == 0)) {
			dir = ndir;
			toggle = true;
			break;
		}
		else if (cango(nx, ny)&& (arr[nx][ny].first == num)) {

			canddir = ndir;
		}
	}

	
	if (toggle == true) {
		shark.dir = dir;
	}
	else {
		shark.dir = canddir;
	}
	
}


void minusSmell() {
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
		
			
			if (arr[i][j].second > 1) {
				--arr[i][j].second;
			}
			else if (arr[i][j].second == 1) {
			
				arr[i][j].second = 0;
				arr[i][j].first = 0;
					
			}

		
		}
	
	}


}


void move(vector<shark>&sharkList) {


	map<pair<int, int>, int>m;
	
	for (int i = 0; i < sharkList.size(); i++) {
		
		int dir = sharkList[i].dir;
		if (dir == -1) { continue; }

		int x = sharkList[i].x;
		int y = sharkList[i].y;

		int num = sharkList[i].num;
		
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		pair<int, int> p = make_pair(nx, ny);
		if (m.find(p) != m.end()) {
				
			if (m[p] < num) {
				sharkList[i] = { num,-1,-1,-1 };
				continue;
			}
			else {
			
				sharkList[m[p] - 1] = { num,-1,-1,-1 };
		
			}
			
		}

		m[p] = num;
		sharkList[i].x = nx;
		sharkList[i].y = ny;
	
	}


	minusSmell();


	map<pair<int, int>, int>::iterator it;

	for (it = m.begin(); it != m.end(); it++) {
			
		arr[it->first.first][it->first.second] = make_pair(it->second,k);
		
	}

}


bool check(vector<shark>&sharkList) {
	
	for (int i = 0; i < sharkList.size(); i++) {
		if (sharkList[i].dir != -1) { return false; }
	}
	return true;
}



int simulate(vector<shark>&sharkList) {

	int count = 1;
	while (count <= 1000) {

		for (int i = 0; i < sharkList.size(); i++) {

			if (sharkList[i].dir == -1) { continue; }
			searchNewDir(sharkList[i]);
		}
		move(sharkList);
		if (check(sharkList)) {

			break;

		}
		
		count++;

	}
	return count;

}



int main(vector<shark>&sharkList) {


	cin >> n;
	cin >> m;
	cin >> k; // 냄새 사라지는데 까지 이동횟수

	vector<shark>sharkList(m);
	int idx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			if (num != 0) {
				
				arr[i][j].first = num;
				arr[i][j].second = k;
				shark shark;
				shark.num = num;
				shark.x = i;
				shark.y = j;
				sharkList[idx] = shark;
				idx++;
			
			}
			
		}
	}



	for (int i = 0; i < m; i++) {
		
		cin >> sharkList[i].dir;
	
	}

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin>> dirlookup[i][j][k];
			}
		}
	}

	cout << simulate(sharkList)<<endl;


}