問題を解く-テトロミノ

トロミノ
に答える
最初に,すべてのテトルミノ形状を配列に保存し,個々に比較することを試みた.回転とミラーの両方を確認する必要があるため、アレイの作成は容易ではありません.ミスの確率も高い.やはりミスだと思いますが、このような方法で解決するのは効率的ではありません.
次は、すべての形状の配列で問題を解決しようとするコードです.

import java.util.*;

public class Main {

    public static int N, M;
    public static int[][] paper;

    public static ArrayList<int[]> getTetoromino(int type, int direction, int[] point) {
        int[][][] dr = {{{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}},
                {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}},
                {{0, 1, 2, 2}, {0, 0, 0, 1}, {0, 0, 1, 2}, {1, 1, 1, 0}, {0, 1, 2, 2}, {0, 0, 0, 1}, {0, 0, 1, 2}, {0, 1, 1, 1}},
                {{0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}},
                {{0, 0, 0, 1}, {0, 1, 1, 2}, {0, 1, 1, 1}, {0, 1, 1, 2}, {0, 0, 0, 1}, {0, 1, 1, 2}, {0, 1, 1, 1}, {0, 1, 1, 2}}};
        int[][][] dc = {{{0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}},
                {{0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}},
                {{0, 0, 0, 1}, {0, 1, 2, 0}, {0, 1, 1, 1}, {0, 1, 2, 2}, {1, 1, 0, 1}, {0, 1, 2, 2}, {0, 1, 0, 0}, {0, 0, 1, 2}},
                {{0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}},
                {{0, 1, 2, 1}, {1, 0, 1, 1}, {1, 0, 1, 2}, {0, 0, 1, 0}, {0, 1, 2, 1}, {1, 0, 1, 1}, {1, 0, 1, 2}, {0, 0, 1, 0}}};
        ArrayList<int[]> result = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            result.add(new int[]{point[0] + dr[type][direction][i], point[1] + dc[type][direction][i]});
        }
        return result;
    }

    public static boolean isRange(ArrayList<int[]> tetromino) {
        for (int[] point : tetromino) {
            if (!(0 <= point[0] && point[0] < N && 0 <= point[1] && point[1] < M)) return false;
        }
        return true;
    }

    public static int getScore(ArrayList<int[]> tetromino) {
        int result = 0;
        for (int[] point : tetromino) {
            result += paper[point[0]][point[1]];
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        paper = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                paper[i][j] = scanner.nextInt();
            }
        }
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int type = 0; type < 5; type++) {
                    for (int direction = 0; direction < 8; direction++) {
                        ArrayList<int[]> tetromino = getTetoromino(type, direction, new int[]{i, j});
                        if (isRange(tetromino)) {
                            result = Math.max(result, getScore(tetromino));
                        }
                    }
                }
            }
        }
        System.out.println(result);
    }
}

配列の1つがスペルを間違えても見つかりにくい.だから他の人のブログを参考にしました.私が参考にした文章はこれ。です.この論文では,ある点で3つの深さを上下左右に移動すれば,4つの回転,反転したすべてのテトルミノ形状を調べることができることを見出した.この事実を知れば、問題を解決するのは難しくない.
インプリメンテーション

import java.util.*;

public class Main {

    public static int N, M;
    public static int[][] paper;
    public static int result = Integer.MIN_VALUE;
    public static boolean[][] visited;
    public static int[] dr = {1, 0, -1, 0};
    public static int[] dc = {0, 1, 0, -1};

    // ㅗ모양을 제외한 다른 모양 모두 탐색
    public static void dfs(int row, int column, int sum, int depth) {
        if (depth == 3) {
            result = Math.max(result, sum);
            return;
        }
        visited[row][column] = true;
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = column + dc[i];
            if (0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc]) {
                dfs(nr, nc, sum + paper[nr][nc], depth + 1);
            }
        }
        visited[row][column] = false;
    }

    // ㅗ모양 탐색
    public static void exDfs(int row, int column) {
        int count = 0;
        int sum = paper[row][column];
        int[] dr = {0, 0, 1, -1};
        int[] dc = {-1, 1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = column + dc[i];
            if (0 <= nr && nr < N && 0 <= nc && nc < M) {
                count++;
                sum += paper[nr][nc];
            }
        }
        if (count == 3)
            result = Math.max(result, sum);
        if (count == 4) {
            for (int i = 0; i < 4; i++) {
                sum -= paper[row + dr[i]][column + dc[i]];
                result = Math.max(result, sum);
                sum += paper[row + dr[i]][column + dc[i]];
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        paper = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                paper[i][j] = scanner.nextInt();
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dfs(i, j, paper[i][j], 0);
                exDfs(i, j);
            }
        }
        System.out.println(result);
    }
}

まず深さ優先探索により,すべての4つの形状を探索し,次いで凸形はまず十字形状の和を求め,次に十字の各突出部分を取り出して比較した.
じかんふくごうどぶんせき
dfs()dfs()dfs()関数は、1つの点から次の点までの回数に1つの深さを乗じることで呼び出し回数を知ることができる.4×3×3=364\times3\times3=364×3×3=36は定数です.exDfs()exDfs()exDfs()関数も定数です.繰り返し文は最大4回まであるからです.したがって,上記コードの時間的複雑さはO(NM)O(NM)O(NM)である.
振り返る
すべてのテルミノの回転と反転を探索する方法が深さ優先で3まで探索されていることを知らない場合は、これは非常に難しいと思います.