ABC348 D — Medicines on Grid

1# -*- coding: utf-8 -*-2 3 4def main():5    import sys6    from collections import deque7    from typing import Any, List, Tuple8 9    input = sys.stdin.readline10 11    h, w = map(int, input().split())12    grid = [list(input().rstrip()) for _ in range(h)]13    n = int(input())14    medicines = list()15 16    sy, sx, ty, tx = 0, 0, 0, 017 18    for i in range(h):19        for j in range(w):20            if grid[i][j] == "S":21                sy, sx = i, j22            elif grid[i][j] == "T":23                ty, tx = i, j24 25    # スタートとゴールにもエネルギーが0の薬があるとみなす26    for _ in range(n):27        ri, ci, ei = list(map(int, input().split()))28        ri -= 129        ci -= 130        medicines.append((ri, ci, ei))31 32    medicines.append((sy, sx, 0))33    medicines.append((ty, tx, 0))34    inf = 10**1235 36    # 各薬を頂点とするグラフをBFSで求める37    def bfs_for_grid(38        grid: List[List[Any]], h: int, w: int, sy: int = 0, sx: int = 039    ) -> List[List[int]]:40        d = deque()41        d.append((sy, sx))42        pending = inf43        dist = [[pending] * w for _ in range(h)]44        dist[sy][sx] = 0  # Initialize45        dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]46 47        while d:48            y, x = d.popleft()49 50            if dist[y][x] == pending:51                continue52 53            for dx, dy in dxy:54                nx = x + dx55                ny = y + dy56 57                if nx < 0 or nx >= w or ny < 0 or ny >= h:58                    continue59                if grid[ny][nx] == "#":60                    continue61                if dist[ny][nx] != pending:62                    continue63 64                dist[ny][nx] = dist[y][x] + 1  # Update ans65                d.append((ny, nx))66 67        return dist68 69    to = [[] for _ in range(n + 2)]70 71    for i, (ri, ci, ei) in enumerate(medicines):72        dist = bfs_for_grid(grid=grid, h=h, w=w, sy=ri, sx=ci)73 74        # 薬jまで到達できるか判定75        for j, (rj, cj, _) in enumerate(medicines):76            if i == j:77                continue78 79            if dist[rj][cj] <= ei:80                to[i].append(j)81 82    # 到達判定83    def bfs_for_graph(84        vertex_count: int, graph: List[List[int]], start_id: int85    ) -> Tuple[List[bool], List[int]]:86        d = deque([start_id])87        visited = [False] * vertex_count88        dist = [inf] * vertex_count89        dist[start_id] = 090 91        while d:92            cur = d.pop()93 94            if visited[cur]:95                continue96 97            visited[cur] = True98 99            for to in graph[cur]:100                if visited[to]:101                    continue102 103                d.append(to)104                dist[to] = min(dist[to], dist[cur] + 1)105 106        return visited, dist107 108    start_id = -2109    _, reachables = bfs_for_graph(vertex_count=n + 2, graph=to, start_id=start_id)110 111    if reachables[-1] == inf:112        print("No")113    else:114        print("Yes")115 116 117if __name__ == "__main__":118    main()119