P.14500トロミノ

14500トロミノ
タイムアウトメモリコミット正解率2秒512 MB 515661934412523235.452%
質問する
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.

正方形は互いに重ならない.

図形はすべてつながっています.

正方形のエッジの間には接続されているはずです.つまり、必ずしも頂点と重なる必要はありません.

4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.
入力
第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.
しゅつりょく
最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.
入力例1
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1
サンプル出力1
19
入力例2
4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
サンプル出力2
20
入力例3
4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
サンプル出力3
7
コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class P_14500 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] b_info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] board = new int[b_info[0]][b_info[1]];
        for (int i = 0; i < b_info[0]; i++) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int answer = first_polyomino(board);
        answer = (answer > second_polyomino(board)) ? answer : second_polyomino(board);
        answer = (answer > third_polyomino(board)) ? answer : third_polyomino(board);
        answer = (answer > fourth_polyomino(board)) ? answer : fourth_polyomino(board);
        answer = (answer > fifth_polyomino(board)) ? answer : fifth_polyomino(board);

        System.out.println(answer);
    }

    public static int first_polyomino(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i].length - j >= 4) {
                    int res = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i][j + 3];
                    max = (max > res) ? max : res;
                }

                if (board.length - i >= 4) {
                    int res = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 3][j];
                    max = (max > res) ? max : res;
                }
            }
        }

        return max;
    }

    public static int second_polyomino(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i].length - j >= 2 && board.length - i >= 2) {
                    int res = board[i][j] + board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1];
                    max = (max > res) ? max : res;
                }
            }
        }

        return max;
    }

    public static int third_polyomino(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i].length - j >= 2 && board.length - i >= 3) {
                    int res = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 2][j + 1];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1];
                    max = (max > res) ? max : res;

                    res = board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i + 2][j];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i][j + 1] + board[i + 1][j] + board[i + 2][j];
                    max = (max > res) ? max : res;
                }

                if (board[i].length - j >= 3 && board.length - i >= 2) {
                    int res = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j];
                    max = (max > res) ? max : res;

                    res = board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2] + board[i][j + 2];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 2];
                    max = (max > res) ? max : res;
                }
            }
        }

        return max;
    }

    public static int fourth_polyomino(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i].length - j >= 2 && board.length - i >= 3) {
                    int res = board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 2][j + 1];
                    max = (max > res) ? max : res;

                    res = board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 2][j];
                    max = (max > res) ? max : res;
                }

                if (board[i].length - j >= 3 && board.length - i >= 2) {
                    int res = board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i][j + 2];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 1][j + 2];
                    max = (max > res) ? max : res;
                }
            }
        }

        return max;
    }

    public static int fifth_polyomino(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i].length - j >= 3 && board.length - i >= 2) {
                    int res = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1];
                    max = (max > res) ? max : res;

                    res = board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2] + board[i][j + 1];
                    max = (max > res) ? max : res;
                }

                if (board[i].length - j >= 2 && board.length - i >= 3) {
                    int res = board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1];
                    max = (max > res) ? max : res;

                    res = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1];
                    max = (max > res) ? max : res;
                }
            }
        }

        return max;
    }
}

コードの内容
Brootforceを使っても1000*1000=10000000なので2秒を超えないので、TetrominoごとにBrootforceを使って数字の和の最値を求めました.
回転または対称では,青色のテトラヒドロキシクロアミン2種,黄色のテトラヒドロキシクロアミン1種,オレンジ色のテトラヒドロキシクロアミン8種,緑色のテトラヒドロキシクロアミン4種,ピンクのテトラヒドロキシクロアミン4種が出現した.
2つの繰り返し文では、標準インデックスは[i][j]であり、テトロミノの形状ごとにインデックス範囲を設定し、この値が碁盤サイズを超えない場合にのみ計算を行い、切り分けエラーが発生しないようにする.