質問リンク

トロミノ

問題の説明

ポリオミ黄色とは、1*1サイズの正方形が複数あるパターンを意味します.トロミノは4つの正方形からなるドオミノで、このトロミノはあります
5種類あります.1000個未満の自然数が書かれたN*Mサイズの紙ごとに、正方形を1つ置くには、1つの正方形しか含まれず、回転して対称にすることができます.テトロミノが手配したカンソ協定の最大限度は?

問題を解く

90度180度270度、x軸y軸対称などの格子を初めて回してみましたが失敗しました^^

試してみる。

特定の格子から始め,dfsを用いて可能なすべてのテトロミノブロックのリストを可能な値に入れ,可能な値リストで最大値を探した.時間が経つと、必ずしも可能性リストに保存して最大値を探すのではなく、dfsを迂回して可能なトロミノを探すときに最大値を更新することで、時間を減らすことができます.

2-dfsを試します

dfs,bfsを用いて,(x,y)格子から4格子のトロミノを探した.

#(x,y)를 시작으로 4칸 찾기 
def dfs(x, y, block, count, max_num):
    global answer
    if count == 4:
        answer = max(answer, max_num)
        return
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and (nx, ny) not in block:
            dfs(nx, ny, block+[(nx, ny)], count+1, max_num+board[nx][ny])

-> dfs, bfs를 이용하면 다섯개의 테트로미노 종류중 'ㅗ' 모양을 갖는 테트로미노는 찾을 수 없다. 

の「凸」形状を有するトロミノを考慮するために,特定の格子の東西南北4方向を決定した.
->範囲内で凸形状が可能な場合は、凸形状の格子の和を求めてmaxを更新します
->範囲内で+の形ができれば、+を形成する格子の和から東西南北の格子ごとに最小値を外します.

def exception(x, y):
    global answer
    tmp = []
    min_val = 1000
    for i in range(4):
        if in_range(x+dx[i], y+dy[i]):
            min_val = min(min_val, board[x+dx[i]][y+dy[i]])
            tmp.append((x+dx[i], y+dy[i]))
    # 범위 내에 ㅗ모양이 가능하면
    if len(tmp) == 3:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp))
    #범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
    elif len(tmp) == 4:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp)-min_val)

完全なコード

import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

def get_score(blocks):
    total = 0
    for block in blocks:
        total += board[block[0]][block[1]]
    return total

#(x,y)를 시작으로 4칸 찾기 -> ㅗ모양은 포함 못함 ㅠ
def dfs(x, y, block, count, max_num):
    global answer
    if count == 4:
        answer = max(answer, max_num)
        return
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and (nx, ny) not in block:
            dfs(nx, ny, block+[(nx, ny)], count+1, max_num+board[nx][ny])

def exception(x, y):
    global answer
    tmp = []
    min_val = 1000
    for i in range(4):
        if in_range(x+dx[i], y+dy[i]):
            min_val = min(min_val, board[x+dx[i]][y+dy[i]])
            tmp.append((x+dx[i], y+dy[i]))
    # 범위 내에 ㅗ모양이 가능하면
    if len(tmp) == 3:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp))
    #범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
    elif len(tmp) == 4:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp)-min_val)

for i in range(N):
    for j in range(M):
        dfs(i, j, [(i,j)], 1, board[i][j])
        #+모양도 추가하기
        exception(i, j)
        
            
print(answer)

試し3-bfs

bfsで解いてみると、やはりdfsの方が直感的で編成しやすいので、

import sys
from collections import deque

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False
    
def bfs(x,y):
    max_num = 0
    queue = deque()
    #x, y, 이전 x, 이전 y, count, total_score
    queue.append((x, y, 0, 0, 1, board[x][y]))

    while queue:
        x, y, pre_x, pre_y, cnt, total_score = queue.popleft()
        if cnt == 4:
            max_num = max(max_num, total_score)
            continue
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            #이동한 좌표가 행렬의 범위를 만족하고, 해당 이동이 이전 좌표로의 이동이 아니면 !!
            if in_range(nx, ny) and (nx, ny) != (pre_x, pre_y):
                queue.append((nx, ny, x, y, cnt+1, total_score+board[nx][ny]))
    return max_num

def get_score(blocks):
    total = 0
    for block in blocks:
        total += board[block[0]][block[1]]
    return total

def exception(x, y):
    global answer
    tmp = []
    min_val = 1000
    for i in range(4):
        if in_range(x+dx[i], y+dy[i]):
            min_val = min(min_val, board[x+dx[i]][y+dy[i]])
            tmp.append((x+dx[i], y+dy[i]))
    # 범위 내에 ㅗ모양이 가능하면
    if len(tmp) == 3:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp))
    #범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
    elif len(tmp) == 4:
        tmp.append((x,y))
        answer = max(answer, get_score(tmp)-min_val)

for i in range(N):
    for j in range(M):
        answer = max(answer, bfs(i,j))
        #+모양도 추가하기
        exception(i, j)
            
print(answer)

に感銘を与える

テトロミノを直接回転させるために、3時間も飛んだように^ㅇ^,接着剤を探して、可能性のあるテトロミノ座標をハードコーディングして見つけたコードをたくさん見つけましたが、出題者の意図はそうではないようで悩んでいましたが、dfsは凸形が見つからないので,これは別の考慮が必要であり,これは難題のようだ.

本当に大変でしたが、