Backjun 2636 Python解釈

間違いなく、実施問題が解決し、今日は2636番チーズが解けました.bfsは,シミュレーションで1回問題を解いたことで有名であり,外部空気に接触するチーズだけが溶ける制約条件をどのように処理するかが鍵となる.これとは異なり,時間の複雑さをできるだけ少なくするために困難に近づき,結果として無駄に長い時間を費やした.私が実施問題がもっと難しいと思っているのは、このような雑念がたくさんあるからです.もちろん、より効率的なコードを書くことをずっと考えなければなりません.とにかく始まりが長い

1.質問

https://www.acmicpc.net/problem/2636
下図1に示すように、正方形の格子からなる正方形の板があり、その上に薄いチーズ(灰色の部分)が置かれています.板の縁(<図1>では、四角形のXの部分)にはチーズが入っておらず、チーズには1つ以上の穴が開いていてもよい.
これらのチーズを空気中に入れると溶け、空気に触れる車両は1時間後に溶けます.チーズの穴には空気が入っていませんが、穴を囲むチーズが溶けて穴が開くと空気が穴に入ります.<図1>に示すように、チーズ孔を囲むチーズは溶けず、図2>に示すように、「c」と表記された部分だけが1時間後に溶けて消える.
<図1>オリジナルチーズ形状

あと1時間で<図2>の「c」で表される部分は<図3>に示すように溶けて消えてしまいます.
<図2>1時間後のチーズの形

<図3>2時間後のチーズの形

<図3>チーズが2時間後の様子で、残りの破片はあと1時間で全部溶けてしまいました.そのため、初めてチーズが全部溶けて消えるまで3時間かかります.<図3>に示すように、チーズは融解中にいくつかに分けることができる.
矩形板の大きさとチーズが板に置かれたとき、空気中のチーズがすべて溶けるのに要する時間と、すべて溶ける1時間前にチーズの破片が残った格子数を入力するプログラムを作成します.

2.入力

最初の行は、矩形板の縦横長が正の整数であることを示します.縦横の長さは最大100です.板上の各横線の形状は、上から下へ順に2行目から最後の行までです.チーズのない格子は0で、チーズのある格子は1で、数字の間にスペースがあります.

3.解答

まず「チーズは外の空気だけで溶ける」という制約条件に注意しましょう.
チーズの中の空気は溶けず、外の空気だけで溶けます
->中の空気と外の空気をセットしておきます.
だから私は、チーズの中の空気を0にして、外の空気を2に変えました.(余談ですが、-1に変更しないでください.デバッグ時に-1が占める体積は1または2が占める体積より大きいので、見分けがつきにくいです...)
ここだけ知っていれば、ほとんどが解けてしまうのに、どうして外の空気を2に変えるのでしょうか.ここではbfsを使用します.どうせ板の外には絶対にチーズは入れないから、(0,0)外の空気に違いない.そこで,(0,0)から,自分に隣接する外気を探索し,それを2(1)に変換する.
そして、外の空気と触れたチーズだけを0に変えます.(外の空気であることを認識させる)このとき、外の空気が何であれ、チーズであればチーズcnt++を与える.(2)
最後に、time++、チーズが全部溶けるまで(1)と(2)を無限に繰り返します.
確かに近づきにくい感じ

4.ソースコード

# 치즈 (골드 5)
from collections import deque

dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]

def bfs(y, x):
    global board, h, w

    q = deque()
    q.append([y, x])
    visited = [[0] * w for _ in range(h)]
    visited[y][x] = 1
    board[y][x] = 2
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if visited[ny][nx] == 0 and board[ny][nx] != 1:
                    board[ny][nx] = 2
                    visited[ny][nx] = 1
                    q.append([ny, nx])

# 녹을 수 있는 치즈인지 아닌지 구분하는 함수
def check(y, x):
    global h, w, board
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            if board[ny][nx] == 2:
                return True
    return False

# 입력
h, w = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]

time = 0
previous_cheese = 0

# 치즈가 다 녹아 없어질 때까지 반복
while True:
    # 외부 공기를 다른 값(2)으로 설정 
    # 왜냐면 안의 공기도 0이고 밖에 공기도 0인데 치즈는 밖의 공기에만 녹으니까!
    bfs(0, 0)

    # 외부 공기에 노출된 치즈를 0로
    cheese = 0
    for i in range(h):
        for j in range(w):
            if board[i][j] == 1:
                cheese += 1
                if check(i, j):
                    board[i][j] = 0
    if cheese == 0:
        break
    else:
        previous_cheese = cheese
    time += 1

print(time)
print(previous_cheese)

5.分析、結果

久しぶりに解けたので、思ったより難しかったです.雑念を減らし、考えがうまくいかないたびに注釈を書く.

いつでも質問と指導を歓迎します!間違ったところを教えてください:)