2048(easy)

2048(easy)

import java.util.*;

public class Main {  
	public static int ans = 2;  // 보드들의 최소값은 2이다.
	public static int N;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

    // 보드 입력단.
		N = sc.nextInt();
		int map[][] = new int[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
    // 위 아래 양옆의 모든 경우를 시작해 준다. 
		up(map, 0);
		down(map, 0);
		left(map, 0);;
		right(map, 0);
			
		System.out.println(ans);
	}
	public static void up(int map[][], int nowCnt) {  // 이전에 만들어진 map과 지금까지 진행한 숫자 nowCnt
		int nowMap[][] = new int[N][N];   // 이번 함수를 통해 만들 nowMap
		boolean once = false;   // 한 번 값이 합쳐지면 그렇게 만들어진 값은 다시 합쳐지면 안된다.
		for(int j=0; j<N; j++) {  // 이게 중요한데, 위에서부터 하는 것이므로 i와 j가 반대로 될 것이다. 아래, 오른쪽, 왼쪽은 이와같이 생각하면 된다.
			Stack<Integer> filter = new Stack<>();    // 빈 칸을 없애기 위해 사용할 filter
			for(int i=0; i<N; i++) {
				if(map[i][j]!=0)    // 빈 칸이면 걍 무시하고 지나가버리기~
				if(filter.isEmpty()) {    // filter가 비었으면 당연히 하나는 넣어줘야한다.
					filter.add(map[i][j]);
					once = false;   // 첫값이면 무조건 위의숫자랑 더해졌을리가 없다.
				}else {
					if(filter.peek()==map[i][j] && !once) { // 앞의 과정에서 들어간 값과 이제 비교할 숫자가 같은경우, 또 앞의 과정에서 들어간 값이 이미 한번 더해진 경우가 아닌 경우
						int before = filter.pop();
						filter.add(before*2);   // 숫자를 2배 해준다.
						once = true;    // 이렇게 stack의 맨 위에 들어간 숫자는 또 더해져서는 안된다.
						continue;
					}else {   // 둘의 숫자가 다르거나, 이미 한번 더해준 숫자인 경우는 그냥 다음 숫자를 넣어주면 된다.
						filter.add(map[i][j]);
						once = false; // 이 값은 더해진 것이 아니므로 다시 false
					}
				}
			}
			while(!filter.isEmpty()) {    // 그렇게 해당하는 줄의 숫자들을 완성했으면 빈칸 없이 넣어준다.
				int num = filter.pop();   // 하나 꺼냄
				ans = Math.max(ans, num);   // 그리고 만들어진 숫자들 중 최대값을 저장한다
				nowMap[filter.size()][j] = num;   // 보면 제일먼저 만든숫자가 맨 나중에 나오고, 가장 최근에 만들어진 숫자가 처음 나온다. 그리고 가장 먼저 만든 숫자는 맨 위로 가야하고 그러면 거꾸로 하면 된다.
			}
		}
    // 5번 하는 경우들을 전체 검색
		nowCnt++;
		if(checkCnt(nowCnt)) {
			return;
		}
		up(nowMap, nowCnt);
		down(nowMap, nowCnt);
		left(nowMap, nowCnt);
		right(nowMap, nowCnt);
	}
  // 아래도 이와 비슷한 로직이다.
	public static void down(int map[][], int nowCnt) {
		int nowMap[][] = new int[N][N];
		boolean once = false;
		for(int j=0; j<N; j++) {
			Stack<Integer> filter = new Stack<>();
			for(int i=N-1; i>=0; i--) {
				if(map[i][j]!=0) {
					if(filter.isEmpty()) {
						filter.add(map[i][j]);
						once = false;
					}else {
						if(filter.peek()==map[i][j] && !once) {
							int before = filter.pop();
							filter.add(before*2);
							once = true;
							continue;
						}else {
							filter.add(map[i][j]);
							once = false;
						}
					}
				}
			}
			while(!filter.isEmpty()) {
				int num = filter.pop();
				ans = Math.max(ans, num);
				nowMap[filter.size()][j] = num;
			}
		}
		nowCnt++;
		if(checkCnt(nowCnt)) {
			return;
		}
		up(nowMap, nowCnt);
		down(nowMap, nowCnt);
		left(nowMap, nowCnt);
		right(nowMap, nowCnt);
	}
	public static void left(int map[][], int nowCnt) {
		int nowMap[][] = new int[N][N];
		boolean once = false;
		for(int i=0; i<N; i++) {
			Stack<Integer> filter = new Stack<>();
			for(int j=0; j<N; j++) {
				if(map[i][j]!=0) {
					if(filter.isEmpty()) {
						filter.add(map[i][j]);
						once = false;
					}else {
						if(filter.peek()==map[i][j] && !once) {
							int before = filter.pop();
							filter.add(before*2);
							once = true;
							continue;
						}else {
							filter.add(map[i][j]);
							once = false;
						}
					}
				}
			}
			while(!filter.isEmpty()) {
				int num = filter.pop();
				ans = Math.max(ans, num);
				nowMap[i][filter.size()] = num;
			}
		}
		nowCnt++;
		if(checkCnt(nowCnt)) {
			return;
		}
		up(nowMap, nowCnt);
		down(nowMap, nowCnt);
		left(nowMap, nowCnt);
		right(nowMap, nowCnt);
	}
	public static void right(int map[][], int nowCnt) {
		int nowMap[][] = new int[N][N];
		boolean once = false;
		for(int i=0; i<N; i++) {
			Stack<Integer> filter = new Stack<>();
			for(int j=N-1; j>=0; j--) {
				if(map[i][j]!=0) {
					if(filter.isEmpty()) {
						filter.add(map[i][j]);
						once = false;
					}else {
						if(filter.peek()==map[i][j] && !once) {
							int before = filter.pop();
							filter.add(before*2);
							once = true;
							continue;
						}else {
							filter.add(map[i][j]);
							once = false;
						}
					}
				}
			}
			while(!filter.isEmpty()) {
				int num = filter.pop();
				ans = Math.max(ans, num);
				nowMap[i][filter.size()] = num;
			}
		}
		nowCnt++;
		if(checkCnt(nowCnt)) {
			return;
		}
		up(nowMap, nowCnt);
		down(nowMap, nowCnt);
		left(nowMap, nowCnt);
		right(nowMap, nowCnt);
	}
	public static boolean checkCnt(int cnt) {
		if(cnt==5) return true;
		return false;
	}
}