2048 (Easy)

これは2048ゲームの実施問題です.この問題をするとき、しっかり覚えなければならない条件があります.1回の移動では、マージされたブロックは別のブロックと再マージできません.こんな部分です
(個人的にこの条件を逃したので、間違えました…)
マザーボードの最大サイズは20 x 20で、最大5回移動したときの最大値です.方向は上下左右4方向あり、5回移動可能であるため、状態の最大数は4^5、すなわち1024である.
また、各プレートからブロックを取り出すコストは20であり、各ブロックがプレートの大きさ(400)から一方向に移動するコストであるため、各ブロックを端部から取り出すコストは400*20=8000であると考えられる.
また,状態の最大数は1024であるため,10000,000個のループを迂回するのに十分な大きさと考えられる.もちろん、実装中に現在の回路基板の状態をコピーする必要があるかもしれないが、限られた時間でBroutforceにコピーできると予測できる.

答えを出す。

問題を実施するには問題の条件を満たすだけでよい.
宣言はBoardのクラスを表し、定義方法は4方向に移動させ、最大5回移動させることができ、Boardはその状態をコピーして他の方向に移動することができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int[] UP = {-1, 0};
    private static final int[] RIGHT = {0, 1};
    private static final int[] DOWN = {1, 0};
    private static final int[] LEFT = {0, -1};

    private static int N;
    private static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws Throwable {
        Board board = input();

        move(board, 5);

        System.out.println(ans);
    }

    private static Board input() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        N = Integer.parseInt(br.readLine());

        final int[][] board = new int[N][N];

        for (int ni = 0; ni < N; ni++) {
            final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int nj = 0; nj < N; nj++) {
                board[ni][nj] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();

        return new Board(board);
    }

    private static void move(Board board, int remain) {
        if (remain == 0) {
            return;
        }

        final int nextRemain = remain - 1;

        move(board.up(), nextRemain);
        move(board.right(), nextRemain);
        move(board.down(), nextRemain);
        move(board.left(), nextRemain);
    }

    static class Board {
        private final int[][] board;

        public Board(int[][] board) {
            this.board = board;
        }

        public Board up() {
            return copy().moveUp();
        }

        private Board moveUp() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveBlock(UP, y, x);
                }
            }

            return this;
        }

        public Board down() {
            return copy().moveDown();
        }

        private Board moveDown() {
            for (int y = N-1; y >= 0; y--) {
                for (int x = 0; x < N; x++) {
                    moveBlock(DOWN, y, x);
                }
            }

            return this;
        }

        public Board left() {
            return copy().moveLeft();
        }

        private Board moveLeft() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveBlock(LEFT, y, x);
                }
            }

            return this;
        }

        public Board right() {
            return copy().moveRight();
        }

        private Board moveRight() {
            for (int y = 0; y < N; y++) {
                for (int x = N-1; x >= 0; x--) {
                    moveBlock(RIGHT, y, x);
                }
            }

            return this;
        }

        private Board copy() {
            final int[][] newBoard = new int[N][N];

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    newBoard[y][x] = Math.abs(board[y][x]);
                }
            }

            return new Board(newBoard);
        }

        /**
         * y, x 블록을 dir 방향으로 민다.
         *
         * @param dir 방향
         * @param y y좌표
         * @param x x좌표
         */
        private void moveBlock(int[] dir, int y, int x) {
            if (board[y][x] == 0) {
                return;
            }

            while (true) {
                int nextY = y + dir[0];
                int nextX = x + dir[1];

                if (isOutOfIndex(nextY, nextX)) {
                    break;
                }

                final int current = board[y][x];
                final int next = board[nextY][nextX];

                // 해당 방향이 비어있다면
                // 그 위치로 민다.
                if (next == 0) {
                    board[nextY][nextX] = board[y][x];
                    board[y][x] = 0;

                    y = nextY;
                    x = nextX;

                    continue;
                }

                // 해당 방향이 같은 블럭이면
                // 합친다.
                // 이미 합쳐진 블록이면 더이상 합치지 않는다.
                // 해당 값은 음수로 표현한다.
                if (next == current && next > 0) {
                    board[y][x] = 0;
                    board[nextY][nextX] *= -2;

                    y = nextY;
                    x = nextX;

                    break;
                }

                // 다른 블럭이 있는 경우이므로
                // 끝낸다.
                break;
            }

            // 합쳐진 블록의 값을 음수로 체크했으므로, 절댓값으로 표시한다.
            ans = Math.max(ans, Math.abs(board[y][x]));
        }

        private boolean isOutOfIndex(int y, int x) {
            return y < 0 || y >= N || x < 0 || x >= N;
        }
    }
}

moveBlockの方法で解題すればよく、マージされたブロックについては負の値で表される.

説明する。

プール1では,プレート自体を90度回転させ,無条件に上向きに結合すれば,それぞれ4方向を実現したが,結果は同じであった.これらのアイデアを実装するコードは、次のとおりです.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws Throwable {
        Board board = input();

        move(board, 5);

        System.out.println(ans);
    }

    private static Board input() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        N = Integer.parseInt(br.readLine());

        final int[][] board = new int[N][N];

        for (int ni = 0; ni < N; ni++) {
            final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int nj = 0; nj < N; nj++) {
                board[ni][nj] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();

        return new Board(board);
    }

    private static void move(Board board, int remain) {
        if (remain == 0) {
            return;
        }

        final int nextRemain = remain - 1;

        Board next = board;
        for (int i = 0; i < 4; i++) {
            next = next.rotate();
            move(next.copy().up(), nextRemain);
        }
    }

    static class Board {
        private final int[][] board;

        public Board(int[][] board) {
            this.board = board;
        }

        public Board rotate() {
            final int[][] newBoard = new int[N][N];

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    // 회전할 때에는 절댓값을 씌워줘서 기존에 합쳐졌다는 표시가 남은 블록을
                    // 제거해줘야 한다.
                    newBoard[y][x] = Math.abs(board[N - x - 1][y]);
                }
            }

            return new Board(newBoard);
        }

        public Board up() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveUp(y, x);
                }
            }

            return this;
        }

        public Board copy() {
            final int[][] copied = new int[N][N];
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    copied[y][x] = board[y][x];
                }
            }

            return new Board(copied);
        }

        /**
         * y, x 블록을 윗쪽 방향으로 민다.
         *
         * @param y y좌표
         * @param x x좌표
         */
        private void moveUp(int y, int x) {
            if (board[y][x] == 0) {
                return;
            }

            while (true) {
                int nextY = y - 1;
                int nextX = x;

                if (isOutOfIndex(nextY, nextX)) {
                    break;
                }

                final int current = board[y][x];
                final int next = board[nextY][nextX];

                // 해당 방향이 비어있다면
                // 그 위치로 민다.
                if (next == 0) {
                    board[nextY][nextX] = board[y][x];
                    board[y][x] = 0;

                    y = nextY;
                    x = nextX;

                    continue;
                }

                // 해당 방향이 같은 블럭이면
                // 합친다.
                // 이미 합쳐진 블록이면 더이상 합치지 않는다.
                // 해당 값은 음수로 표현한다.
                if (next == current && next > 0) {
                    board[y][x] = 0;
                    board[nextY][nextX] *= -2;

                    y = nextY;
                    x = nextX;

                    break;
                }

                // 다른 블럭이 있는 경우이므로
                // 끝낸다.
                break;
            }

            // 합쳐진 블록의 값을 음수로 체크했으므로, 절댓값으로 표시한다.
            ans = Math.max(ans, Math.abs(board[y][x]));
        }

        private boolean isOutOfIndex(int y, int x) {
            return y < 0 || y >= N || x < 0 || x >= N;
        }
    }
}

ほとんどのコードは同じですが、rotateを追加し、無条件に上へ移動するのではなく、4つの方向に移動します.