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:
from queue import Queue

def bfs(H, W, s):
    inf = 10 ** 20
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

    while not q.empty():
        p = q.get()
        x = p[0]
        y = p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.put([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == INF):
    print("-1")
else:
    print(wnum - d)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]  # 迷路
D = [[-1] * W for i in range(W)]  # 最短距離
D[0][0] = 0

Black = 0  # 最初の盤面の黒の数
for g in G:
    Black += g.count('#')

# BFS
que = deque([[0, 0]])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not 0 <= nh + dh < H:
            continue
        
        if not 0 <= nw + dw < W:
            continue
            
        if D[nh + dh][nw + dw] > 0:
            continue

        if G[nh + dh][nw + dw] == '#':
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        que.appendleft([nh + dh, nw + dw])

if D[H - 1][W - 1]:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]  # 迷路
D = [[-1] * W for i in range(W)]  # 最短距離
D[0][0] = 0

Black = 0  # 最初の盤面の黒の数
for g in G:
    Black += g.count('#')

# BFS
que = deque([[0, 0]])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] > 0:
            continue

        if G[nh + dh][nw + dw] == '#':
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        que.appendleft([nh + dh, nw + dw])

if D[H - 1][W - 1]:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]  # 迷路
D = [[None] * W for i in range(W)]  # 最短距離
D[0][0] = 0

Black = 0  # 最初の盤面の黒の数
for g in G:
    Black += g.count('#')

# BFS
que = deque([[0, 0]])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] is not None:
            continue

        if G[nh + dh][nw + dw] == '#':
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        que.appendleft([nh + dh, nw + dw])

if D[H - 1][W - 1]:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int, input().split())

start, goal = (1, 1), (H, W)
# 左右上下
directions = [[0,-1],[0,1],[-1,0],[1,0]]
# 四方に一回り大きいフィールドを作る
field = [['*'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        field[i][j] = row[j-1]

# 移動距離メモ
memo = [[float('inf')] * (W+2) for i in range(H+2)]
memo[start[0]][start[1]] = 0
# 訪問済メモ
visited = [[0] * (W+2) for i in range(H+2)]
# 移動元メモ
prevs = [[None] * (W+2) for i in range(H+2)]

def bfs():
    que = deque()
    # スタート位置
    que.append(start)
    while len(que) != 0:
        cur = que.popleft()
        # 見終わった場所はもうやらない
        if visited[cur[0]][cur[1]] == 1:
            continue
        # 訪問済にする
        visited[cur[0]][cur[1]] = 1
        # 4方向見る
        for direction in directions:
            # 上下左右に1つずつ動かした座標
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁か黒マスはスキップ
            if field[nxt[0]][nxt[1]] == '*' or field[nxt[0]][nxt[1]] == '#':
                continue
            # 現在位置+1の距離を移動先に記録
            if field[nxt[0]][nxt[1]] == '.' and memo[nxt[0]][nxt[1]] > memo[cur[0]][cur[1]] + 1:
                memo[nxt[0]][nxt[1]] = memo[cur[0]][cur[1]] + 1
                # ここで移動元のマスを記録
                prevs[nxt[0]][nxt[1]] = (cur[0], cur[1])
                # キューに次のマスを足す
                que.append(nxt)

# 最短経路を出す
bfs()
# 最短経路で使うマスに目印をつける
field[goal[0]][goal[1]] = '@'
nxt = prevs[goal[0]][goal[1]]
for _ in range(memo[goal[0]][goal[1]]):
    field[nxt[0]][nxt[1]] = '@'
    nxt = prevs[nxt[0]][nxt[1]]
# 残っている白マスが塗り替えられる場所
ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if field[i][j] == '.':
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

from collections import deque

H, W = map(int, input().split())

start,goal = (1, 1), (H, W)
# 左右上下
directions = [[0,-1],[0,1],[-1,0],[1,0]]
# 四方に一回り大きいフィールドを作る
field = [['*'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())[:-1]
    for j in range(1, W+1):
        field[i][j] = row[j-1]

# 移動距離メモ
memo = [[float('inf')] * (W+2) for i in range(H+2)]
memo[start[0]][start[1]] = 0
# 訪問済メモ
visited = [[0] * (W+2) for i in range(H+2)]
# 移動元メモ
prevs = [[None] * (W+2) for i in range(H+2)]


def bfs():
    que = deque()
    # スタート位置
    que.append(start)
    while len(que) != 0:
        cur = que.popleft()
        # 見終わった場所はもうやらない
        if visited[cur[0]][cur[1]] == 1:
            continue
        # 訪問済にする
        visited[cur[0]][cur[1]] = 1
        # 4方向見る
        for direction in directions:
            # 上下左右に1つずつ動かした座標
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁か黒マスはスキップ
            if field[nxt[0]][nxt[1]] == '*' or field[nxt[0]][nxt[1]] == '#':
                continue
            # 現在位置+1の距離を移動先に記録
            if field[nxt[0]][nxt[1]] == '.' and memo[nxt[0]][nxt[1]] > memo[cur[0]][cur[1]] + 1:
                memo[nxt[0]][nxt[1]] = memo[cur[0]][cur[1]] + 1
                # ここで移動元のマスを記録
                prevs[nxt[0]][nxt[1]] = (cur[0], cur[1])
                # キューに次のマスを足す
                que.append(nxt)

# 最短経路を出す
bfs()
# 最短経路で使うマスに目印をつける
field[goal[0]][goal[1]] = '@'
nxt = prevs[goal[0]][goal[1]]
for _ in range(memo[goal[0]][goal[1]]):
    field[nxt[0]][nxt[1]] = '@'
    nxt = prevs[nxt[0]][nxt[1]]
# 残っている白マスが塗り替えられる場所
ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if field[i][j] == '.':
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def calc_min_root(start_x, start_y, goal_x, goal_y):
    global maze
    X = [0, 0, 1, -1]
    Y = [1, -1, 0, 0]
    visited = [[None] * (goal_y+1) for _ in range(goal_x+1)]
    visited[start_x][start_y] = 1
    q_row = deque()
    q_column = deque()
    q_row.append(start_x)
    q_column.append(start_y)
    while q_row:
        row = q_row.popleft()
        column = q_column.popleft()
        for dx, dy in zip(X, Y):
            new_row = row + dx
            new_column = column + dy
            if 0 <= new_row <= goal_x and 0 <= new_column <= goal_y:
                if visited[new_row][new_column] == None and maze[new_row][new_column] == '.':
                    visited[new_row][new_column] = visited[row][column] + 1
                    q_row.append(new_row)
                    q_column.append(new_column)
    return visited[goal_x][goal_y]

if __name__ == "__main__":
    row, column = map(int, input().split())
    maze = []
    for _ in range(row):
        one_row = list(input())
        maze.append(one_row)
    count_sharp = 0
    for one_row in maze:
        count_sharp += one_row.count('#')
    
    count_min_root_cost = calc_min_root(0, 0, row-1, column-1)
    
    print(row * column - count_min_root_cost - count_sharp)

Submission status: Runtime Error

Solution code:
def main():
	H, W = map(int, input().split())
	S = [list(input()) for _ in range(H)]

	D = [[0]*H for j in range(W)]

	D[0][0] = 1
	L = [(0,0)]

	for k in range(2,H*W):
		L_next = []
		for l in L:
			w = l[0]
			h = l[1]
			#上
			if (0 < h):
				if ((0 == D[h-1][w]) and ('.'==S[h-1][w])):
					D[h-1][w] = k
					L_next.append((w,h-1))
			#左
			if (0 < w):
				if ((0 == D[h][w-1]) and ('.'==S[h][w-1])):
					D[h][w-1] = k
					L_next.append((w-1,h))
			#下
			if (h < (H - 1)):
				if ((0 == D[h+1][w]) and ('.'==S[h+1][w])):
					D[h+1][w] = k
					L_next.append((w,h+1))
			#右
			if (w < (W - 1)):
				if ((0 == D[h][w+1]) and ('.'==S[h][w+1])):
					D[h][w+1] = k
					L_next.append((w+1,h))
		L = L_next
		if (0 != D[H-1][W-1]):
			break
		if (not L):	#リストが空
			return -1

	return W*H - D[H-1][W-1] - 2

print(main())

Submission status: Runtime Error

Solution code:
H, W = ( int(i) for i in input().split() )
S = [input() for i in range(H)]

cc = 0
for ss in S:
    for st in ss:
        if st == ".":
            cc += 1

for i in range(len(S)):
    S[i] = "#" + S[i] + "#"

temp = ["#" * (W + 2)]
S = temp + S + temp

dd = [[float("inf")] * W for i in range(H)]

def DFS(a, b, d):
    dd[a-1][b-1] = d
    for x, y in [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]:
        if S[x][y] == "#":
            continue
        else:
            if dd[x-1][y-1] > d + 1:
                DFS(x, y, d + 1)

DFS(1,1,0)

print(cc - dd[H-1][W-1] -1)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
L=[]
l=["#"]*(W+2)
L.append(l)
cnt=0
for i in range(H):
    s=input()
    s="#"+s+"#"
    l=[]
    for j in range(W+2):
        l.append(s[j])
        if s[j]==".":
            cnt+=1
    L.append(l)
l=["#"]*(W+2)
L.append(l)
#print(L)
D=deque([[1,1,1]])
for x in range(1000000):
    if D==[]:
        print("-1")
    elif H==D[0][0] and W==D[0][1]:
        print(cnt-D[0][2])
        exit()
    else:
        if L[D[0][0]+1][D[0][1]]==".":
            D.append([D[0][0]+1,D[0][1],D[0][2]+1])
        if L[D[0][0]][D[0][1]+1]==".":
            D.append([D[0][0],D[0][1]+1,D[0][2]+1])
        if L[D[0][0]-1][D[0][1]]==".":
            D.append([D[0][0]-1,D[0][1],D[0][2]+1])
        if L[D[0][0]][D[0][1]-1]==".":
            D.append([D[0][0],D[0][1]-1,D[0][2]+1])
        L[D[0][0]][D[0][1]]="#"
        D.popleft()

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
L=[]
l=["#"]*(W+2)
L.append(l)
cnt=0
for i in range(H):
    s=input()
    s="#"+s+"#"
    l=[]
    for j in range(W+2):
        l.append(s[j])
        if s[j]==".":
            cnt+=1
    L.append(l)
l=["#"]*(W+2)
L.append(l)
#print(L)
D=deque([[1,1,1]])
for x in range(1000000):
    if H==D[0][0] and W==D[0][1]:
        print(cnt-D[0][2])
        exit()
    else:
        if L[D[0][0]+1][D[0][1]]==".":
            D.append([D[0][0]+1,D[0][1],D[0][2]+1])
        if L[D[0][0]][D[0][1]+1]==".":
            D.append([D[0][0],D[0][1]+1,D[0][2]+1])
        if L[D[0][0]-1][D[0][1]]==".":
            D.append([D[0][0]-1,D[0][1],D[0][2]+1])
        if L[D[0][0]][D[0][1]-1]==".":
            D.append([D[0][0],D[0][1]-1,D[0][2]+1])
        L[D[0][0]][D[0][1]]="#"
        D.popleft()

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import chain

ADS = [(0, 1), (1, 0), (-1, 0), (0, -1)]

h, w = map(int, input().split(" "))
s = [list(input()) for _ in range(h)]

l = [[None for _ in range(w)] for _ in range(h)]
l[0][0] = 0

q = deque([(0, 0)])
while q:
	this_x, this_y = q.popleft()
	this_num = l[this_y][this_x]
	if (this_x, this_y) == (w-1, h-1):
		break

	for ad_x, ad_y in ADS:
		x, y = this_x+ad_x, this_y+ad_y
		if not (0 <= x < w and 0 <= y < h):
			continue
		
		square = s[y][x]
		if square == "#":
			continue

		num = l[y][x]
		if num != None:
			continue
		l[y][x] = this_num + 1

		q.append((x, y))

print(sum(s_i.count(".") for s_i in s) - l[h-1][w-1] - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import chain

ADS = [(0, 1), (1, 0), (-1, 0), (0, -1)]

h, w = map(int, input().split(" "))
s = [list(input()) for _ in range(h)]

l = [[None for _ in range(w)] for _ in range(h)]
l[0][0] = 0

q = deque([(0, 0)])
while q:
	this_x, this_y = q.popleft()
	this_num = l[this_y][this_x]
	if (this_x, this_y) == (w, h):
		break

	for ad_x, ad_y in ADS:
		x, y = this_x+ad_x, this_y+ad_y
		if not (0 <= x < w and 0 <= y < h):
			continue
		
		square = s[y][x]
		if square == "#":
			continue

		num = l[y][x]
		if num != None:
			continue
		l[y][x] = this_num + 1

		q.append((x, y))

print(sum(s_i.count(".") for s_i in s) - l[h-1][w-1] - 1)

Submission status: Runtime Error

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = []
count_dot = 0
for _ in range(H):
    s = input()
    count_dot += s.count('.')
    S += [list(s)]


def parse(i, j):
    for x, y in ([i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]):
        if x < 0 or H <= x or y < 0 or W <= y:
            continue
        elif S[x][y] == '.':
            S[x][y] = S[i][j] + 1
            parse(x, y)


S[0][0] = 1
parse(0, 0)
print(count_dot - S[-1][-1])

Submission status: Runtime Error

Solution code:
import sys

c = list(list(map(int,input().split())) for _ in range(3))
row = [0, (c[1][0] - c[0][0]), (c[2][0] - c[0][0])]
line = [0, (c[0][1] - c[0][0]), (c[0][2] - c[0][0])]

for i in range(3):
    c[i][0] - row[0]
    if max(c[i][0] - line[0], c[i][1] - line[1], c[i][2] - line[2]) != min(c[i][0] - line[0], c[i][1] - line[1], c[i][2] - line[2]):
        print("No")
        sys.exit()
    elif max(c[0][i] - row[0], c[1][i] - row[1], c[2][i] - row[2]) != min(c[0][i] - row[0], c[1][i] - row[1], c[2][i] - row[2]):
        print("No")
        sys.exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
L=[]
cnt=0
for i in range(H+2):
    if i==0 or i==H+1:
        S="#"*(W+2)
    else:
        S=input()
        S="#"+S+"#"
    L1=[]
    for j in range(W+2):
        if S[j]==".":
            cnt+=1
        L1.append(S[j])
    L.append(L1)
L[1][1]=0
D=deque()
D.append([1,1])
h=[0,1,0,-1]
w=[1,0,-1,0]
i=0
for i in range(10000):
    #print(D)
    #print(L)
    if D==[]:
        print(-1)
    elif D[0][0]==H and D[0][1]==W:
        print(cnt-L[H][W]-1)
        exit()
    for k in range(3):
        if L[D[0][0]+h[k]][D[0][1]+w[k]]==".":
            if [D[0][0]+h[k],D[0][1]+w[k]] not in D:
                D.append([D[0][0]+h[k],D[0][1]+w[k]])
            L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
            
        elif L[D[0][0]+h[k]][D[0][1]+w[k]]=="#":
            pass
        else:
            if L[D[0][0]+h[k]][D[0][1]+w[k]]>L[D[0][0]][D[0][1]]+1:
                L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
    D.popleft()

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
L=[]
cnt=0
for i in range(H+2):
    if i==0 or i==H+1:
        S="#"*(W+2)
    else:
        S=input()
        S="#"+S+"#"
    L1=[]
    for j in range(W+2):
        if S[j]==".":
            cnt+=1
        L1.append(S[j])
    L.append(L1)
L[1][1]=0
D=deque()
D.append([1,1])
h=[0,1,0,-1]
w=[1,0,-1,0]
i=0
for i in range(10000):
    #print(D)
    #print(L)
    if D[0][0]==H and D[0][1]==W:
        print(cnt-L[H][W]-1)
        exit()
    for k in range(3):
        if L[D[0][0]+h[k]][D[0][1]+w[k]]==".":
            if [D[0][0]+h[k],D[0][1]+w[k]] not in D:
                D.append([D[0][0]+h[k],D[0][1]+w[k]])
            L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
            
        elif L[D[0][0]+h[k]][D[0][1]+w[k]]=="#":
            pass
        else:
            if L[D[0][0]+h[k]][D[0][1]+w[k]]>L[D[0][0]][D[0][1]]+1:
                L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
    D.popleft()

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W, D = inpl()
S = dict([])
for i in range(H):
    a = inpl()
    for j in range(W):
        S[a[j]] = [i,j]

dist = [[0] for i in range(D+1) ]
for i in range(1,D+1):
    for j in range(1,1+(H*W-i)//D):
        dist[i].append(dist[i][-1] +\
        (abs(S[i+j*D][0]-S[i+(j-1)*D][0])+abs(S[i+j*D][1]-S[i+(j-1)*D][1])))
Q = int(input())
ans = []
for i in range(Q):
    l, r = inpl()
    mod = l % D
    if mod == 0 : mod = D
    l, r = (l-mod)//D, (r-mod)//D
    ans.append(dist[mod][r]-dist[mod][l])
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]

black = 0
for g in G:
    black += g.count("#")


que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if nh == H - 1 & nw == W - 1:
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == ".":
                que.appendleft((nh + dh, nw + dw, cost + 1))

print(H * W - black - int(G[H - 1][W - 1]) - 1)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
MAP=[list(input()) for i in range(H)]


ANS=0
for i in range(H):
    ANS+=MAP[i].count(".")

from collections import deque

QUE = deque()
QUE.append((0,0))
MAP[0][0]=0

while QUE:
    (x,y)=QUE.pop()

    for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if i<0 or j<0 or i>=H or j>=W:
            continue
        if MAP[i][j]==".":
            MAP[i][j]=MAP[x][y]+1
            QUE.appendleft((i,j))
            
        
if MAP[i][j]==".":
    print(-1)
else:
    print(ANS-MAP[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(grid: list):
    h = len(grid)
    w = len(grid[0])
    
    dhs = [0, 1, 0, -1]
    dws = [1, 0, -1, 0]
    
    que = deque([(1,(0,0))])
    grid[0][0] = "1"
    
    while que:
        cost, (hcur, wcur) = que.popleft()
    
        for dh, dw in zip(dhs, dws):
            if 0 <= hcur+dh < h and 0 <= wcur+dw < w and grid[hcur+dh][wcur+dw] == ".":
                nex_cost = cost + 1
                grid[hcur+dh][wcur+dw] = str(nex_cost)
                que.append((nex_cost, (hcur+dh, wcur+dw)))
    

h,w = li()

grid = []
for _ in range(h):
    grid.append(lc())

whites = 0
for row in grid:
    whites += row.count(".")

bfs(grid)

print(whites - int(grid[-1][-1]))

Submission status: Runtime Error

Solution code:
#全部#の数を数える
#最小のルートを探し、そのルートで使ったますを数える（見つかんなかったら-1
#マスの数-最小のルートで使った歩数-最初に数えた#の数が答え
h,w= map(int,input().split())
arr = [input() for i in range(h)]
routed =  [[False for i in range(w)] for j in range(h)]
"""
arr=['.....................................',
 '...#...####...####..###...###...###..',
 '..#.#..#...#.##....#...#.#...#.#...#.',
 '..#.#..#...#.#.....#...#.#...#.#...#.',
 '.#...#.#..##.#.....#...#.#.###.#.###.',
 '.#####.####..#.....#...#..##....##...',
 '.#...#.#...#.#.....#...#.#...#.#...#.',
 '.#...#.#...#.##....#...#.#...#.#...#.',
 '.#...#.####...####..###...###...###..',
 '.....................................']

arr=['..#','#..','...']
h=3
w=3
"""
mnct=100000000
mn=[0]
cnt=0
def tansaku(x,y,cnt,mnct):
    # print(x,y,cnt)
    # print(routed)
    #この道は通った
    cnt+=1
    #ゴールに着いたら最小経路を更新してリターン
    if (x==h-1) and (y == w-1):

        # print("Goal!")
        if mnct>cnt:
            mnct= cnt
            mn[0]=mnct
        return
    #下に行ける


    if(x<h-1)and(arr[x+1][y]!='#')and(routed[x+1][y]==False):
        routed[x+1][y]=True
        tansaku(x+1,y,cnt,mnct)
        routed[x+1][y]=False
    #→にいける

    if(y<h-1)and(arr[x][y+1]!='#')and(routed[x][y+1]==False):
        routed[x][y+1]=True
        tansaku(x,y+1,cnt,mnct)
        routed[x][y+1]=False

    #左にいける
    if(y>0)and(arr[x][y-1]!='#')and(routed[x][y-1]==False):
        routed[x][y-1]=True
        tansaku(x,y-1,cnt,mnct)
        routed[x][y-1]=False
    #上にいける

    if(x>0)and(arr[x-1][y]!='#')and(routed[x-1][y]==False):
        routed[x-1][y]=True
        tansaku(x-1,y,cnt,mnct)
        routed[x-1][y]=False



    # print("Game Over!")
    return

tansaku(0,0,0,mnct)


ans=0
for i in range(0,h):
    ans+=arr[i].count('#')

print(h*w-mn[0]-ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
h,w=map(int,input().split())
l=[]
v=0

for _ in range(h):
  b=[0 if i=="." else 1 for i in input()]
  v+=b.count(1)
  l.extend([b])

heap=[]
heappush(heap,(1,0,0))
while h:
  d,x,y=heappop(heap)
  if x==w-1 and y==h-1:break
  for (dx,dy) in zip([1,0],[0,1]):
    ax=x+dx
    ay=y+dy
    if 0<=ax<w and 0<=ay<h and not l[ay][ax]:
      heappush(heap,(d+1,ax,ay))

if x==w-1 and y==h-1:
  print(h*w-v-d)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
h,w=map(int,input().split())
l=[]
v=0

for _ in range(h):
  b=[0 if i=="." else 1 for i in input()]
  v+=b.count(1)
  l.extend([b])

heap=[]
heappush(heap,(1,0,0))
while h:
  d,x,y=heappop(heap)
  if x==w-1 and y==h-1:break
  for (dx,dy) in zip([1,0],[0,1]):
    ax=x+dx
    ay=y+dy
    if 0<=ax<w and 0<=ay<h and not l[ay][ax]:
      heappush(heap,(d+1,ax,ay))

print(h*w-v-d)

Submission status: Runtime Error

Solution code:
// https://beta.atcoder.jp/contests/abc088
// status:

#define SUBMIT

#include <utility>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

const int MAX_SIDE = 50;
const int NOT_VISITED = -1;

int H, W;
int sy, sx;
int gy, gx;
int dist[MAX_SIDE + 1][MAX_SIDE + 1];
char field[MAX_SIDE + 1][MAX_SIDE + 1];
int black_count;
queue<pair<int, int>> pos_queue;

bool is_goal(int y, int x) {
    return y == gy && x == gx;
}

void bfs(int y, int x) {
    pos_queue.push(make_pair(y, x));

    while (!pos_queue.empty()) {
        auto p = pos_queue.front();
        pos_queue.pop();

        y = p.first, x = p.second;
        auto up = y - 1, down = y + 1;
        auto left = x - 1, right = x + 1;

        // up
        if (1 <= up && field[up][x] != '#' && dist[up][x] == NOT_VISITED) {
            dist[up][x] = dist[y][x] + 1;
            if (is_goal(up, x)) break;
            pos_queue.push(make_pair(up, x));
        }

        // down
        if (down <= H && field[down][x] != '#' && dist[down][x] == NOT_VISITED) {
            dist[down][x] = dist[y][x] + 1;
            if (is_goal(down, x)) break;
            pos_queue.push(make_pair(down, x));
        }

        // left
        if (1 <= left && field[y][left] != '#' && dist[y][left] == NOT_VISITED) {
            dist[y][left] = dist[y][x] + 1;
            if (is_goal(y, left)) break;
            pos_queue.push(make_pair(y, left));
        }

        // right
        if (right <= W && field[y][right] != '#' && dist[y][right] == NOT_VISITED) {
            dist[y][right] = dist[y][x] + 1;
            if (is_goal(y, right)) break;
            pos_queue.push(make_pair(y, right));
        }
    }
}

void start_bfs() {
    memset(dist, NOT_VISITED, sizeof(dist));
    dist[sy][sx] = 0;
    bfs(sy, sx);
}


int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    auto s = std::string(R"(10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................
)");

    stringstream stream(s);
#endif
    stream >> H >> W;
    black_count = 0;
    for (int y = 1; y <= H; ++y) {
        for (int x = 1; x <= W; ++x) {
            stream >> field[y][x];
            if (field[y][x] == '#') black_count++;
        }
    }

    sy = 1, sx = 1;
    gy = H, gx = W;

    start_bfs();
    auto ans = H * W - black_count - dist[gy][gx] - 1;
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
B = [['']*(w+1) for _ in range(h+1)]
BIGINT = 1000000
C = [[BIGINT]*(w+1) for _ in range(h+1)]
wn = 0
for i in range(1,h+1):
    W = input()
    wn += W.count('.')
    for j in range(1,w+1):
        #print(j, W[j-1])
        B[i][j] = W[j-1]

def move(i, j, k):
    if i < 1 or h < i or j < 1 or w < j:
        return
    if B[i][j] == '#':
        return
    if C[i][j] < k:
        return
    C[i][j] = k
    move(i-1, j, k+1)
    move(i+1, j, k+1)
    move(i, j-1, k+1)
    move(i, j+1, k+1)
move(1, 1, 1)
if C[h][w] == BIGINT:
    print(-1)
else:
    print(wn-C[h][w])

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
B = [['']*(w+1) for _ in range(h+1)]
C = [[1000000]*(w+1) for _ in range(h+1)]
wn = 0
for i in range(1,h+1):
    W = input()
    wn += W.count('.')
    for j in range(1,w+1):
        #print(j, W[j-1])
        B[i][j] = W[j-1]

def move(i, j, k):
    if i < 1 or h < i or j < 1 or w < j:
        return
    if B[i][j] == '#':
        return
    if C[i][j] < k:
        return
    C[i][j] = k
    move(i-1, j, k+1)
    move(i+1, j, k+1)
    move(i, j-1, k+1)
    move(i, j+1, k+1)
move(1, 1, 1)
print(wn-C[h][w])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

def cid(x):
    return x[0] * W + x[1]

def cl(adj, x, y):
    xid = cid(x)
    yid = cid(y)
    links = adj.setdefault(xid , [])
    links.append((yid, 1))
    links = adj.setdefault(yid, [])
    links.append((xid, 1))

adj = {}
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        ni = i + 1
        if ni < H and S[ni][j] == ".":
            cl(adj, (i, j), (ni, j))
        nj = j + 1
        if nj < W and S[i][nj] == ".":
            cl(adj, (i, j), (i, nj))

c = dijkstra(adj, H*W, cid((0,0)))
hwc = c[cid((H-1,W-1))]
print(-1 if hwc == 2**64 else H * W - sum(s.count("#") for s in S) - hwc - 1)

Submission status: Runtime Error

Solution code:
from collections import deque

class Map_input():

    def __init__(self):
        line = input().split(" ")
        self.H = int(line[0])
        self.W = int(line[1])
        Map = [[] for i in range(self.H)]
        for i in range(self.H):
            line = input()
            for j in range(self.W):
                if line[j] == ".":
                    Map[i].append(0)
                else:
                    Map[i].append(1)
        self.Map = Map

class Maze_min():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dist = [[]]
    def __init__(self, H, W, Map, start, goal):
        self.H = H
        self.W = W
        self.Map = Map
        self.goal = goal
        self.queue = deque([start])
        Maze_min.dist = [[-1]*W for i in range(H)]
        Maze_min.dist[start[0]][start[1]] = 0
    
    def min_step(self):
        if len(self.queue) == 0:
            return -1 #例外は-1とする
        else:
            p = self.queue.popleft()
            if p == self.goal:
                return Maze_min.dist[p[0]][p[1]]
            else:
                for i in range(len(Maze_min.dx)):
                    (nx, ny) = (p[0] + Maze_min.dx[i], p[1] + Maze_min.dy[i])
                    if nx in range(self.H) and ny in range(self.W) and self.Map[nx][ny] == 0 and Maze_min.dist[nx][ny] == -1:
                        self.queue.append((nx, ny))
                        Maze_min.dist[nx][ny] = Maze_min.dist[p[0]][p[1]] + 1
                return self.min_step()

M = Map_input()
maze = Maze_min(M.H, M.W, M.Map, (0, 0), (M.H-1, M.W-1))
num_black = sum(list(map(sum, M.Map)))
d = maze.min_step()
if d == -1:
    print(-1)
else:
    print(M.H*M.W-d-num_black-1)