ABC387Dを解いた【BFS】

筆者はレート800前後の茶～緑コーダ

ABC387のD問題を解いていく

実装コード

進んだ方向（0: 縦、1: 横）をBFSのキューに持たせ、
直前に進んだ方向と異なる場合のみ遷移できるようにする。

開始点については、縦・横のどちらにも進めるように初期化する。

main.py

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)

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)
    
    dy = [-1, 0, 1, 0]
    dx = [ 0, 1, 0, -1]
    dd = [ 0, 1, 0, 1]
    
    def out_of_bounds(y, x, h, w):
        return y < 0 or y >= h or x < 0 or x >= w
    i,j = S
    q = deque()
    dist = [[[float('inf'),float('inf')] for i in range(W)] for _ in range(H)]
    visited = [[[False, False] for _ in range(W)] for _ in range(H)]
    for k in range(2):
        dist[i][j][k] = 0
        visited[i][j][k] = True
        q.append((i,j,k))
    
    while q:
        y, x, d = q.popleft()
        # err(y, x, d)
        for di in range(4):
            ny, nx, nd = y + dy[di], x + dx[di], dd[di]
            if nd != d and not out_of_bounds(ny, nx, H, W) and grid[ny][nx] != "#" and not visited[ny][nx][nd]:
                dist[ny][nx][nd] = dist[y][x][d] + 1
                visited[ny][nx][nd] = True
                q.append((ny, nx, nd))
                # err(" ", ny, nx, nd)
    
    # for k in range(2):
    #     for i in range(H):
    #         x = ""
    #         for j in range(W):
    #             b = dist[i][j][k]
    #             x += "X" if b == float('inf') else str(b) if b < 10 else chr(ord("a") + ((b-10)%26))
    #         err(x)
    #     err("")

    i,j = G

    print(min(dist[i][j]) if any(visited[i][j]) else -1)
    
if __name__ == '__main__':
    main()

感想

今年の始め頃に行われたコンテストの問題だが、
当時はBFSの理解が浅く、解くのを諦めてしまっていた。

今回あらためて挑戦してみたところ、
特に詰まることなく実装できた。

この1年で、少しずつではあるが
確実に力がついてきていることを実感できた。