ABC308Dを解いた【BFS】

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

ABC308のD問題を解いていく

実装コード

gridBFSの条件に、マスの文字が次の文字に対応したものかチェックする条件を付加すればOK

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)


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

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

def bfs(i, j, h, w, grid):
    q = deque([(i, j)])
    visited = [[False] * w for _ in range(h)]
    visited[i][j] = True
    
    while q:
        y, x = q.popleft()
        s = grid[y][x]
        if s not in T:
            continue
        for di in range(4):
            ny, nx = y + dy[di], x + dx[di]
            if not out_of_bounds(ny, nx, h, w) and grid[ny][nx] == T[s] and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx))

    return visited

T = {s:t for s,t in zip("snuke","nukes")}
def main():
    H, W = rLI()
    S = [list(rS()) for _ in range(H)]
    
    visited = bfs(0,0,H,W,S)
    
    ans = visited[-1][-1]
    print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

感想

シンプルなBFSはスニペット化したのでとりあえずできるようになってきた

snukeを1文字ローテーションしたらnukesになったのは笑った。