청소년 상어 C++

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

19236번: 청소년 상어

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

using namespace std;
const int MAX = 4;

int map[MAX][MAX];

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 x, y, dir; };

vector<INFO> shark(17);

int answer = 0;

INFO s_info; //상어 정보

void MoveFish() {

	for (int i = 1; i <= 16; i++) {
		if (shark[i].x == -1 && shark[i].y == -1 && shark[i].dir == -1)	continue;
		int d = shark[i].dir;

		for (int k = 0; k < 8; k++) {
			int movei = shark[i].x + mv[d].x;
			int movej = shark[i].y + mv[d].y;

			if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4) {
				if (make_pair(s_info.x, s_info.y) != make_pair(movei, movej)) {
					if (map[movei][movej] == -1) { //빈칸
						map[movei][movej] = i;
						map[shark[i].x][shark[i].y] = -1;
						shark[i] = { movei,movej,d };
					}
					else {//서로 바꿈
						int tmp_num = map[movei][movej];
						INFO tmp_sk = shark[tmp_num];

						map[movei][movej] = i;
						shark[tmp_num] = { shark[i].x, shark[i].y, tmp_sk.dir };
						map[shark[i].x][shark[i].y] = tmp_num;
						shark[i] = { movei,movej,d };
					}
					break;
				}
			}
			d += 1;
			if (d == 8)	d = 0;
		}
	}
}

void MoveShark(int count) {
	bool flag = false;
	INFO tmp_s_info = s_info;
	vector<INFO> shark_tmp = shark;
	int map_tmp2[MAX][MAX];
	for (int ii = 0; ii < 4; ii++) {
		for (int jj = 0; jj < 4; jj++) {
			map_tmp2[ii][jj] = map[ii][jj];
		}
	}

	MoveFish();

	int movei = tmp_s_info.x;
	int movej = tmp_s_info.y;
	int d = tmp_s_info.dir;

	for (int k = 0; k < 4; k++) {
		movei += mv[d].x;
		movej += mv[d].y;
		int tp;

		if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4) {
			if (map[movei][movej] != -1) {
				INFO tmp_s_info2 = s_info;
				vector<INFO> shark_tmp2 = shark;
				int map_tmp[MAX][MAX];
				for (int ii = 0; ii < 4; ii++) {
					for (int jj = 0; jj < 4; jj++) {
						map_tmp[ii][jj] = map[ii][jj];
					}
				}

				tp = map[movei][movej];
				s_info = { movei,movej,shark[tp].dir };
				shark[tp] = { -1,-1,-1 };
				map[movei][movej] = -1;

				MoveShark(count+tp);

				s_info = tmp_s_info2;
				shark = shark_tmp2;
				for (int ii = 0; ii < 4; ii++) {
					for (int jj = 0; jj < 4; jj++) {
						map[ii][jj] = map_tmp[ii][jj];
					}
				}
				flag = true;
			}
		}
	}

	if (flag == false) {
		answer = max(answer, count);
	}

	s_info = tmp_s_info;
	shark = shark_tmp;
	for (int ii = 0; ii < 4; ii++) {
		for (int jj = 0; jj < 4; jj++) {
			map[ii][jj] = map_tmp2[ii][jj];
		}
	}
}

int main(void) {
	memset(map, -1, sizeof(map));

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int num, dir;
			cin >> num >> dir;
			map[i][j] = num;
			shark[num] = { i,j,dir - 1 };
		}
	}

	s_info = { 0,0,shark[map[0][0]].dir };
	answer = map[0][0];
	shark[answer] = { -1,-1,-1 };
	map[0][0] = -1;

	MoveShark(answer);

	cout << answer << endl;
}