241228 테트로미노

static int maxSum = 0;
static int n, m;
static int[][] board;
static int maxValue = 0;
static boolean[][] visited;

static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	board = new int[n][m];

	for (int i = 0; i < n; i++) {
		st = new StringTokenizer(br.readLine());
		for (int j = 0; j < m; j++) {
			board[i][j] = Integer.parseInt(st.nextToken());
			maxValue = Math.max(maxValue, board[i][j]);
		}
	}

	visited = new boolean[n][m];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			searchTetromino(i, j, 1, board[i][j]);
			visited[i][j] = false;
		}
	}

	System.out.println(maxSum);
}

static void searchTetromino(int x, int y, int depth, int sum) {
	if (sum + maxValue * (4 - depth) <= maxSum)
		return;
	if (depth == 4) {
		maxSum = Math.max(maxSum, sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (isValid(nx, ny)) {
			if (depth == 2) {
				visited[nx][ny] = true;
				searchTetromino(x, y, depth + 1, sum + board[nx][ny]);
				visited[nx][ny] = false;
			}
			visited[nx][ny] = true;
			searchTetromino(nx, ny, depth + 1, sum + board[nx][ny]);
			visited[nx][ny] = false;
		}
	}
}

static boolean isValid(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y];
}

출처:https://www.acmicpc.net/problem/14500