BOJ 14500. テテルミノ(Python)
23964 ワード
BOJ 14500. テテルミノ(Python)
質問リンク
問題の説明
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.
美しい大きさは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)
Reference
この問題について(BOJ 14500. テテルミノ(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@jinho0705/BOJ-14500.-테트로미노pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol