[BOJ] 12100. 2048(Easy)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int N=sc.nextInt();
	static int arr[][]=new int[N][N];
	static int dh[]= {-1,0,1,0}; //UP,LEFT,DOWN,RIGHT 순
	static int dw[]= {0,-1,0,1};
	static int max=Integer.MIN_VALUE;
	public static void main(String[] args) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		
		go(arr,0);
		
		int a=0;
		System.out.println(max);
	}
	
	public static void go(int arr[][],int d) {
		int map[][]=new int[N][N];
		if(d==5) {
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr.length; j++) {
					if(arr[i][j]>max) {
						max=arr[i][j];
					}
				}
			}
			return;
		}
		
		copy(map,arr);
		
		up(arr);
		go(arr,d+1);
		copy(arr,map);
		down(arr);
		go(arr,d+1);
		copy(arr,map);
		left(arr);
		go(arr,d+1);
		copy(arr,map);
		right(arr);
		go(arr,d+1);
		copy(arr,map);
	}
	
	public static void up(int arr[][]) {
		for (int w = 0; w < arr.length; w++) {
			boolean merged[]=new boolean[N];
			List<Integer> list=new ArrayList<Integer>();
			for (int h = 0; h < arr.length; h++) {
				if(arr[h][w]!=0) {
					int size=list.size();
					if(size>=1 && !merged[size-1] && list.get(size-1)==arr[h][w]) {
						list.remove(list.size()-1);
						list.add(2*arr[h][w]);
						merged[size-1]=true;
					}else {
						list.add(arr[h][w]);
					}
				}
			}
		
			int size=list.size();
			for (int i = 0; i < size; i++) {
				arr[i][w]=list.get(i);
			}
			for (int i = size; i < N; i++) {
				arr[i][w]=0;
			}
		}
	}
	
	public static void down(int arr[][]) {
		for (int w = 0; w < arr.length; w++) {
			boolean merged[]=new boolean[N];
			List<Integer> list=new ArrayList<Integer>();
			for (int h = arr.length-1; h >= 0 ; h--) {
				if(arr[h][w]!=0) {
					int size=list.size();
					if(size>=1 && !merged[size-1] && list.get(size-1)==arr[h][w]) {
						list.remove(list.size()-1);
						list.add(2*arr[h][w]);
						merged[size-1]=true;
					}else {
						list.add(arr[h][w]);
					}
				}
			}
			int size=list.size();
			for (int i = 0; i < size; i++) {
				arr[N-1-i][w]=list.get(i);
			}
			for (int i = size; i < N; i++) {
				arr[N-1-i][w]=0;
			}
		}
	}
	
	public static void left(int arr[][]) {
		for (int h = 0; h < arr.length; h++) {
			boolean merged[]=new boolean[N];
			List<Integer> list=new ArrayList<Integer>();
			for (int w = 0; w < arr.length; w++) {
				if(arr[h][w]!=0) {
					int size=list.size();
					if(size>=1 && !merged[size-1]&& list.get(size-1)==arr[h][w]) {
						list.remove(list.size()-1);
						list.add(2*arr[h][w]);
						merged[size-1]=true;
					}else {
						list.add(arr[h][w]);
					}
				}
			}
			int size=list.size();
	 		for (int i = 0; i < size; i++) {
				arr[h][i]=list.get(i);
			}
	 		for (int i = size; i < N; i++) {
				arr[h][i]=0;
			}
		}
	}
	
	public static void right(int arr[][]) {
		for (int h = 0; h < arr.length; h++) {
			boolean merged[]=new boolean[N];
			List<Integer> list=new ArrayList<Integer>();
			for (int w = arr.length-1; w >= 0; w--) {
				if(arr[h][w]!=0) {
					int size=list.size();
					if(size>=1 && !merged[size-1] && list.get(size-1)==arr[h][w]) {
						list.remove(list.size()-1);
						list.add(2*arr[h][w]);
						merged[size-1]=true;
					}else {
						list.add(arr[h][w]);
					}
				}
			}
			int size=list.size();
			for (int i = 0; i < size; i++) {
				arr[h][N-1-i]=list.get(i);
			}
			for (int i = size; i < N; i++) {
				arr[h][N-1-i]=0;
			}
		}
	}
	
	public static void copy(int map[][],int arr[][]) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				map[i][j]=arr[i][j];
			}
		}
	}
}