청소년 상어

www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

#include <iostream>

using namespace std;

int dy[] = { -1,-1,0,1,1,1,0,-1 };
int dx[] = { 0,-1,-1,-1,0,1,1,1 };

struct FISH {
	int y, x, dir;
};

int answer = 0;
int board[4][4];
FISH fish[16];

void solve(int board[][4], FISH fish[], int shark_y, int shark_x, int sum) {
	int candi_board[4][4];
	FISH candi_fish[16];
	for (int y = 0; y < 4; y++) {
		for (int x = 0; x < 4; x++) {
			candi_board[y][x] = board[y][x];
		}
	}
	for (int i = 0; i < 16; i++) {
		candi_fish[i] = fish[i];
	}
	// 상어 먹기
	int fish_number = candi_board[shark_y][shark_x];
	int shark_dir = fish[fish_number].dir;
	candi_fish[fish_number].y = -1;
	candi_fish[fish_number].x = -1;
	candi_fish[fish_number].dir = -1;
	candi_board[shark_y][shark_x] = -1;
	sum += fish_number + 1;
	if (answer < sum) answer = sum;
	// 물고기 이동
	for (int f = 0; f < 16; f++) {
		if (candi_fish[f].x == -1) continue; //죽은 물고기
		int cy = candi_fish[f].y;
		int cx = candi_fish[f].x;
		int cd = candi_fish[f].dir;
		int ny = cy + dy[cd];
		int nx = cx + dx[cd];
		int nd = cd;
		while (ny < 0 || ny >= 4 || nx < 0 || nx >= 4 || (ny == shark_y && nx == shark_x)) {
			nd = (nd + 1) % 8;
			ny = cy + dy[nd];
			nx = cx + dx[nd];
		}
		if (candi_board[ny][nx] != -1) {
			int target = candi_board[ny][nx];
			candi_fish[f].y = ny;
			candi_fish[f].x = nx;
			candi_fish[f].dir = nd;
			candi_fish[target].y = cy;
			candi_fish[target].x = cx;
			candi_board[ny][nx] = f;
			candi_board[cy][cx] = target;
		}
		else {
			candi_fish[f].y = ny;
			candi_fish[f].x = nx;
			candi_fish[f].dir = nd;
			candi_board[ny][nx] = f;
			candi_board[cy][cx] = -1;
		}
	}
	// 상어 이동
	for (int step = 1; step < 4; step++) {
		int ny = shark_y + dy[shark_dir] * step;
		int nx = shark_x + dx[shark_dir] * step;
		if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) break;
		if (candi_board[ny][nx] != -1)  solve(candi_board, candi_fish, ny, nx, sum);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	for (int y = 0; y < 4; y++) {
		for (int x = 0; x < 4; x++) {
			int a, b; //번호, 방향
			cin >> a >> b;
			a--; b--;
			board[y][x] = a;
			fish[a].y = y;
			fish[a].x = x;
			fish[a].dir = b;
		}
	}
	solve(board, fish, 0, 0, 0);
	cout << answer << "\n";
	return 0;
}