[伯俊]14500テルミノPython
12695 ワード
トロミノ
質問する
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.
美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.
入力
第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.
しゅつりょく
最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.
ソリューション
接続
もう一つの関数を作って実現します.
n,m = map(int,input().split())
grid = list(list(map(int,input().split())) for _ in range(n))
max_val = max(map(max, grid))
dr = [0,1,0,-1]
dc = [1,0,-1,0]
def dfs(r,c,cnt,S) :
global a
if a >= S + max_val * (4-cnt) :
return
if cnt >=4 :
if S>a :
a = S
return
for d in range(4) :
nr = r + dr[d]
nc = c + dc[d]
if 0<=nr<n and 0<=nc<m and not visited[nr][nc] :
visited[nr][nc] = 1
dfs(nr,nc,cnt+1,S+grid[nr][nc])
visited[nr][nc] = 0
def cross(r,c,S) :
global a
tmp = []
for d in range(4) :
nr = r + dr[d]
nc = c + dc[d]
if 0<=nr<n and 0<=nc<m :
S += grid[nr][nc]
tmp.append(grid[nr][nc])
if len(tmp) == 3 :
if S > a :
a = S
if len(tmp) == 4 :
for t in tmp :
if S - t >a :
a = S - t
a = 0
visited = [[0]*m for _ in range(n)]
for r in range(n) :
for c in range(m) :
visited[r][c] = 1
dfs(r,c,1,grid[r][c])
visited[r][c] = 0
cross(r,c,grid[r][c])
print(a)Reference
この問題について([伯俊]14500テルミノPython), 我々は、より多くの情報をここで見つけました https://velog.io/@holawan/백준-14500테트로미노-pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol