[BOJ 17136]カラーペーパーを貼り付ける(Python)

12389 ワード
ついせき ブルトポス boj テキストリンク
質問する
色紙を張る
問題の説明
10 X 10行列、1 x 1,2 x 2,...これは5 x 5色の紙5枚を用いてすべてのマトリクスを0にする問題である.ここにカラーシートを貼り付けるには、すべての領域が1であることを確認します.
私は全部で3つの方法を使った.
  • フルナビゲーション方法
  • 方法
    • は、現在の座標で使用可能な色紙を取得するために使用される.
  • 方法
    • は、現在の座標からカラー紙を貼り付け、この領域をすべて0または1に変換する.
    まず、ナビゲーション方法全体で1が見つかった場合は、この領域で使用可能なすべての色紙を取得します.次に、カラーペーパー(==すべてのグラフィックを0にする)を貼り付け、再帰呼び出しを行います.
    再帰呼び出しが終了したら、貼り付けた色紙を取り外します.(==グラフィックを1にリセット)
    貼り付け可能な色紙がない場合、または色紙ですべての領域を塗りつぶしている場合は、終了します.
    最も重要なのは、1が見つかった場合、再帰呼び出し後すぐに関数を閉じる必要があることです.そうでなければ、正しい答えを探す過程で、全ナビゲーションの重複性のため、時間の複雑さが増加します.
    プールコード
    import sys

input = sys.stdin.readline
graph = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 5, 5, 5, 5, 5]
answer = 30
# 현 좌표에서 사용할 수 있는 색종이가 무엇인지 판별
def possible(x, y):
    number = []
    for n in range(1, 6):
        for i in range(x, x + n):
            for j in range(y, y + n):
                # 0이 발견되면 그 뒤에 색종이도 못쓴다.
                if i < 0 or i >= 10 or j < 0 or j >= 10 or graph[i][j] == 0:
                    return number
        number.append(n)
    return number


# 그래프 색칠하기.
# 좌표, 윈도우 크기, 어떤 값으로 색칠할지
def colored(x, y, n, value):
    for i in range(x, x + n):
        for j in range(y, y + n):
            graph[i][j] = value


# 백트래킹 탐색
def dfs(blank):
    global answer
    # 빈공간이 없으면
    if blank == 0:
        answer = min(answer, 25 - sum(paper[1:]))
        return
    for i in range(10):
        for j in range(10):
            if graph[i][j] == 1:
                # 붙일 수 있는 모든 색종이의 크기
                number = possible(i, j)
                for num in number[::-1]:
                    # 색종이가 있으면 붙이고 재귀
                    if paper[num] > 0:
                        paper[num] -= 1
                        colored(i, j, num, 0)
                        dfs(blank - (num ** 2))
                        paper[num] += 1
                        colored(i, j, num, 1)
                return


temp = 0  # 공간 세기
for i in range(10):
    for j in range(10):
        if graph[i][j] == 1:
            temp += 1
dfs(temp)
print(answer) if answer != 30 else print(-1)
    Androidは、発表されたプログラムのクラッシュ情報を収集する方法
    Beginning Android Games 2 nd Edition(19)ゲームWorld類を読む