質問する

2048ゲームは4×4サイズの碁盤で独自に楽しむ面白いゲーム.これを押すとリンクでゲームができます.
このゲームでは、1回の移動は、ボード上のブロック全体を上下左右4方向の1つに移動します.同じ値を持つ2つのブロックが衝突すると、2つのブロックが1つに結合されます.1回の移動では、マージされたブロックは別のブロックと再マージできません.(実際のゲームでは、移動するたびにブロックが追加されますが、この問題ではブロックは追加されません)

入力

第1行は、プレートのサイズN(1≦N≦20)を与える.2行目からN行目まではゲームボードの初期状態が与えられる.0はスペース、その他の値はブロックです.ブロックに書かれた数は、2以上であり、1024以下の2の平方である.少なくとも1つのブロックをください.

しゅつりょく

最大5回移動し、得られる最大ブロックを出力します.

I/O例

に答える

すべての状況が試します.
各線を移動するとき
キューに1.0以外の要素を指定
2.次の要素が1の要素と同じ場合は、次の要素の値を指定し、その値を配列に挿入します.

コード#コード#

import java.io.*;
import java.util.*;
public class Main_B12100 {
	static int n,answer=0;
	//5번 이동을 위한 dfs
	static void dfs(int depth,int[][]arr) {
		if(depth==5) {
			answer=Math.max(answer, getMax(arr));
			return;
		}
		for(int i=0;i<4;i++) {			
			dfs(depth+1,move(i,arr));
		}
	}
	//각 배열의 최댓값 찾는 메서드
	static int getMax(int[][]arr) {
		int temp=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(arr[i][j]>temp)temp=arr[i][j];
			}
		}
		return temp;
	}
	//한 라인씩 이동
	static void lineMove(int[][]arr,Queue<Integer> q,int i,int d){
		int[]temp=new int[n];
		int num=0,index=0;
		while(!q.isEmpty()) {
			if(num==0)num=q.poll();
			if(!q.isEmpty()&&num==q.peek()) {
				q.poll();
				temp[index++]=num*2;
			}
			else temp[index++]=num;
			num=0;
		}
        //상
		if(d==0)for(int k=0;k<n;k++)arr[k][i]=temp[k];
		//하
        else if(d==1)for(int k=0;k<n;k++)arr[n-k-1][i]=temp[k];
        //좌
		else if(d==2)for(int k=0;k<n;k++)arr[i][k]=temp[k];
		//우
        else for(int k=0;k<n;k++)arr[i][n-k-1]=temp[k];
	}
	//각 방향으로 배열 이동
	static int[][] move(int d,int[][]arr) {
		Queue<Integer> q = new LinkedList<>();
		int[][]map=new int[n][n];
		if(d==0) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[j][i]!=0)q.offer(arr[j][i]);
				}
				lineMove(map,q,i,d);
			}
		}
		else if(d==1) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[n-j-1][i]!=0)q.offer(arr[n-j-1][i]);
				}
				lineMove(map,q,i,d);
			}
		}
		else if(d==2) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[i][j]!=0)q.offer(arr[i][j]);
				}
				lineMove(map,q,i,d);
			}
		}
		else {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[i][n-j-1]!=0)q.offer(arr[i][n-j-1]);
				}
				lineMove(map,q,i,d);
			}
		}
		return map;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n=Integer.parseInt(br.readLine());
		
		int[][]arr=new int[n][n];
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		dfs(0, arr);
		System.out.println(answer);
	}

}