https://www.acmicpc.net/problem/19236
import java.util.Scanner;
public class Main {
public static class Fish {
int x, y, d;
boolean live;
public Fish(int x, int y, int d, boolean live) {
this.x = x;
this.y = y;
this.d = d;
this.live = live;
}
}
public static Fish[] fish = new Fish[17];
public static int[][] fishMap = new int[4][4];
public static int result = 0;
public static int[] dx = {0,-1,-1,0,1,1,1,0,-1};
public static int[] dy = {0,0,-1,-1,-1,0,1,1,1};
//상어 위치 (x, y)
public static void moveFish(int x, int y) {
for (int i = 1; i <= 16; i++) {
Fish moveFish = fish[i];
//죽어있으면 이동X
if (!moveFish.live) continue;
//8방향 이동여부 확인
for (int j = 0; j < 8; j++) {
int D = (moveFish.d + j) >= 9 ? (moveFish.d + j) % 8 : (moveFish.d + j);
int X = moveFish.x + dx[D];
int Y = moveFish.y + dy[D];
//상어가 있거나 경계를 넘으면 continue
if (X < 0 || Y < 0 || X >= 4 || Y >= 4 || (X == x && Y == y)) continue;
//물고기 있으면
if (fishMap[X][Y] != -1) {
Fish otherFish = fish[fishMap[X][Y]];
fishMap[moveFish.x][moveFish.y] = fishMap[X][Y];
fishMap[X][Y] = i;
otherFish.x = moveFish.x;
otherFish.y = moveFish.y;
moveFish.x = X;
moveFish.y = Y;
moveFish.d = D;
//물고기 없으면
} else {
fishMap[moveFish.x][moveFish.y] = -1;
fishMap[X][Y] = i;
moveFish.x = X;
moveFish.y = Y;
moveFish.d = D;
}
break;
}
}
}
public static void solve(int x, int y, int d, int sum) {
//결과값 갱신
if (result < sum) result = sum;
//fish, fishMap 상태 저장해둠
Fish[] fishTmp = new Fish[17];
for (int i = 1; i < 17; i++)
fishTmp[i] = new Fish(fish[i].x, fish[i].y, fish[i].d, fish[i].live);
int[][] fishMapTmp = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
fishMapTmp[i][j] = fishMap[i][j];
}
}
//1. 물고기 이동
moveFish(x, y);
//2. 상어 이동
for (int i = 1; i < 4; i++) {
int X = x + dx[d]*i;
int Y = y + dy[d]*i;
if (X < 0 || Y < 0 || X >= 4 || Y >= 4) break;
//살아있는 물고기가 있는 경우
int fishNum = fishMap[X][Y];
if (fishNum != -1) {
fish[fishNum].live = false;
fishMap[X][Y] = -1;
solve(X, Y, fish[fishNum].d, sum + fishNum);
fish[fishNum].live = true;
fishMap[X][Y] = fishNum;
}
}
//fish, fishMap 상태 복구
for (int i = 1; i < 17; i++) {
fish[i].x = fishTmp[i].x;
fish[i].y = fishTmp[i].y;
fish[i].d = fishTmp[i].d;
fish[i].live = fishTmp[i].live;
}
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
fishMap[i][j] = fishMapTmp[i][j];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int fishNum = sc.nextInt();
int fishDir = sc.nextInt();
fishMap[i][j] = fishNum;
fish[fishNum] = new Fish(i, j, fishDir, true);
}
}
//상어가 첫번째 위치의 물고기 먹음.
int fishNum = fishMap[0][0];
fish[fishNum].live = false;
fishMap[0][0] = -1;
solve(0, 0, fish[fishNum].d, fishNum);
System.out.println(result);
}
}