[BOJ 2636]チーズ(Python)

10580 ワード
boj BFS アルゴリズム#アルゴリズム# テキストリンク
[BOJ 2636]チーズ(Python)
に答える
BFSを検索して初めてアクセスしました.まずチーズを見つけて、チーズの穴以外のチーズの縁の座標をゴールレバーに入れます.そして列からエッジの座標を取り出し、チーズを溶かします.しかし、print()で撮影したところ、この方法は間違っていたことがわかりました.チーズの穴も溶けています.
問題の鍵はチーズから探すのではなく、空気からBFSを探すことです.空気だけがBFS探索の過程でエッジのチーズを溶かし、チーズの穴に触れず、エッジのチーズだけを溶かす.論理を簡単に説明する.
(1時間ごとに次のプロセスが続くと思えばOK!)

  • プレートの空気をキューに入れ、BFSナビゲーションを行います.

  • キューから空気座標を1つ取り出し,4つの探索を行う.
    次の座標がエアの場合は、次の座標をキューに入れてBFSナビゲーションを行います
    次の座標がチーズであれば、チーズを溶かします.△チーズの穴に触らないでください.
    (-->why?空気から探すので、チーズに囲まれた空気の座標はキューに入らない!)

  • 正解リストにチーズの数を挿入します.
    • コード#コード#
    import sys
from collections import deque

input = sys.stdin.readline
row, col = map(int, input().split())
cheese_board = [list(map(int, input().split())) for _ in range(row)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans_list = []


def bfs():
    visited = [[False] * col for _ in range(row)]
    q = deque([(0, 0)])
    visited[0][0] = True
    cheese_cnt = 0  # 1시간 마다 녹는 치즈의 개수 저장

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny]:
                # 치즈부터 찾는 것이 아닌 공기부터 찾는다.
                # 치즈부터 찾지않고 공기부터 찾게되면 치즈의 구멍은 건드리지 않게 된다.
                if cheese_board[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = True

                # 가장자리 치즈를 녹인다.
                elif cheese_board[nx][ny] == 1:
                    visited[nx][ny] = True
                    cheese_board[nx][ny] = 0
                    cheese_cnt += 1

    ans_list.append(cheese_cnt)
    return cheese_cnt


while True:
    cnt = bfs()
    if cnt == 0:
        print(len(ans_list) - 1)
        print(ans_list[-2])
        break
    Springboot統合redis格納セッション
    ASP.NET MVC 4ドメイン間