BOJ 14500. テテルミノ(Python)


BOJ 14500. テテルミノ(Python)


質問リンク
問題の説明
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.
  • 正方形は互いに重ならない.
  • 図形はすべてつながっています.
  • 正方形のエッジの間には接続されているはずです.つまり、必ずしも頂点と重なる必要はありません.
  • 4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

    美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
    1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
    トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.


    ソリューション
    対称に刻まれ,回転する可能性のあるすべての状況を徹底的に探索した.正解は正しいですが、時間がかかります.
    コード#コード#
    # import sys
    # sys.stdin = open('input.txt')
    
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    # 테트로미노 회전, 대칭으로 나올 수 있는 모든 종류
    tetromino_lst = [
        [(0,0), (0,1), (0,2), (0,3)],
        [(0,0), (1,0), (2,0), (3,0)],
        [(0,0), (0,1), (1,0), (1,1)],
        [(0,0), (0,1), (0,2), (1,0)],
        [(1,0), (1,1), (1,2), (0,2)],
        [(0,0), (1,0), (1,1), (1,2)],
        [(0,0), (0,1), (0,2), (1,2)],
        [(0,0), (1,0), (2,0), (2,1)],
        [(2,0), (2,1), (1,1), (0,1)],
        [(0,0), (0,1), (1,0), (2,0)],
        [(0,0), (0,1), (1,1), (2,1)],
        [(0,0), (0,1), (0,2), (1,1)],
        [(1,0), (1,1), (1,2), (0,1)],
        [(0,0), (1,0), (2,0), (1,1)],
        [(1,0), (0,1), (1,1), (2,1)],
        [(1,0), (2,0), (0,1), (1,1)],
        [(0,0), (1,0), (1,1), (2,1)],
        [(1,0), (0,1), (1,1), (0,2)],
        [(0,0), (0,1), (1,1), (1,2)]
    ]
    max_v = 0
    # 완전탐색으로 모든 점에서 테트로미노 별 합을 구하고 최대값과 비교
    for x in range(N):
        for y in range(M):
            for tetromino in tetromino_lst:
                sum_v = 0
                for dx, dy in tetromino:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < N and 0 <= ny < M:
                        sum_v += arr[nx][ny]
                if sum_v > max_v:
                    max_v = sum_v
    print(max_v)