마법사 상어와 복제

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

23290번: 마법사 상어와 복제

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
int m, s;
struct MOVE { int x, y; };
MOVE mv[8] = { {0,-1}, {-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1} };
struct INFO { int x, y, d; };
vector<INFO> fish;
INFO shark;
vector<INFO> tmp_fish;
vector<int> smell[4][4];
vector<int> turn;
int maxvalue = -1;
MOVE mv_sh[5] = { {-1,-1}, {-1,0}, {0,-1}, {1,0}, {0,1} };
vector<int> fish_info[4][4];

void MoveFish() {
	for (int i = 0; i < fish.size(); i++) {
		int si = fish[i].x;
		int sj = fish[i].y;
		int dir = fish[i].d;

		for (int k = 0; k < 8; k++) {
			int movei = si + mv[dir].x;
			int movej = sj + mv[dir].y;

			if (movei == shark.x && movej == shark.y) {
				dir--;
				if (dir == -1)	dir = 7;
				continue;
			}

			if (smell[movei][movej].size() > 0) {
				dir--;
				if (dir == -1)	dir = 7;
				continue;
			}

			if (!(movei >= 0 && movei <4 && movej >= 0 && movej < 4)) {
				dir--;
				if (dir == -1)	dir = 7;
				continue;
			}

			fish[i] = { movei,movej,dir };
			break;
		}
	}
}

void MoveShark2(vector<int> t) {
	vector<int> tmp[4][4];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			tmp[i][j] = fish_info[i][j];
		}
	}

	int eat = 0;

	int movei = shark.x;
	int movej = shark.y;

	for (int k = 0; k < 3; k++) {
		movei = movei + mv_sh[t[k]].x;
		movej = movej + mv_sh[t[k]].y;

		if (!(movei >= 0 && movei <4 && movej >= 0 && movej < 4)) {
			eat = -1;
			break;
		}

		eat += tmp[movei][movej].size();
		tmp[movei][movej].clear();
	}

	if (eat != -1) {
		if (eat > maxvalue) {
			turn = t;
			maxvalue = eat;
		}
	}
}

void MakeTurn(vector<int> t) { // 상:1, 좌:2, 하:3, 우:4
	if (t.size() == 3) {
		MoveShark2(t);
		return;
	}

	for (int i = 1; i <= 4; i++) {
		t.push_back(i);
		MakeTurn(t);
		t.pop_back();
	}
}

void MoveShark() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			fish_info[i][j].clear();
		}
	}

	for (int i = 0; i < fish.size(); i++) {
		fish_info[fish[i].x][fish[i].y].push_back(fish[i].d);
	}

	maxvalue = -1;
	turn.clear();
	vector<int> t;
	MakeTurn(t);

	//진짜 움직이고 상어 위치 갱신
	int movei = shark.x;
	int movej = shark.y;
	for (int i = 0; i < 3; i++) {
		movei = movei + mv_sh[turn[i]].x;
		movej = movej + mv_sh[turn[i]].y;

		for(int k=0; k<fish_info[movei][movej].size(); k++)
			smell[movei][movej].push_back(3);

		fish_info[movei][movej].clear();
	}

	fish.clear();
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < fish_info[i][j].size(); k++) {
				fish.push_back({ i,j,fish_info[i][j][k] });
			}
		}
	}

	shark = { movei,movej,-1 };
}

void DeleteSmell() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			vector<int> tmp;
			for (int k = 0; k < smell[i][j].size(); k++) {
				if (smell[i][j][k] - 1 > 0) {
					tmp.push_back(smell[i][j][k] - 1);
				}
			}
			smell[i][j] = tmp;
		}
	}
}

int main(void) {
	cin >> m >> s;

	for (int i = 0; i < m; i++) {
		int x, y, d;
		cin >> x >> y >> d;
		fish.push_back({ x-1,y-1,d-1 });
	}

	int x, y;
	cin >> x >> y;
	shark = { x-1,y-1,-1 };

	for (int testcase = 0; testcase < s; testcase++) {
		tmp_fish = fish; //복제
		MoveFish();
		MoveShark();
		DeleteSmell();

		for (int k = 0; k < tmp_fish.size(); k++) {
			fish.push_back({ tmp_fish[k].x, tmp_fish[k].y, tmp_fish[k].d });
		}
	}

	cout << fish.size() << endl;
	return 0;
}