提出 #61394747

---

ソースコード 拡げる

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

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

def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w

def main():
    H, W = rLI()
    S = G = (-1,-1)
    
    grid = [[] for _ in range(H)]
    
    for i in range(H):
        s = list(rS())
        grid[i] = s
        for j,c in enumerate(s):
            if c == "S":
                S = (i,j)
            if c == "G":
                G = (i,j)
    si,sj = S
    gi,gj = G
    # err(S,G)
    q = deque()
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    dist[si][sj] = 0
    visited[si][sj] = True
    for di in range(4):
        ny, nx = si + dy[di], sj + dx[di]
        if dy[di] == 0:
            r = "H"
        else:
            r = "V"
        if not out_of_bounds(ny, nx, H, W) and grid[ny][nx] in ".G":
            q.append((ny, nx, 1, r))
            dist[ny][nx] = 1
            visited[ny][nx] = True
    # err(q)
    while q:
        y, x, d, br = q.popleft()
        # err("--",y, x, d, br)
        for di in range(2):
            if br == "H":
                ny, nx = y + dr[di], x
                r = "V"
            if br == "V":
                ny, nx = y, x + dr[di]
                r = "H"
            if not out_of_bounds(ny, nx, H, W) and grid[ny][nx] in ".G":
                # err(r, ny,nx,H,grid[ny][nx],dist[ny][nx],visited[ny][nx])
                if dist[ny][nx]==-1: 
                    # err(f"dist[{ny}][{nx}] = {d + 1}")
                    dist[ny][nx] = d + 1
                elif dist[ny][nx]>(d+1):
                    # err(f"dist[{ny}][{nx}] = {d + 1}")
                    dist[ny][nx] = d + 1
                else:
                    continue
                item0 = (ny+1, nx+1, d + 1, r)
                # err(item0)
                item = (ny, nx, d + 1, r)
                q.append(item)
                visited[ny][nx] = True

    print(dist[gi][gj])
    
if __name__ == '__main__':
    main()

提出情報

ジャッジ結果