リンクテキスト

トロミノ

ラフデザイン
グラフィックの対称回転2*4の計8種類を思い浮かべます.でもdxdyは全部で8個作ると思います一般的なDFSポリシー自体が菱形表の形で伝播していることは分かっているので,ここに含めるべきであると考えられるが,一般的なDFSアクセスポイントには戻る部分は存在しないので,遡及ポリシーを採用する方法をとるべきである.しかし、最後のテストケースの3番目には答えが見つからなかった.何が問題なのか分からないが、DFSポリシーを開く過程でアクセスしたポイントが再びfalseとして処理されていることに気づいたが、グラフィックには達していない.
この部分も一緒に処理すべきだと思いますが、本当に出られないので、関連記事を参考にして、例外過程を体現しました.

https://yubh1017.tistory.com/47(図では非常に明確に説明されている)を参照してください.

package oneDay_twoSol.DB_FirstSearch;

import java.util.Scanner;

public class Tetromino {

    static int[][] ey = {{0, 0, 0, 1}, {1, 1, 1, 0}, {0, 1, 2, 1}, {0, 1, 2, 1}};
    static int[][] ex = {{0, 1, 2, 1}, {0, 1, 2, 1}, {1, 1, 1, 0}, {0, 0, 0, 1}};
    // 예외의 도형 . y축 x축.
    
    static int n, m;
    static int dy[] = {-1, 1, 0, 0};
    static int dx[] = {0, 0, -1, 1};
    // 위 아래 왼쪽 오른쪽
    static int max;
    static int board[][];
    static boolean visited[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i, j, 0, 0);
                except(i, j);
            }
        }
        System.out.println(max);
    }

    static void dfs(int y, int x, int depth, int sum) {

        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int tempY = y + dy[i];
            int tempX = x + dx[i];
            if (tempX >= 0 && tempY >= 0 && tempY < n && tempX < m) {
                if (!visited[tempY][tempX]) {
                    visited[tempY][tempX] = true;
                    dfs(tempY, tempX, depth + 1, sum + board[tempY][tempX]);
                    visited[tempY][tempX] = false;
                }
            }
        }
    }

    static void except(int y, int x) {
        int sum = 0;
        boolean check;
        for (int i = 0; i < 4; i++) {
            sum = 0;
            check = true;
            for (int j = 0; j < 4; j++) {
                int tempY = y + ey[i][j];
                int tempX = x + ex[i][j];
                if (tempX >= 0 && tempY >= 0 && tempY < n && tempX < m) {
                    sum += board[tempY][tempX];
                } else {
                    check = false;
                    break;
                }
            }
            if (check) {
                max = Math.max(max, sum);
            }
        }
    }

}