====== 테트로미노 ======

===== 풀이 =====
  * 5종류의 테트로미노를 회전/대칭시키면 총 19개의 모양이 나온다. 이 19개의 모양들을 각각 그리드 위에서 움직여보면서 점수를 계산해보고, 그중에서 최대값을 구하면 된다. 알고리즘은 간단하지만, 구현이 귀찮다.
  * 구현방식에서 고민할것은 우선 19개의 모양을 어떻게 코딩할것인가이다
    * 그냥 19개의 모양을 다 하드코딩 하는 방법도 있고, 5개의 모양을 하드코딩한뒤 회전,대칭하는 함수를 만들줘서 5개를 자동으로 19개로 확장시키는 방법도 있다. 그냥 DFS와 같은 방식으로 19개의 모양을 알아서 찾아내도록 하는 방법도 있다 (이 경우는 T모양에 대해서는 따로 처리해줘야 한다).
  * 그냥 19개 모양을 하드코딩해서 주는 것이 코드가 가장 깔끔하다는 결론을 내리고 그렇게 구현했다.
  * 어떤 블럭이 어떤 위치에 놓일때의 점수를 계산하는 것은 그냥 하면 O(4)이다. 이것을 줄이는 것은 모양이 복잡해서 간단히 되지는 않지만, 일일히 처리를 잘 해주면 prefix sum이나 sliding window 등의 요령으로 O(2) 정도까지는 줄일수 있을것 같다. 하지만 굳이 그걸 구현하는 것은 패스..
  * 결국 시간복잡도는 O(19*4*R*C) = O(RC) 이긴 하다.
  * 하지만 다른 솔루션들에 비해서 시간차이가 꽤 크게 난다. 가장 빠른 코드들은 250ms 정도인데 (DFS로 구현), 이 방식은 4000ms 이상이 걸린다. 사실 이것은 DFS와 하드코딩의 차이라기 보다는, DFS로 하면 좀더 가지치기를 추가하기에 용이하기 때문이다. 
  * 간단하게 추가 가능한 가지치기 방식은, 그리드에 있는 가장 큰 값 max_val을 찾아준다. 그리고 블럭을 배치했을때의 스코어를 계산하는 과정에서 나올수 있는 가장 큰 점수를 계속 비교한다. 첫번째 칸의 점수가 x라면 x+3*max_val 이 현재까지의 최고 점수보다 낮다면 나머지 칸을 볼 필요가 없이 바로 다음 위치에서 점수를 계산하면 된다. 첫번째 칸에서 안걸러진다면, 다시 두번째 칸의 점수를 확인하고, 그 점수가 y라면 x+y+max_val*2 가 가능한 최고 점수가 되고, 이것으로 또 가자치기를 할수 있다. 이런식으로 처리했더니 4000ms정도의 시간을 1000ms 정도로 줄일 수 있었다
  * max_val을 전체에서 구하는 것이 아니라, 더 작은 범위들에 대해서 (예를들면 4x4 공간마다) 구해놓는다면, 가능한 가장 큰 점수를 더욱 정확하게 예측할수 있고 그럴면 가지치기의 효율이 더 올라가서 시간적으로 훨씬 더 단축시키는것이 가능할 것이다. 하지만 거기까지 구현하기 시작하면 너무 귀찮아지는 관계로 패스..


===== 코드 =====

==== 코드 1 - 가지치기 없음 ====
<dkpr py>
"""Solution code for "BOJ 14500. 테트로미노".

- Problem link: https://www.acmicpc.net/problem/14500
- Solution link: http://www.teferi.net/ps/problems/boj/14500

Tags: [Implementation]
"""

TETROMINOES = (
    # I
    ((0, 0), (0, 1), (0, 2), (0, 3)),
    ((0, 0), (1, 0), (2, 0), (3, 0)),
    # O
    ((0, 0), (0, 1), (1, 0), (1, 1)),
    # T
    ((0, 0), (0, 1), (0, 2), (1, 1)),
    ((0, 0), (1, 0), (1, 1), (2, 0)),
    ((0, 1), (1, 0), (1, 1), (1, 2)),
    ((0, 1), (1, 0), (1, 1), (2, 1)),
    # J
    ((0, 0), (0, 1), (0, 2), (1, 2)),
    ((0, 0), (0, 1), (1, 0), (2, 0)),
    ((0, 0), (1, 0), (1, 1), (1, 2)),
    ((0, 1), (1, 1), (2, 0), (2, 1)),
    # L
    ((0, 0), (0, 1), (0, 2), (1, 0)),
    ((0, 0), (1, 0), (2, 0), (2, 1)),
    ((0, 2), (1, 0), (1, 1), (1, 2)),
    ((0, 0), (0, 1), (1, 1), (2, 1)),
    # S
    ((0, 1), (0, 2), (1, 0), (1, 1)),
    ((0, 0), (1, 0), (1, 1), (2, 1)),
    # Z
    ((0, 0), (0, 1), (1, 1), (1, 2)),
    ((0, 1), (1, 0), (1, 1), (2, 0)),
)


def main():
    N, M = [int(x) for x in input().split()]
    grid = [[int(x) for x in input().split()] for _ in range(N)]

    answer = 0
    for tet in TETROMINOES:
        h = max(r for r, c in tet)
        w = max(c for r, c in tet)
        for r in range(N - h):
            for c in range(M - w):
                score = sum(grid[r + dr][c + dc] for dr, dc in tet)
                answer = max(score, answer)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - 가지치기 ====
<dkpr py>
"""Solution code for "BOJ 14500. 테트로미노".

- Problem link: https://www.acmicpc.net/problem/14500
- Solution link: http://www.teferi.net/ps/problems/boj/14500

Tags: [Implementation]
"""

TETROMINOES = (
    # I
    ((0, 0), (0, 1), (0, 2), (0, 3)),
    ((0, 0), (1, 0), (2, 0), (3, 0)),
    # O
    ((0, 0), (0, 1), (1, 0), (1, 1)),
    # T
    ((0, 0), (0, 1), (0, 2), (1, 1)),
    ((0, 0), (1, 0), (1, 1), (2, 0)),
    ((0, 1), (1, 0), (1, 1), (1, 2)),
    ((0, 1), (1, 0), (1, 1), (2, 1)),
    # J
    ((0, 0), (0, 1), (0, 2), (1, 2)),
    ((0, 0), (0, 1), (1, 0), (2, 0)),
    ((0, 0), (1, 0), (1, 1), (1, 2)),
    ((0, 1), (1, 1), (2, 0), (2, 1)),
    # L
    ((0, 0), (0, 1), (0, 2), (1, 0)),
    ((0, 0), (1, 0), (2, 0), (2, 1)),
    ((0, 2), (1, 0), (1, 1), (1, 2)),
    ((0, 0), (0, 1), (1, 1), (2, 1)),
    # S
    ((0, 1), (0, 2), (1, 0), (1, 1)),
    ((0, 0), (1, 0), (1, 1), (2, 1)),
    # Z
    ((0, 0), (0, 1), (1, 1), (1, 2)),
    ((0, 1), (1, 0), (1, 1), (2, 0)),
)


def main():
    N, M = [int(x) for x in input().split()]
    grid = [[int(x) for x in input().split()] for _ in range(N)]

    max_num = max(max(row) for row in grid)
    possible_max_score = max_num * 4
    answer = 0
    for tet in TETROMINOES:
        h = max(r for r, c in tet)
        w = max(c for r, c in tet)
        for r in range(N - h):
            for c in range(M - w):
                score = possible_max_score
                for dr, dc in tet:
                    score += grid[r + dr][c + dc] - max_num
                    if score <= answer:
                        break
                else:
                    answer = score

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}