幅優先探索の問題　atcoder D - Grid Repaintingを解く

・参考文献：
スタックとキューを極める！〜考え方と使い所を特集〜 - Qiita

・説明：幅優先探索を使ってとく。詳しくは参考文献を参照。プログラムの説明は'#'の数(kabe)とスタートを含むゴールまでの最短距離(dist[gx][gy]+1)を全体(H*W)から引いた値になる。これを素直に実装すればよい。

・実装例：

from collections import deque
H,W=map(int,input().split())
field=[]
for _ in range(H):
  field.append(list(input()))
sx=0
sy=0
gx=H-1
gy=W-1

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

#スタートからの距離がdist
dist=[[-1 for _ in range(W)] for _ in range(H)]
#print(dist)
que=deque()

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

#kabeが'#'の数
kabe=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='#':
      kabe+=1
      
#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
    if field[next_x][next_y]=='#':
      continue
        
    #未探索ならqueにいれる
    if dist[next_x][next_y]==-1:
      que.append((next_x,next_y))
      #距離の更新
      dist[next_x][next_y]=dist[x][y]+1

#ゴールにつかないと-1、ついたら'#'の数とスタートを含む最短経路の距離を足したものを全体から引く
if dist[gx][gy]==-1:
  print(-1)
else:
  print(H*W-(dist[gx][gy]+1+kabe))