Submission #52162753

---

Source Code Expand

from queue import PriorityQueue

n, m = map(int, input().split())
grid = [input() for _ in range(n)]

med = [[0]*m for _ in range(n)]
vis = [[False]*m for _ in range(n)]

for _ in range(int(input())):
    r, c, e = map(int, input().split())
    med[r-1][c-1] = e

sti, stj = next((i, j) for i in range(n) for j in range(m) if grid[i][j] == 'S')

q = PriorityQueue()
q.put((-med[sti][stj], sti, stj))

while not q.empty():
    cm, ci, cj = q.get()
    cm *= -1
    
    if grid[ci][cj] == 'T':
        print('Yes')
        exit()

    if cm == 0 or vis[ci][cj] or grid[ci][cj] == '#':
        continue

    vis[ci][cj] = True

    for ii, ij in [(1,0), (0,1), (-1, 0), (0, -1)]:
        ni, nj = ci + ii, cj + ij
        if not (0 <= ni < n and 0 <= nj < m):
            continue
        if med[ni][nj] >= cm - 1:
            q.put((-med[ni][nj], ni, nj))
            med[ni][nj] = 0
            vis = [[False]*m for _ in range(n)]
        else:
            q.put((-(cm - 1), ni, nj))

print('No')

Submission Info

Judge Result