구현, 완전탐색 - 14500번: 테트로미노

시간 초과 주의: 입력 받을 때 sys.stdin.readline으로 받고, 리스트 중복 탐색하지 않도록 주의!

import sys

# 입력 양 많을 때 input()보다 훨씬 빠름 (표준 입력 버퍼에서 바로 읽기)
input = sys.stdin.readline

maps = []
# inputs = sys.stdin.readlines()
n, m = map(int, input().split())

for i in range(1, n + 1):
    line = list(map(int, input().split()))
    maps.append(line)

# 테트로미노 회전, 대칭 가능 -> 5개의 테트로미노에서 총 19가지의 경우의 수 존재
i_list = [
    [0, 0, 1, 1],
    [0, 0, 0, 0],
    [0, 1, 2, 3],
    [0, 0, 0, -1],
    [0, 1, 1, 1],
    [0, 1, 2, 2],
    [0, 0, -1, -2],
    [0, 0, 1, 2],
    [0, 0, 1, 2],
    [0, 0, 0, 1],
    [0, 0, 0, 1],
    [0, 1, 1, 2],
    [0, 1, 0, -1],
    [0, 0, -1, -1],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, -1],
    [0, 0, -1, 1],
    [0, 1, 2, 1],
]
j_list = [
    [0, 1, 0, 1],
    [0, 1, 2, 3],
    [0, 0, 0, 0],
    [0, 1, 2, 2],
    [0, 0, 1, 2],
    [0, 0, 0, 1],
    [0, 1, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 1, 1],
    [0, 1, 2, 0],
    [0, 1, 2, 2],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 2],
    [0, 1, 1, 2],
    [0, 1, 2, 1],
    [0, 1, 2, 1],
    [0, 1, 1, 1],
    [0, 0, 0, 1],
]

max_sum = 0  # 4칸의 합 중 최댓값

# k: 가능한 테트로미노 경우의 수 (0 ~ 18) 총 19가지
for k in range(0, 19):
    # 맵 전체를 훑기
    for i in range(0, n):
        for j in range(0, m):

            sum_1 = 0  # 이번 경우의 수의 4칸의 합
            # 더하려는 4개의 좌표 체크
            for idx in range(0, 4):
                # 리스트 탐색 반복, 루프 중첩 등 같은 계산 두번하지 않도록 주의! 시간초과 주의
                x = i + i_list[k][idx]
                y = j + j_list[k][idx]
                # 더하려는 4개 좌표가 맵 내부에 존재 시
                if 0 <= x < n and 0 <= y < m:
                    sum_1 += maps[x][y]
                else:
                    break
            # 위 for문을 break 없이 완전히 다 돌았다면(4개 좌표 모두 맵 내부에 존재) (for ~ else문)
            # sum_1이 최댓값보다 크다면 갱신
            else:
                max_sum = max(sum_1, max_sum)


print(max_sum)