Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Runtime Error

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math



s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます

H = p[0]
W = p[1]

a = []
for i in range(H):
    a.append(input())


#パディング
#グリッド入力と組み合わせる
#上と下に入れる行を作る
b = ''
for i in range(W+2):
    b += '#'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = '#' + a[i] + '#'
a.append(b)











header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))

c=[]
for i in range(H+2):
    c.append([])

for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])


#print(header)
#for i in range(len(c)):
    #print('{}{}'.format(i,''.join(c[i])))



white = 0
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '.'):
            white += 1
#print('white:{}'.format(white))



start = [1, 1]
goal = [H, W]

c[start[0]][start[1]] = 'u'


def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))


queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 0
mode = 0
answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#see_banmen()
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = 'u'
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = 'u'
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = 'u'
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = 'u'
            next_list.append([x, y-1])
        c[x][y] = 'd'
    else:
        if(len(next_list) > 0):
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                answer = step
                answer_mode = 1
                #print()
                #print('goal:step{}'.format(answer))
                #print()
            step += 1
            #see_banmen()
        elif(mode == 0):
            mode = 1
            #print()
            #print('step{}end'.format(step))
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                answer = step
                answer_mode = 1
                #print()
                #print('goal:step{}'.format(answer))
                #print()
            step += 1
            #see_banmen()
        else:
            status = False
#print(answer)

print(white - answer - 1)

Submission status: Runtime Error

Solution code:
r, c = map(int, input().split())
cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く


# 保留スタックtodoにスタートの位置情報を入れる
todo=deque([0,0])
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# 黒を数える
bcount=0
for i in range(r):
    bcount+=cc[i].count("#")

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
seen[0][0]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]

# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
    if seen[r-1][c-1]!=-1:
        break
# 面積-ゴールまでの最短手数-1(スタートのマス分)-元々あった黒のマス
print(r*c-seen[r-1][c-1]-1-bcount)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<string> vstring;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
typedef vector<vbool> vvbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(1e9+7)
#define Inf 2147483647
#define llInf 9223372036854775807
#define all(x) x.begin(),x.end()
#define pb push_back
#define isin(n,i) 0<=i&&i<n

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//セグ木・0-indexed・非再帰・(大きさ・単位元)で初期化
template<typename T>
struct SegTree {
	//比較関数の型
	using F = function<T(T, T)>;
	//二分木を配列で表したもの
	vector<T>seg;
	//木の半分の大きさ
	int siz;
	//単位元
	const T unit;
	//比較する関数
	const F f;

	//大きさn、unit(単位元)でsegtreeを初期化する
	SegTree(int n, const T unit, const F f) : unit(unit), f(f) {
		siz = 1;
		while (siz < n)siz <<= 1;
		seg.assign(siz * 2 - 1, unit);
		siz--;
	}

	//k番目にtを入力
	void set(int k, const T& t) {
		seg[k + siz] = t;
	}

	//fによって木を構築する
	void build() {
		for (int i = siz - 1; 0 <= i; i--) {
			seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]);
		}
	}

	T operator[](const int i) {
		return seg[i + siz];
	}

	//k番目をxに更新する
	void update(int k, T x) {
		k += siz;
		seg[k] = x;
		while (0 < k) {
			k = (k - 1) >> 1;
			seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}

	//[a,b)について、fした結果を返す
	//半開区域のためa以上b未満の位置を指す
	T query(int a, int b) {
		T l = unit, r = unit;
		for (a += siz, b += siz; a < b; a >>= 1, b >>= 1) {
			if (!(a & 1))l = f(seg[a++], l);
			if (!(b & 1))r = f(seg[--b], r);
		}
		return f(l, r);
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//nCrを1000000007で割った余りを求める
llint nCr(llint n, llint r) {
	llint ans = 1;
	for (llint i = 0; i < r; i++) {
		ans *= n - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= r; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, (llint)b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

bool next_combination(llint& sub, int length) {
	llint x = sub & -sub, y = sub + x;
	sub = (((sub & ~y) / x) >> 1) | y;
	return sub < (llint)(1 << (llint)length);
}

int main() {
	int h, w;
	cin >> h >> w;
	vstring s(h);
	rep(i, h)cin >> s[i];
	queue<pint>que;
	que.push({ 0,0 });
	int ans = 0;
	vvbool visited(h, vbool(w, false));
	pint plus[4] = { {0,1},{0,-1},{1,0},{-1,0} };
	while (!que.empty()) {
		ans++;
		int tmp = que.size();
		rep(i, tmp) {
			auto now = que.front(); que.pop();
			if (visited[now.first][now.second])continue;
			visited[now.first][now.second] = true;
			rep(j, 4) {
				int x = now.first + plus[j].first,
					y = now.second + plus[j].second;
				if (isin(h, x) && isin(w, y) && s[x][y] == '.')que.push({ x,y });
			}
		}
		if (visited[h - 1][w - 1])break;
	}
	ans *= -1;
	rep(i, h)rep(j, w)if (s[i][j] == '.')ans++;
	cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [[0 for i in range(W)]for j in range(H)]
ans = -1
for i in range(H):
    S = input()
    for j in range(W):
        maze[i][j] = S[j]
        if maze[i][j] == '.':
            ans += 1

q = deque()
q.append([0, 0])
maze[0][0] = 0
while len(q) != 0:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + [0, 1, 0, -1][i], y + [1, 0, -1, 0][i]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        elif maze[ny][nx] == '#':
            continue
        elif maze[ny][nx] == '.':
            maze[ny][nx] = maze[y][x] + 1
            q.append([nx, ny])
print(ans - maze[H-1][W-1])

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,-1,0,1]
def dfs(x, y, index):
    if x < 0 or H <= x or y < 0 or W <= y:
        return INF
    if MAP[x][y] == '#':
        return INF
    if x == H - 1 and y == W - 1:
        return index
    ret = INF
    MAP[x][y] = '#'
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        ret = min(ret, dfs(nx, ny, index+1))
    return ret
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
cnt += dfs(0,0,1)
ans = H * W - cnt
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W=map(int,input().split())
count=0
S=[['#']*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    S_comp=list(str(input()))
    for j in range(1,W+1):
        if S_comp[j-1]=='.':
            count+=1
        S[i][j]=S_comp[j-1]


def sur(v):  #v is tuple
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
    E=[]
    for nv in preE:
        if 1<=nv[0]<=H and 1<=nv[1]<=W:
            if S[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

q=deque()
s=(1,1)
g=(H,W)
q.append(s)
dist=[[-1]*(W+1) for k in range(H+1)]
dist[s[0]][s[1]]=0

while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]!=-1:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1
        if next==g:
            ans=dist[g[0]][g[1]]
            break
    else:
        continue
    break

print(count-1-ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc088/tasks/abc088_d
# 19:01-20:04 chudan
# 20:17-20:30 done


def main():
    H, W = map(int, input().split())

    INF = 10**10
    n_white = 0
    s = [[-1] * (W+2) for _ in range(H+2)]
    for i in range(H):
        for j, x in enumerate(input()):
            # white => 1, black => -1
            s[i+1][j+1] = INF if x == "." else -1
            n_white += 1 if x == "." else 0
    s[1][1] = 0

    fixed = set([])
    while True:
        # 最短から貪欲に伸ばして行く
        x, y = H, W  # init
        for i in range(1, H+1):
            for j in range(1, W+1):
                if s[i][j] != -1 and s[i][j] <= s[x][y] and "{}_{}".format(i, j) not in fixed:
                    x, y = i, j
                    
        fixed.add("{}_{}".format(x, y))
        
        if x == H and y == W:
            shortest = s[x][y]
            break

        if s[x][y-1] != -1:
            s[x][y-1] = min(s[x][y]+1, s[x][y-1])
            # fixed.add("{}_{}".format(x, y-1))
        if s[x][y+1] != -1:
            s[x][y+1] = min(s[x][y]+1, s[x][y+1])
            # fixed.add("{}_{}".format(x, y+1))
        if s[x-1][y] != -1:
            s[x-1][y] = min(s[x][y]+1, s[x-1][y])
            # fixed.add("{}_{}".format(x-1, y))
        if s[x+1][y] != -1:
            s[x+1][y] = min(s[x][y]+1, s[x+1][y])
            # fixed.add("{}_{}".format(x+1, y))
    
    return n_white - (shortest + 1) if shortest < H*W else


print(main())

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        if len(candidates)==0:
            return -1
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    if len(candidates)==0:
        return -1
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
#            if data[new_pos[0]][new_pos[1]]!="#":
            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()
print(data)

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
#            if data[new_pos[0]][new_pos[1]]!="#":
            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            try:
                if data[new_pos[0]][new_pos[1]]!="#":
                    candidates.append(new_pos)
            except:
                continue
                
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            try:
                if data[new_pos[0]][new_pos[1]]!="#":
                    candidates.append(new_pos)
                
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]!="#":
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
print(check_number(data)-result-1)