[銀色1]18405号:競争的伝染

🛠 質問する

https://www.acmicpc.net/problem/18405

👩🏻‍💻 解決策

ウイルスのタイプ、位置、および経過時間を格納するdequeが生成されました
sortによりローエンドウイルスが感染し始めます
bfsでウイルスを感染し、経過時間と入力したS値が等しい場合はwhileゲートを閉じる
ソースコード

from collections import deque
n, k = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
S, X, Y = map(int, input().split())
virus = []

for i in range(n):
  for j in range(n):
    if data[i][j] != 0:
      virus.append([data[i][j], i, j, 0])
virus.sort()

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

q = deque(virus)
while q:
  virus_type, x, y, now = q.popleft()
  if now == S:
    break

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n:
      if data[nx][ny] == 0:
        data[nx][ny] = virus_type
        q.append([virus_type, nx, ny, now+1])

print(data[X-1][Y-1])