atcoder ABC317 E - Avoid Eye Contactの勉強

DFS,BFS atcoder

atcoder.jp

・参考
Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)

・説明
　参考記事をPythonで実装した。
　注意点としてBFSのcontinueする条件は　s[nx][ny]!='.'　とすると　s[nx][ny]='G'(ゴール)　のときをスルーしてしまうので一生ゴールにつかなくなる。

from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]

#スタート、ゴールの位置を求める。
for i in range(h):
  for j in range(w):
    if s[i][j]=='S':
      sx=i
      sy=j
    if s[i][j]=='G':
      gx=i
      gy=j
      
dx=[1,0,-1,0]
dy=[0,1,0,-1]
direction='v>^<'  #vがdx,dy=1,0に対応、他も上のdx,dyに対応する。

#視界に入っていいるマスをviewed[i][j]=1にする。
viewed=[[0 for _ in range(w)]for _ in range(h)]
for i in range(h):
  for j in range(w):
    for k in range(4):
      #s[i][j]にいる人がk番目の人でないときはスルー。
      if s[i][j]!=direction[k]:
        continue
      
      #視界に入っているマスを求める。
      x, y=i, j
      while 1:  #breakまで無限ループ。
        x+=dx[k]
        y+=dy[k]
        if x<0 or x>=h or y<0 or y>=w:  #場外はbreak。
          break
        if s[x][y]!='.':  #壁や人がいるときbreak。
          break
        viewed[x][y]=1  



#BFS
#スタートからの距離がdist
dist=[[-1 for _ in range(w)] for _ in range(h)]
#print(dist)

#スタートはdist=0、queにスタートを追加
dist[sx][sy]=0
que=deque()
que.append((sx,sy))
#print(que)

#queがからになるまでやる
while len(que)!=0:
  x,y=que.popleft()  #queの先頭のペアを取り出す
  for k in range(4):
    nx=x+dx[k]
    ny=y+dy[k]
    if nx<0 or nx>=h or ny<0 or ny>=w:  #場外はスルー。
      continue
    
    #壁、人のときはスルーして、'G'と'.'のときはスルーしない。s[nx][ny]!='.'とすると'G'のときはスルーしてしまう。
    if s[nx][ny]=='#':  #壁のときもスルー。
      continue 
    if s[nx][ny]=='v' or s[nx][ny]=='^' or s[nx][ny]=='<' or s[nx][ny]=='>':  #人のときもスルー。
      continue 
    
    if viewed[nx][ny]:  #視界に入っていたらダメ
      continue 
    if dist[nx][ny]==-1: #未探索のとき、距離を更新して追加。
      dist[nx][ny]=dist[x][y]+1
      que.append((nx,ny))

print(dist[gx][gy] if dist[gx][gy]!=-1 else -1)  #ゴールにたどり着けたら(dist[gx][gy]!=-1)dist[gx][gy]を出力、たどり着けなかったら-1を出力する。