✅문제 요약

1. nxm 종이 위 테트로미노를 하나 놓았을 때 각 칸의 합이 최대가 될 때 몇인지 출력
2. 테트로미노는 회전, 대칭이 가능하다
3. 종이 밖을 나갈 수 없다

✅문제 풀이

각 도형들을 보면 모든 도형이 한 붓 그리기가 된다면 BFS를 돌려서 찾을 수 있다.
하지만 자주색 도형은 한 붓 그리기가 안된다.
방법1. bfs로 4칸을 탐색하여 가장 큰 값을 찾고 자주색 도형은 직접 인덱싱하여 4칸 탐색
방법2. 모든 도형을 인덱스로 탐색

난 방법2를 사용했다.

import sys
input = sys.stdin.readline

shapes = [([1, 0], [2, 0], [3, 0]),
          ([0, 1], [0, 2], [0, 3]),
          ([1, 0], [0, 1], [1, 1]),
          ([0, 1], [1, 1], [1, 2]),
          ([0, 1], [-1, 1], [-1, 2]),
          ([1, 0], [1, 1], [2, 1]),
          ([1, 0], [1, -1], [2, -1]),
          ([0, 1], [1, 0], [2, 0]),
          ([0, 1], [1, 1], [2, 1]),
          ([1, 0], [2, 0], [2, 1]),
          ([1, 0], [2, 0], [2, -1]), 
          ([0, 1], [0, 2], [-1, 2]),
          ([0, 1], [0, 2], [1, 2]),
          ([1, 0], [1, 1], [1, 2]),
          ([-1, 0], [-1, 1], [-1, 2]),
          ([1, 0], [2, 0], [1, 1]),
          ([1, 0], [2, 0], [1, -1]),
          ([0, 1], [0, 2], [-1, 1]),
          ([0, 1], [0, 2], [1, 1])]


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
res = 0

for i in range(N):
    for j in range(M):
        for shape in shapes:
            cnt = arr[i][j]
            for s in shape:
                r, c = i+s[0], j+s[1]
                if 0 <= r < N and 0 <= c < M:
                    cnt += arr[r][c]
                else:
                    break
            else:
                res = max(res, cnt)

print(res)