[BOJ 14500]テロミノ(Python)

質問する

トロミノ

問題の説明

DFSの深さが4のすべてのグラフィックにナビゲートすれば、回転と対称性を含むすべてのグラフィックが解決されます.
ㅎ、ㅎ、ㅎ、ㅎ、ㅎ、単独で回転することができ、深さが3の場合、ここで、前にアクセスしたセルの中から、もう1つのセルを歩くと、ㅎ、ㅎ、ㅎ、ㅎ、ㅎ、ㅎ、ㅎの形を処理できます.-ああ、こんなことがあったので、もう1段行けば、訪れたことのない場所だったはずです.

プールコード

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
answer = 0
visited = [[False] * m for _ in range(n)]
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))


def dfs(depth, x, y, tot):
    global n, m, answer
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1

    if depth == 4:
        answer = max(answer, tot)
        return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        xx = nx + dx[i]
        yy = ny + dy[i]
        # 길이가 3이고, 방금 지나온 곳을 한번 더 지나 그곳이 방문하지 않은 곳이면
        # ㅗ,ㅓ,ㅏ,ㅜ 이다.
        if (
            depth == 3
            and 0 <= nx < n
            and 0 <= ny < m
            and visited[nx][ny]
            and 0 <= xx < n
            and 0 <= yy < m
            and not visited[xx][yy]
        ):
            dfs(depth + 1, xx, yy, tot + graph[xx][yy])
        # 범위 안에 있고 방문하지 않은곳만 탐색
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(depth + 1, nx, ny, tot + graph[nx][ny])
            visited[nx][ny] = False


# 한칸씩 확인하며 dfs
for i in range(n):
    for j in range(m):
        # ㅗ를 제외한 나머지 도형
        visited[i][j] = True
        dfs(1, i, j, graph[i][j])
        visited[i][j] = False
print(answer)