[白俊14500]トロミノ-Java

すべての場合、まず検索するのは個数で、それから最大値を求めます.
DFSで解決すべきだと思います.
しかし、どのように接近するか分からないので、ヒントを参考にしました.
結論として、「ㅜ」以外の図形は再帰呼び出しですべての形式で表示できる
すなわち,始点から上,下,左,右を観察し,値があれば再帰を呼び出し,4回呼び出すことで4つの整数の総和を求めることができる.
また、「ㅜ」パターンの場合は、上、下、左、右を観察し、値があれば合計後、上、下、左、右ともに値があれば、最後に最低値を落とせばよい.
次のコードで実現しました.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {

	static int result = Integer.MIN_VALUE;
	static int N;
	static int M;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static int[][] irr;
	static boolean[][] visited;
	
	static void dfs(int y, int x, int cnt, int pos) {
    	// 도형이 완성되면 최대값 구하고 리턴
		if(cnt == 4) {
			result = Math.max(result, pos);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int nexti = y + dy[i];
			int nextj = x + dx[i];
			
            // 종이 범위에 벗어나면 다음 방향 진행
			if(nexti < 0 || nextj < 0 || nexti >= N || nextj >= M) {
				continue;
			}
            
            // 현재 방문한 위치인지 확인
			if(visited[nexti][nextj]) {
				continue;
			}

			visited[nexti][nextj] = true;
			dfs(nexti, nextj, cnt +1, pos + irr[nexti][nextj]);
			visited[nexti][nextj] = false;
		}
		
	}
	
    // 'ㅜ'도형에서 최대값 구하기
	static void excep(int y, int x) {
    	// wing은 상,하,좌,우
		int wing = 4;
		int min = Integer.MAX_VALUE;
		int sum = irr[y][x];
		
		for(int i = 0; i < 4; i++) {
			int nexti = y + dy[i];
			int nextj = x + dx[i];
			
            // wing이 2개이하면 'ㅜ'도형이 아님
			if(wing <= 2) {
				return;
			}
			
            // 종이 범위에 벗어난 경우 잘린 도형 확인
			if(nexti < 0 || nextj < 0 || nexti >= N || nextj >= M) {
				wing--;
				continue;
			}
			
			min = Math.min(min, irr[nexti][nextj]);
			sum = sum + irr[nexti][nextj];
		}

		// 상,하,좌,우 모두 값 있을시, 그 중 최소값을 뺴준다
		if(wing == 4) {
			sum = sum - min;
		}
		result = Math.max(result, sum);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] arr = str.split(" ");
		
		N = Integer.parseInt(arr[0]);
		M = Integer.parseInt(arr[1]);
		
		irr = new int[N][M];
		visited = new boolean[N][M];

		for(int i = 0; i < N; i++) {
			String[] nrr = br.readLine().split(" ");
			for(int j = 0; j < M; j++) {
				irr[i][j] = Integer.parseInt(nrr[j]); 
			}
		}

		// 종이판 (0,0) 부터 탐색 시작
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dfs(i, j, 0, 0);
				excep(i, j);
			}
		}
		System.out.print(result);
		
	}
 
}