[BOJ 17144]スモッグこんにちは!(Python)

質問する

スモッグこんにちは!

問題の説明

問題の要件は次のとおりです.
1.スモッグが広がる.
2.空気清浄機が起動します.

空気清浄機は常に上から下へ2段以上移動するので、Cycleを考慮する必要はありません.

空気清浄機は2つの部屋を占めており、常に第1列に存在します.

スモッグはまず拡散し、空気清浄機を起動します.

スモッグの拡散は一度に拡散する必要があるため、他の値と重複することなく、キューなどのデータ構造に拡散するために座標と量を一時的に含める必要がある.
空気清浄機の起動では、上部と下部の違いは方向だけです.したがって,方向を変える限り,もう一つの方法を作成する必要はなく,再利用可能な構造を用いてコードを実現する.

プールコード

import sys
from collections import deque

input = sys.stdin.readline
n, m, t = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
air = []  # 공기청정기 좌표, 위아래순

for i in range(n):
    if graph[i][0] == -1:
        air.append((i, 0))
# 미먼 확산
def spread():
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1
    # 1. 맵에 존재하는 모든 미세먼지 큐에 삽입
    q = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0:
                # x, y, 미먼 양
                q.append((i, j, graph[i][j]))
    size = len(q)
    for _ in range(size):
        x, y, amount = q.popleft()
        spread_dust = amount // 5
        # 4방 탐색으로 확산될 곳을 찾는다.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 안이며 청정기랑 닿으면 안됨
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != -1:
                q.append((nx, ny, spread_dust))
                amount -= spread_dust
        # 확산된 먼지를 뺀 값을 다시 넣어줌.
        graph[x][y] = amount
    # 큐에는 현재 확산될 먼지밖에 없다. 모두 빼서 확산시킨다.
    while q:
        x, y, dust = q.popleft()
        graph[x][y] += dust


# 공기청정기 가동
def move_dust(x, y, command):
    # command = 0 -> 위쪽, 1-> 아랫쪽
    dx, dy = (0, 0, 0, 0), (0, 0, 0, 0)
    if command == 0:  # 오,위,왼,아래 순
        dx, dy = (0, -1, 0, 1), (1, 0, -1, 0)
    else:  # 오, 아래, 왼, 위 순
        dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
    dir, priv = 0, 0
    # 한바퀴 돌아 공기 청정기로 돌아올때까지 진행
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        # 범위 밖이면 방향을 틀어준다.
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            dir += 1
            continue
        # 종료조건
        if graph[nx][ny] == -1:
            break
        graph[nx][ny], priv = priv, graph[nx][ny]
        x, y = nx, ny


for _ in range(t):
    spread()
    for i in range(2):
        # 각각 위아래 청정기 가동
        move_dust(air[i][0], air[i][1], i)
answer = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] > 0:
            answer += graph[i][j]
print(answer)