ABC317 E — Avoid Eye Contact

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    a = [list(input().rstrip()) for _ in range(h)]13 14    # 人の視線に入る部分をチェック15    # 共通部分をまとめる16    dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]17    dxy = dxy[:4]18    dirs = ["<", ">", "^", "v"]19    eye = "!"20 21    for (dx, dy), dir in zip(dxy, dirs):22        for i in range(h):23            for j in range(w):24                if a[i][j] != dir:25                    continue26 27                ny, nx = i, j28 29                while True:30                    ny += dy31                    nx += dx32 33                    if nx < 0 or nx >= w or ny < 0 or ny >= h:34                        break35                    if not (a[ny][nx] == "." or a[ny][nx] == eye):36                        break37 38                    a[ny][nx] = eye39 40    # 始点・終点の位置を調べる41    sy, sx, gy, gx = -1, -1, -1, -142 43    for i in range(h):44        for j in range(w):45            if a[i][j] == "S":46                sy, sx = i, j47            elif a[i][j] == "G":48                gy, gx = i, j49 50    # BFSで始点から終点まで移動51    blocked = [">", "v", "<", "^", "#", "!"]52 53    def bfs_for_grid(54        grid: List[List[Any]], h: int, w: int, sy: int = 0, sx: int = 055    ) -> Tuple[List[List[bool]], List[List[int]]]:56        d = deque()57        d.append((sy, sx))58        visited = [[False] * w for _ in range(h)]59        pending = -160        dist = [[pending] * w for _ in range(h)]61        dist[sy][sx] = 0  # Initialize62        dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]63 64        while d:65            y, x = d.popleft()66 67            if dist[y][x] == pending:68                continue69 70            if visited[y][x]:71                continue72 73            visited[y][x] = True74 75            for dx, dy in dxy:76                nx = x + dx77                ny = y + dy78 79                if nx < 0 or nx >= w or ny < 0 or ny >= h:80                    continue81                if visited[ny][nx]:82                    continue83                if grid[ny][nx] in blocked:84                    continue85                if dist[ny][nx] != pending and dist[ny][nx] <= dist[y][x]:86                    continue87 88                dist[ny][nx] = dist[y][x] + 1  # Update ans89                d.append((ny, nx))90 91        return visited, dist92 93    visited, dist = bfs_for_grid(grid=a, h=h, w=w, sy=sy, sx=sx)94 95    print(dist[gy][gx])96 97 98if __name__ == "__main__":99    main()100