백준 14500 – 테트로미노 

# https://www.acmicpc.net/problem/14500
from sys import stdin

# 입력: 종이의 세로 크기 N과 가로 크기 M
n, m = map(int, stdin.readline().split())
# graph: 각 칸에 쓰여 있는 수를 저장하는 2차원 리스트
graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
# visited: 각 칸의 방문 여부를 확인하는 2차원 리스트
visited = [[False] * m for _ in range(n)]
# highest_value: 보드에서 가장 큰 값, 나머지 탐색을 최적화하기 위해 사용
highest_value = max(map(max, graph))
# max_count: 테트로미노가 놓인 칸에 쓰인 수들의 합의 최대값
max_count = 0

def dfs(x, y, count, score):
    global max_count, graph
    # 탐색을 중단하는 조건: 남은 칸으로 얻을 수 있는 최대 점수를 더해도 현재 max_count보다 작은 경우
    if max_count > score + highest_value * (4 - count):
        return
    # 기저 조건: 4칸 모두 탐색했을 때, max_count 갱신
    if count == 4:
        max_count = max(max_count, score)
        return
    # 탐색 방향: 상, 하, 좌, 우
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        # 경계 조건 확인 및 방문하지 않은 칸에 대해서만 탐색
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            # 임시로 점수 저장, 이를 통해 탐색 후 원래 상태로 복구
            temp = graph[nx][ny]
            # 'ㅗ' 모양 테트로미노 처리를 위한 조건, 3번째 칸에서 추가 탐색
            if count == 2:
                # 'ㅗ' 모양과 같이 특정 지점에서 방향 전환을 통해 탐색해야 하는 경우,
                # 현재 방문한 지점(nx, ny)을 방문 처리하고,
                # 원래 위치(x, y)를 기준으로 다음 칸을 탐색하지 않고,
                # 즉시 다른 방향으로의 추가 탐색을 시도합니다.
                # 이는 'ㅗ', 'ㅜ', 'ㅏ', 'ㅓ' 모양을 포함하여 테트로미노가
                # 일렬로만 이어지지 않는 특수한 형태를 처리하기 위한 것입니다.
                visited[nx][ny] = True
                # 추가 탐색을 통해 현재 위치에서 다른 방향으로의 점수를 계산하며,
                # 이때 count를 증가시켜 탐색 깊이를 조절합니다.
                # score + temp는 현재까지의 점수에 방문한 칸의 점수를 추가한 것입니다.
                dfs(x, y, count + 1, score + temp)
                # 탐색이 끝난 후, 방문 처리를 해제하여 다른 경로 탐색 시 재사용할 수 있도록 합니다.
                visited[nx][ny] = False


# 모든 칸에 대해 DFS 수행
for i in range(n):
    for j in range(m):
        # 현재 칸을 시작점으로 설정
        visited[i][j] = True
        dfs(i, j, 1, graph[i][j])
        # 탐색이 끝난 후 방문 상태 초기화
        visited[i][j] = False

# 최대 점수 출력
print(max_count)