청소년 상어 C++

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

19236번: 청소년 상어

 

#include <iostream>

using namespace std;
const int MAX = 4;
int fishmap[MAX][MAX];
int dir[MAX][MAX];
struct info { int dir, x, y; };
info shark;
info fish[17];
struct MOVE { int x, y; };
MOVE mv[9] = { { 0,0 },{ -1,0 },{ -1,-1 },{ 0,-1 },{ 1,-1 },{ 1,0 },{ 1,1 },{ 0,1 },{ -1,1 } };
int temp_fishmap[MAX][MAX];
int temp_dir[MAX][MAX];
info temp_fish[17];

void copymap(int temp_fishmap[MAX][MAX], int temp_dir[MAX][MAX], info temp_fish[17]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			temp_fishmap[i][j] = fishmap[i][j];
			temp_dir[i][j] = dir[i][j];
		}
	}

	for (int i = 1; i <= 16; i++) {
		temp_fish[i] = fish[i];
	}
}
void remakemap(int temp_fishmap[MAX][MAX], int temp_dir[MAX][MAX], info temp_fish[17]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			fishmap[i][j] = temp_fishmap[i][j];
			dir[i][j] = temp_dir[i][j];
		}
	}

	for (int i = 1; i <= 16; i++) {
		fish[i] = temp_fish[i];
	}
}
void MoveFish(info s) {

	for (int i = 1; i <= 16; i++) {
		if (fish[i].dir != -1) {
			int rotate = fish[i].dir;
			for (int j = 1; j <= 8; j++) {
				int movei = fish[i].x + mv[rotate].x;
				int movej = fish[i].y + mv[rotate].y;
				if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4) {
					//빈칸
					if (fishmap[movei][movej] == 0 && !(movei == s.x && movej == s.y)) {
						fishmap[fish[i].x][fish[i].y] = 0;
						dir[fish[i].x][fish[i].y] = 0;
						fish[i] = { rotate,movei,movej };
						fishmap[movei][movej] = i;
						dir[movei][movej] = rotate;
						break;
					}
					//다른 물고기
					else if (fishmap[movei][movej] != 0 && !(movei == s.x && movej == s.y)) {
						//서로 자리 바꾸기
						int temp_num = fishmap[movei][movej];
						int temp_dir = dir[movei][movej];
						fish[temp_num] = { temp_dir,fish[i].x,fish[i].y };
						fishmap[movei][movej] = i;
						dir[movei][movej] = rotate;
						fishmap[fish[i].x][fish[i].y] = temp_num;
						dir[fish[i].x][fish[i].y] = temp_dir;
						fish[i] = { rotate,movei,movej };
						break;
					}
				}
				rotate += 1;
				if (rotate == 9)
					rotate = 1;
			}
		}
	}
}
int MoveShark(info s, int value) {
	int temp_fishmap[MAX][MAX];
	int temp_dir[MAX][MAX];
	info temp_fish[17];

	bool process = false;
	copymap(temp_fishmap, temp_dir,temp_fish);
	MoveFish(s);

	int ans = value;
	int rotate = s.dir;
	int flag = false;
	info temp_s = s;
	int movei = s.x + mv[rotate].x;
	int movej = s.y + mv[rotate].y;
	for (int j = 1; j <= 3; j++) {
		if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4) {
			info temp_f = fish[fishmap[movei][movej]];
			int temp_value = fishmap[movei][movej];
			//다른 물고기
			if (fishmap[movei][movej] != 0) {
				//물고기 먹음
				s = { dir[movei][movej],movei,movej };
				fish[fishmap[movei][movej]].dir = -1;
				fishmap[movei][movej] = 0;
				int temp = MoveShark(s, value + temp_value);
				if (temp > ans)
					ans = temp;
				flag = true;

				//원복
				fishmap[movei][movej] = temp_value;
				fish[temp_value] = temp_f;
				s = temp_s;
				process = true;
			}
		}
		movei += mv[rotate].x;
		movej += mv[rotate].y;
	}
	shark = temp_s;
	remakemap(temp_fishmap, temp_dir, temp_fish);
	return ans;
}
int main(void) {
	int max_value = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> fishmap[i][j] >> dir[i][j];
			fish[fishmap[i][j]] = { dir[i][j],i,j };
		}
	}
	max_value += fishmap[0][0];
	shark = { dir[0][0],0,0 };
	fish[fishmap[0][0]].dir = -1;
	fishmap[0][0] = 0;
	//dfs()
	max_value = MoveShark(shark, max_value);
	cout << max_value;
	return 0;
}