백준 19236 청소년상어(dfs)

www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int map[4][4][2];
int fish[17][3];
int dx[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[9] = { 0,0,-1,-1,-1,0,1,1,1 };
int sum;

int move(int sx,int sy,int sdir) {
	int res = 0;
	int tempMap[4][4][2];
	int tempFish[17][3];
	for (int z = 0; z <4; z++) {
		for (int j = 0; j <4; j++) {
			tempMap[z][j][0] = map[z][j][0];
			tempMap[z][j][1] = map[z][j][1];
		}
	}
	for (int j = 1; j < 17; j++) {
		tempFish[j][0] = fish[j][0];
		tempFish[j][1] = fish[j][1];
		tempFish[j][2] = fish[j][2];
	}

	//물고기
	for (int a = 1; a < 17; a++) {
		if (fish[a][2] != -1) {
			int fx = fish[a][0];
			int fy = fish[a][1];
			int fdir = map[fx][fy][1];
			for (int i = 0; i <= 8; i++) {
				int nfdir = (fdir - 1 + i) % 8 + 1;
				int fnx = fx + dx[nfdir];
				int fny = fy + dy[nfdir];

				if ((fnx >= 0 && fny >= 0 && fnx < 4 && fny < 4) && !(fnx == sx && fny == sy)) {
					int tempNum, tempDir;
					
					tempNum = map[fx][fy][0];
					//tempDir = map[fx][fy][1];
					map[fx][fy][0] = map[fnx][fny][0];
					map[fx][fy][1] = map[fnx][fny][1];
					map[fnx][fny][0] = tempNum;
					map[fnx][fny][1] = nfdir;

					fish[map[fx][fy][0]][0] = fx;
					fish[map[fx][fy][0]][1] = fy;
					fish[map[fnx][fny][0]][0] = fnx;
					fish[map[fnx][fny][0]][1] = fny;

					break;
				}
			}

		}
	}


	//상어 
	for (int i = 1; i <= 3; i++) {
		int nx = sx + (dx[sdir]*i);
		int ny = sy + (dy[sdir]*i);
		int ndir = map[nx][ny][1];

		if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
			for (int z = 0; z < 4; z++) {
				for (int j = 0; j < 4; j++) {
					map[z][j][0] = tempMap[z][j][0];
					map[z][j][1] = tempMap[z][j][1];
				}
			}
			for (int j = 1; j < 17; j++) {
				fish[j][0] = tempFish[j][0];
				fish[j][1] = tempFish[j][1];
				fish[j][2] = tempFish[j][2];
			}
			return res;
		}
		if (fish[map[nx][ny][0]][2] == -1) continue;

		int fishNum = map[nx][ny][0];
		//map[nx][ny][0] = 0;
		fish[fishNum][2] = -1;
		res = max(move(nx, ny, ndir) + fishNum, res);
		//map[nx][ny][0] = fishNum;
		fish[map[nx][ny][0]][2] = 0;

	}
		for (int z = 0; z < 4; z++) {
			for (int j = 0; j < 4; j++) {
				map[z][j][0] = tempMap[z][j][0];
				map[z][j][1] = tempMap[z][j][1];
			}
		}
		for (int j = 1; j < 17; j++) {
			fish[j][0] = tempFish[j][0];
			fish[j][1] = tempFish[j][1];
			fish[j][2] = tempFish[j][2];
		}
	return res;
}

int main() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			scanf("%d", &map[i][j][0]);
			scanf("%d", &map[i][j][1]);
			fish[map[i][j][0]][0] = i;
			fish[map[i][j][0]][1] = j;
		}
	}

	sum = map[0][0][0];
	fish[map[0][0][0]][2] = -1;
	//map[0][0][1] = 0;

	printf("%d", sum + move(0, 0, map[0][0][1]));
	return 0;
}