[白俊]18405回競争性伝染

リンク:https://www.acmicpc.net/problem/18405

🌐 質問する

NxNサイズの試験管があります.試験管は1 x 1サイズの格子に分けられ,特定の位置にウイルスが存在する可能性がある.すべてのウイルスは1番からK番までのウイルスの種類の一つです.
試験管に存在するすべてのウイルスは1秒ごとに上,下,左,右方向に増殖した.しかし、毎秒番号の低いウイルスから増殖し始める.また、増殖中にあるセルにウイルスがすでに存在する場合は、他のウイルスに入ることはできません.
試験管の大きさとウイルスの位置情報を得た場合は、S秒後(X,Y)にウイルスの種類を出力するプログラムを作成します.S秒後にこの位置にウイルスがない場合は0を出力します.このときXとYはそれぞれ行と列の位置を示し,試験管の最左上角は(1,1)に対応する.
例えば、3 x 3サイズの試験管があると仮定する.異なる1番、2番、3番ウイルスはそれぞれ(1、1)、(1、3)、(3、1)に位置している.このとき2秒後、(3,2)に存在するウイルスの種類を計算します.

一秒後、試験官の状態は以下の通りです.

2秒後、試験官の状態は以下の通りです.

その結果,2秒後(3,2)に存在するウイルスの種類は3番ウイルスであった.したがって,出力3が正解である.

1グラム

from collections import deque
n,k = map(int, input().split())
graph = []
virus = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((graph[i][j], i, j))

s,X,Y = map(int, input().split())

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

def bfs(s,X,Y):
    q = deque(virus)
    count = 0
    while q:
        if count == s:
            break
        for _ in range(len(q)):
            prev, x, y = q.popleft()
            for i in range(4):
                nx = x+ dx[i]
                ny = y + dy[i]
                if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y]
                    q.append((graph[nx][ny], nx, ny))
        count += 1
    return graph[X-1][Y-1]

virus.sort()
print(bfs(s,X,Y))