atcoder arc C - 器物損壊！高橋君の勉強

・参考：
Submission #16162979 - AtCoder Regular Contest 005
AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録

・ダイクストラ法：
グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube

・0-1BFSを使う。壁の有無で0，1を重さとしてBFSするものをいう。ダイクストラ法の重さが0，1になったもので、0のときはdequeの左から入れて1のときは右から入れる。こうすると0の壁がないルートを優先的に選んで進む（popleftは左から取ってくるので）。

・やり方：
Submission #16162979 - AtCoder Regular Contest 005のやり方を参考にする。s(スタート）からg（ゴール）までBFSをする。distに壁を壊した回数を入れて(無限大で初期化)、移動した座標が'#'なら前の座標+1する(プログラムのd=dist[x][y]+wallの部分)。最終的にdist[gx][gy]が2以下ならOK。

・注意点："Yes","No"ではなく"YES","NO"と出力することを忘れずに。

ここからは参考の記事の2つのやり方をやってみる。まずSubmission #16162979 - AtCoder Regular Contest 005の場合

from collections import deque
H,W=map(int,input().split())
field=[input() for _ in range(H)]

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


#スタートの座標とゴールの座標の特定。
for i in range(H):
  for j in range(W):
    if field[i][j]=='s':
      sx=i
      sy=j
    if field[i][j]=='g':
      gx=i
      gy=j
    

#壁を壊した回数がdist。大きい値で初期化
dist=[[10**18 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 i in range(4):
    next_x=x+dx[i]
    next_y=y+dy[i]
    
    #場外はスルー
    if next_x<0 or next_x>=H or next_y<0 or next_y>=W:
      continue
    
        
    wall=(field[next_x][next_y]=='#')  #field[next_x][next_y]=='#'なら1、違ったら0
    d=dist[x][y]+wall   #壁があったら前の座標足す1。
 
    #distが更新できるならdにする。
    if d<dist[next_x][next_y]:  
      dist[next_x][next_y]=d

      #壁があったらqueの後ろから足す、なかったら前からいれる
      if wall:
        que.append((next_x,next_y))
      else:
        que.appendleft((next_x,next_y))
      
print("YES" if dist[gx][gy]<=2 else "NO")

次にAtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録

from collections import deque
H,W=map(int,input().split())
field=[input() for _ in range(H)]

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


#スタートの座標とゴールの座標の特定。
for i in range(H):
  for j in range(W):
    if field[i][j]=='s':
      sx=i
      sy=j
    if field[i][j]=='g':
      gx=i
      gy=j
    

#壁を壊した回数がdist。大きい値で初期化
dist=[[10**18 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 i in range(4):
    next_x=x+dx[i]
    next_y=y+dy[i]
    
    #場外はスルー
    if next_x<0 or next_x>=H or next_y<0 or next_y>=W:
      continue
    
    #壁があって、前の座標のdist+1(壁のぶん+1する)のほうが次のよりも小さいとqueの後ろからいれる
    if field[next_x][next_y]=='#':
      if dist[next_x][next_y]>dist[x][y]+1:
        dist[next_x][next_y]=dist[x][y]+1
        que.append((next_x,next_y))

    #壁がないとき、queの前から。     
    else:
      if dist[next_x][next_y]>dist[x][y]:
        dist[next_x][next_y]=dist[x][y]
        que.appendleft((next_x,next_y))
      
print("YES" if dist[gx][gy]<=2 else "NO")