청소년 상어 C++

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

19236번: 청소년 상어

 

#include <iostream>

using namespace std;
const int MAX = 5;
struct MOVE { int x, y; };
MOVE mv[8] = { { -1,0 },{ -1,-1 },{ 0,-1 },{ 1,-1 },{ 1,0 },{ 1,1 },{ 0,1 }, {-1,1} };
struct INFO { int num, dir; };
INFO map[MAX][MAX];
pair<int, pair<int, int>> loc; //방향, 위치 // {0,0}이면 비어있는 칸
pair<int, int> fish[17]; //{0,0}이면 사라진 물고기

void MoveFish(pair<int, pair<int, int>> shark) {
	for (int i = 1; i <= 16; i++) {
		if (fish[i] != make_pair(0, 0)) {
			int currentdir = map[fish[i].first][fish[i].second].dir;
			int cu_i = fish[i].first;
			int cu_j = fish[i].second;

			for (int k = 0; k < 9; k++) {
				if (currentdir == 9)	currentdir = 1;
				int movei = cu_i + mv[currentdir - 1].x;
				int movej = cu_j + mv[currentdir - 1].y;

				if (!(movei > 0 && movei <= 4 && movej > 0 && movej <= 4) || (shark.second.first == movei && shark.second.second == movej)) {
					currentdir += 1;
					continue;
				}

				//비어있는 칸
				if (map[movei][movej].dir == 0 && map[movei][movej].num == 0) {
					map[fish[i].first][fish[i].second] = { 0,0 };
					map[movei][movej] = { i,currentdir };
					fish[i] = make_pair(movei,movej);
					break;
				}
				//다른 물고기가 있는 칸
				else {
					fish[map[movei][movej].num] = { fish[i].first,fish[i].second };
					map[fish[i].first][fish[i].second] = map[movei][movej];
					map[movei][movej] = { i,currentdir };
					fish[i] = make_pair(movei,movej);
					break;
				}
				currentdir += 1;
			}
		}
	}
}

int EatFish(pair<int, pair<int, int>> shark,int answer) {
	
	int value = answer;

	INFO map_temp[MAX][MAX];
	pair<int, int> fish_temp[17]; 

	for (int i = 1; i <= 4 ; i++) {
		for (int j = 1; j <= 4; j++) {
			map_temp[i][j] = map[i][j];
		}
	}

	for (int i = 1; i <= 16; i++)
		fish_temp[i] = fish[i];

	MoveFish(shark);

	int currentdir = shark.first;
	int movei = shark.second.first;
	int movej = shark.second.second;

	//상어 최대 3번 이동 가능
	for (int i = 0; i < 3; i++) {
		movei = movei + mv[currentdir - 1].x;
		movej = movej + mv[currentdir - 1].y;

		if (!(movei > 0 && movei <= 4 && movej > 0 && movej <= 4))	continue;

		if (map[movei][movej].dir == 0 && map[movei][movej].num == 0)	continue;
		else {
			int temp = map[movei][movej].num;
			pair<int,pair<int,int>> temp_shark = make_pair(map[movei][movej].dir, make_pair(movei, movej));
			pair<int, int> temp_fish = fish[map[movei][movej].num];
			INFO temp_map = map[movei][movej];
			fish[map[movei][movej].num] = make_pair(0,0);
			map[movei][movej] = { 0,0 };


			int result = EatFish(temp_shark, answer + temp);
			if (value < result)	value = result;

			//움직인애들(상어, 물고기) 원복

			map[movei][movej] = temp_map;
			fish[map[movei][movej].num] = temp_fish;

		}
	}
	//원복
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			map[i][j] = map_temp[i][j];
		}
	}
	for (int i = 1; i <= 16; i++) {
		fish[i] = fish_temp[i];
	}
	return value;
}

int main(void) {
	int answer = 0;

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			int n, d;
			cin >> n >> d;
			map[i][j] = { n,d };
			fish[n] = make_pair(i, j);
		}
	}
	int temp = map[1][1].num;
	loc = make_pair(map[1][1].dir, make_pair(1, 1));
	fish[map[1][1].num] = { 0,0 };
	map[1][1] = { 0,0 };

	answer = EatFish(loc,temp);
	cout << answer << endl;
}