Problem p03436 (python)

Fixed submission:
'''


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False


## input
h,w = map(int, input().split())

M = [list(input().rstrip()) for _ in range(h)]

## ステータス管理2次元配列
# 訪問状態をWHITE, GRAY, BLACKのいずれかで表す
M_color = [['WHITE']*w for _ in range(h)]

## 距離
# 初期値は-1（到達不能）を入れ、到達できたら実際の距離を代入する
M_distance = [[-1]*w for _ in range(h)]

route_str = '.'
# start, goal設定
sy=0
sx=0
gy=h-1
gx=w-1

def breadth_first_search():
    """

    """
    # 開始頂点sのステータスを探索中へ変更、距離は0を代入
    M_color[sy][sx] = 'GRAY'
    M_distance[sy][sx] = 0
    # キューを初期化し、開始頂点をキューへ代入
    q = deque()
    q.append([sy,sx])

    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]

    # qが空になるまでwhileループ処理
    while len(q) > 0:
        # 探索する頂点を取り出し
        y, x = q.popleft()

        # ゴールに辿り着いたら距離をreturn
        if x == gx and y == gy:
            return M_distance[y][x]

        ## uに隣接する全ての頂点について、未探索の場合は探索
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # r,cの範囲に収まっていなければスキップ
            if after_x < 0 or after_x > w-1 or after_y < 0 or after_y > h-1:
                continue
            
            # 移動先が陸かつ未探索なら
            if M[after_y][after_x] == route_str and M_color[after_y][after_x] == 'WHITE':
                M_color[after_y][after_x] = 'GRAY'
                # 距離は、現在キューにある頂点u + 1となる（隣接しているので）
                M_distance[after_y][after_x] = M_distance[y][x] + 1
                # キューに追加
                q.append([after_y,after_x]) # キューに追加
                            
            M_color[y][x] = 'BLACK'
    
    # goalへたどり着けない場合
    return -1


def main():
    '''メイン処理'''
    g_distance = breadth_first_search()
    # 塗りつぶせる'.'の数 = 全ての'.'の数 - ゴールまでの距離 - 1(スタート地点の.)
    if is_debug:
        print(g_distance)
    
    if g_distance == -1:
        print(-1)
    else:
        # 2次元配列Mの中の、.の数をカウント
        all_dot = len([s for s in list(itertools.chain.from_iterable(M)) if '.' in s])
        ans = all_dot - g_distance -1
        print(ans)
    
    
if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Buggy submission (verdict: Runtime Error):
'''


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False


## input
h,w = map(int, input().split())

M = [list(input().rstrip()) for _ in range(h)]

## ステータス管理2次元配列
# 訪問状態をWHITE, GRAY, BLACKのいずれかで表す
M_color = [['WHITE']*w for _ in range(h)]

## 距離
# 初期値は-1（到達不能）を入れ、到達できたら実際の距離を代入する
M_distance = [[-1]*w for _ in range(h)]

route_str = '.'
# start, goal設定
sy=0
sx=0
gy=h-1
gx=w-1

def breadth_first_search():
    """

    """
    # 開始頂点sのステータスを探索中へ変更、距離は0を代入
    M_color[sy][sx] = 'GRAY'
    M_distance[sy][sx] = 0
    # キューを初期化し、開始頂点をキューへ代入
    q = deque()
    q.append([sy,sx])

    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]

    # qが空になるまでwhileループ処理
    while len(q) > 0:
        # 探索する頂点を取り出し
        y, x = q.popleft()

        # ゴールに辿り着いたら距離をreturn
        if x == gx and y == gy:
            return M_distance[y][x]

        ## uに隣接する全ての頂点について、未探索の場合は探索
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # r,cの範囲に収まっていなければスキップ
            if after_x < 0 or after_x > w-1 or after_y < 0 or after_y > h-1:
                continue
            
            # 移動先が陸かつ未探索なら
            if M[after_y][after_x] == route_str and M_color[after_y][after_x] == 'WHITE':
                M_color[after_y][after_x] = 'GRAY'
                # 距離は、現在キューにある頂点u + 1となる（隣接しているので）
                M_distance[after_y][after_x] = M_distance[y][x] + 1
                # キューに追加
                q.append([after_y,after_x]) # キューに追加
                            
            M_color[y][x] = 'BLACK'


def main():
    '''メイン処理'''
    g_distance = breadth_first_search()
    # 塗りつぶせる'.'の数 = 全ての'.'の数 - ゴールまでの距離 - 1(スタート地点の.)
    if is_debug:
        print(g_distance)
    
    # 2次元配列Mの中の、.の数をカウント
    all_dot = len([s for s in list(itertools.chain.from_iterable(M)) if '.' in s])
    ans = all_dot - g_distance -1
    print(ans)
    
    


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()