import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static boolean Debug = true;
private static int MapSize;
private static int[][] OriginMap;
private static int[][] CopyMap;
private static Queue<Integer>[] bQueue;
static int MaxNum = 0;
final static int north = 0, east = 1, south = 2, west = 3;
public static void main(String[] args) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
// 맵 크기, 사과 개수
MapSize = Integer.parseInt(br.readLine());
MaxNum = 0;
// 맵 생성
OriginMap = new int[MapSize][];
for (int i = 0; i < MapSize; i++) {
OriginMap[i] = new int[MapSize];
st = new StringTokenizer(br.readLine());
int item;
for (int j = 0; j < MapSize; j++) {
item = Integer.parseInt(st.nextToken());
OriginMap[i][j] = item;
// 합칠 수 없는 경우, 처음 주어진 수가 가장 크다.
if (MaxNum < item) {
MaxNum = item;
}
}
}
// 큐 초기화 (블록을 옮기는 데 사용된다.
bQueue = new LinkedList[MapSize];
for (int i = 0; i < MapSize; i++) {
bQueue[i] = new LinkedList<>();
}
// 00000 ~ 33333
int[] bitmasking = new int[5];
execute(bitmasking, 0);
// 시간 출력
System.out.println(MaxNum);
}
private static void execute(int[] bitmask, int index) {
// 비트마스킹을 조립
if (index <= 4) {
for (int i = 0; i < 4; i++) {
bitmask[index] = i;
execute(bitmask, index + 1);
}
return;
}
// 맵초기화
initMap();
// 실행
int rIndex;
for (int i = 0; i < 5; i++) {
rIndex = bitmask[i];
tiltMap(rIndex);
}
}
private static void initMap() {
// Merge를 위한 지도 초기화
CopyMap = new int[MapSize][];
for (int i = 0; i < MapSize; i++) {
CopyMap[i] = new int[MapSize];
for (int j = 0; j < MapSize; j++) {
int num = OriginMap[i][j];
if (num != 0) { // 0은 빈공간
CopyMap[i][j] = num;
} else {
// non-target
}
}
}
}
private static void tiltMap(int rIndex) {
// log("tiltMap(%d)", rIndex);
// 정방향|역방향
// 행기준|열기준
boolean good = (rIndex == west || rIndex == north);
boolean isRow = (rIndex == west || rIndex == east);
// 방향에 따른 병합 및 매칭
int j_start = (good ? 0 : MapSize - 1);
int j_end = (good ? MapSize : -1);
int j_add = (good ? 1 : -1);
for (int i = 0; i < MapSize; i++) {
// 1. 큐에 대입
int j = j_start;
while (j != j_end) {
// 행기준 열기준에 따라 값을 큐에 넣는다.
int item = isRow ? CopyMap[i][j] : CopyMap[j][i];
if (item != 0) {
bQueue[i].add(item);
// 값을 옮기면, 해당 자리는 빈공간으로 체크
if (isRow) {
CopyMap[i][j] = 0;
} else {
CopyMap[j][i] = 0;
}
}
j += j_add;
}
// 2. 머지
bQueue[i] = mergeBlock(bQueue[i]);
// 3. 맵에 매칭
j = j_start;
while (j != j_end) {
if (!bQueue[i].isEmpty()) {
if (isRow) {
CopyMap[i][j] = bQueue[i].poll();
// log("큐 방출 [%d][%d] = %d", i, j, CopyMap[i][j].num);
} else {
CopyMap[j][i] = bQueue[i].poll();
// log("큐 대입 [%d][%d] = %d", j, i, CopyMap[j][i].num);
}
} else {
break;
}
j += j_add;
}
}
}
static Queue<Integer> rQue;
private static Queue<Integer> mergeBlock(Queue<Integer> que) {
// 반환을 위한 큐
rQue = new LinkedList<>();
// 합치고
int item1 = 0, item2 = 0;
while (true) {
// 합칠 대상1 픽업
if (item1 == 0) {
if (!que.isEmpty()) {
item1 = que.poll();
} else {
// 큐가 비었으므로
break;
}
}
// 합칠 대상2 픽업
if (item2 == 0) {
if (!que.isEmpty()) {
item2 = que.poll();
} else {
// 비교대상이 없으므로
rQue.add(item1);
break;
}
}
// item1과 item2를 합친다.
if (item1 == item2) {
int mergeNum = item1 * 2;
rQue.add(mergeNum);
// 최고값 측정
if (MaxNum < mergeNum) {
MaxNum = mergeNum;
}
item1 = 0;
item2 = 0;
} else { // 합칠수 없는 경우, 이전 비교대상은 rQue에 넣는다.
rQue.add(item1);
item1 = item2; // 다음비교 대상이 첫번 째가 된다.
item2 = 0;
}
}
return rQue;
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
백준 14500번: 테트로미노 (0) | 2017.10.20 |
---|---|
백준 13460번: 째로탈출2 (0) | 2017.10.20 |
백준 3190번: 뱀 (0) | 2017.10.19 |
백준 14499번: 주사위 굴리기 (0) | 2017.10.19 |
백준 14502번: 연구소 (0) | 2017.10.17 |