[백준] 12100번 2048 (Easy (gold 2

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static int[][] map; //원래 지도.
    static int[][] temp; //임시지도
    static int[] num=new int[5]; //백트래킹. 5가지 방향 선택한 것.
    static int n;
    static int answer=Integer.MIN_VALUE;
    static Queue<Point> que=new LinkedList<>(); // 이동할 때 빈칸들 넣기.
    static int x; //임시맵의 col
    static int y; //임시맵의 row
    static int value; //임시맵의 블록 크기
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n=Integer.valueOf(br.readLine());
        map=new int[n+1][n+1];
        temp=new int[n+1][n+1];

        //맵 초기화 (블럭의 초기 상태.
        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j]=Integer.valueOf(st.nextToken());
            }
        }

        back(0,0);
        System.out.println(answer);

    }
    //5가지 방향 선택해주기.
    public static void back(int max, int index){
        if(max==5){
            //5가지 방향을 선택함.
            move();
            return;
        }
        for(int i=1; i<=4; i++){
            num[index]=i;
            back(max+1, index+1);
        }
    }
    //이동하는 시뮬레이션 구현.
    public static void move(){
        //임시맵에 원래 맵 저장.
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                temp[i][j]=map[i][j];
            }
        }
        //저장되어 있는 백트래킹 결과. 즉 방향 5가지에 맞게 이동.
        //1은 위, 2는 아래, 3은 왼쪽, 4는 오른쪽을 이동
        for(int e : num){
            que.clear();
            if(e==1){
                up();
            }
            else if(e==2){
                down();
            }
            else if(e==3){
                left();
            }
            else if(e==4){
                right();
            }
        }

        //가장 큰 블록 찾기.
        bigBlock();
    }

    //방향별로 구현.//

    //블럭 합치고 위에서 부터 채우기.
    public static void up(){
        for(int col=1; col<=n; col++){
            que.clear();
            y=0;
            x=0;
            value=0;
            for(int row=1; row<=n; row++){
                combine(row,col);
            }
            for(int row=1; row<=n; row++){
                collect(row, col);
            }
        }
    }
    //블럭합치고 아래서 부터 채우기
    public static void down(){
        for(int col=1; col<=n; col++){
            que.clear();
            y=0;
            x=0;
            value=0;
            for(int row=n; row>=1; row--){
                combine(row,col);
            }
            for(int row=n; row>=1; row--){
                collect(row, col);
            }
        }
    }
    //블럭합치고 왼쪽에서 부터 채우기
    public static void left(){
        for(int row=1; row<=n; row++){
            que.clear();
            y=0;
            x=0;
            value=0;
            for(int col=1; col<=n; col++){
                combine(row,col);
            }
            for(int col=1; col<=n; col++){
                collect(row, col);
            }
        }
    }
    //블럭합치고 오른쪽부터 채우기.
    public static void right(){
        for(int row=1; row<=n; row++){
            que.clear();
            y=0;
            x=0;
            value=0;
            for(int col=n; col>=1; col--){
                combine(row,col);
            }
            for(int col=n; col>=1; col--){
                collect(row,col);
            }
        }
    }

    //같은 블록 만나면 블록들 합치기.
    public static void combine(int row, int col){
        if(value==0 && temp[row][col]!=0){
            y=row;
            x=col;
            value=temp[row][col];
        }
        else if(value!=0 && temp[row][col]!=0){
            //같은 수 발견
            //같은 값 만나면 합쳐지면서 비어서 초기화,
            if(temp[row][col]==value){
                temp[y][x]=value+value; //한쪽으로 합쳐짐
                temp[row][col]=0; //다른쪽은 비게됨
                y=0;
                x=0;
                value=0;
            }
            //새로 만난 블럭을 기준으로 아래를 봐야해서 초기화.
            else{
                y=row;
                x=col;
                value=temp[row][col];
            }
        }
    }

    //한쪽으로 블록들을 몰아넣기.
    public static void collect(int row, int col){
        //해당값이 0이면 큐에 추가. 추후에 이 칸으로 저장.
        if(temp[row][col]==0){
            que.add(new Point(col,row));
        }
        //만약 빈칸이 있을때, 0이 아닌 수를 만나면 빈칸에 넣고,
        //비운자리는 0으롳 초기화, que에 추가하여 추후에 이자리로 추가 가능.
        else{
            if(que.size()>0){
                temp[que.peek().y][que.peek().x]=temp[row][col];
                temp[row][col]=0;
                que.poll();
                que.offer(new Point(col,row));
            }
        }
    }

    //최고 블럭의 크기를 전역변수와 비교하여 저장.
    public static void bigBlock(){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                answer= answer <temp[i][j] ? temp[i][j] : answer;
            }
        }
    }
}

//최적화에 아직 실패.. 계속 해봐야한다.
//조건을 잘못 적용해서 틀리던 문제..