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: Wrong Answer

Solution code:
import math

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

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

num_of_white = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            s[i][j] = 0     # 白なら 0
            num_of_white += 1
        else:
            s[i][j] = 1     # 黒なら 1

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


def numel(a):
    return W * a[0] + a[1]


def route_add(i1, j1, i2, j2):
    route_list[numel([i1, j1])][numel([i2, j2])] = 1


for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j - 1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j + 1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
        elif i == H-1:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
        else:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [1000000] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = 100000000 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]:
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示

# print("-----経路-----")
# previous_node = node_num - 1
# while previous_node != -1:
#     if previous_node !=0:
#         print(str(previous_node + 1) + " <- ", end='')
#     else:
#         print(str(previous_node + 1))
#     previous_node = previous_nodes[previous_node]
#
# print("-----距離-----")
# print(distance[node_num - 1])

print(num_of_white - distance[node_num - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(" "))

s = [list(input()) for _ in range(0, H)]

visited = {}
def walk(i, j, x):
	if (i, j) not in visited:
		visited[(i, j)] = x+1
		if i+1 < H and s[i+1][j] == '.':
			walk(i+1, j, x+1)
		if j+1 < W and s[i][j+1] == '.':
			walk(i, j+1, x+1)
		if i-1 > 0 and s[i-1][j] == '.':
			walk(i-1, j, x+1)
		if j-1 > W and s[i][j-1] == '.':
			walk(i, j-1, x+1)

walk(0, 0, 0)
if (H-1, W-1) in visited:
	print("".join(map(lambda x: "".join(x), s)).count(".") - visited[(H-1, W-1)])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(" "))

s = [list(input()) for _ in range(0, H)]

visited = {}
def walk(i, j):
	if (i, j) not in visited:
		visited[(i, j)] = True
		if i+1 < H and s[i+1][j] == '.':
			walk(i+1, j)
		if j+1 < W and s[i][j+1] == '.':
			walk(i, j+1)

walk(0, 0)
if (H-1, W-1) in visited:
	print("".join(map(lambda x: "".join(x), s)).count(".") - H - W + 1)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
# coding=utf-8

line = input().split(" ")
H = int(line[0])
W = int(line[1])

s = []
cnt_w = 0
for _ in range(H):
    line = list(input())
    for x in line:
        if x==".":
            cnt_w += 1
    s.append(line)

INF = 100000

diff = [
    [0,1]
    ,[0,-1]
    ,[1,0]
    ,[-1,0]
]

def dfs():
    q = []
    m = []
    for i in range(H):
        m.append([INF for _ in range(W)])
    q.append((0,0))
    m[0][0] = 1

    while len(q)>0:
        p = q.pop(0)
        if H-1==p[0] and W-1==p[1]:
            break

        for d in diff:
            ni = p[0]+d[0]
            nj = p[1]+d[1]
            if 0<=ni<H and 0<=nj<W:
                if s[ni][nj]=="." and m[ni][nj]==INF:
                    q.append((ni,nj))
                    m[ni][nj] = m[p[0]][p[1]]+1

    return m[H-1][W-1]

print(cnt_w - dfs())

Submission status: Wrong Answer

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, h, w, v, q):
    while True:
        if q.empty(): return -1
        k, i, j = q.get()
        if (i, j) not in v:
            v.add((i, j))
            break
    if i == h - 1 and j == w - 1: return k
    if i > 1 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
    if i < h - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
    if j > 1 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
    if j < w - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
    return s(m, h, w, v, q)

h, w = map(int, raw_input().split())
m = [raw_input()[:w] for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
c = s(m, h, w, set(), q)
if c == -1: print -1
else:
    a = 0
    for row in m:
        a += row.count('#')
    print h * w - c - a

Submission status: Wrong Answer

Solution code:
import queue

H, W = list(map(int, input().split()))
board = []
for i in range(H):
    board.append(input())

d = [[0 for i in range(W)] for j in range(H)]

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

sx, sy = 0, 0 # スタートの座標
gx, gy = H-1, W-1 # ゴールの座標

def bfs():
    que = queue.Queue()
    # すべての点をINFで初期化
    for i in range(H):
        for j in range(W):
            d[i][j] = float("inf")
    # スタート地点をキューに入れて、その点の距離を0にする
    que.put((sx, sy))
    d[sx][sy] = 0
    
    # キューが空になるまでループ
    while que.qsize() > 0:
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を(nx, ny)とする
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            if 0 <= nx < H and 0 <= ny < W:
                if board[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    que.put((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

def solve():
    res = bfs()
    if type(res) != "int":
        print(-1)
        return
    sharp_num = 0
    for l in board:
        for c in l:
            if c == "#":
                sharp_num += 1
    print(H*W - res - sharp_num - 1)
    
    
    
solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter
H, W = map(int, input().split())
s = np.array([[x for x in input()] for h in range(H)])
counter = Counter()
for row in s:
    for x in row:
        counter[x] += 1
print(counter['.']-(H+W-1))

Submission status: Wrong Answer

Solution code:
import queue

H, W = list(map(int, input().split()))
board = []
for i in range(H):
    board.append(input())

d = [[0 for i in range(W)] for j in range(H)]

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

sx, sy = 0, 0 # スタートの座標
gx, gy = H-1, W-1 # ゴールの座標

def bfs():
    que = queue.Queue()
    # すべての点をINFで初期化
    for i in range(H):
        for j in range(W):
            d[i][j] = float("inf")
    # スタート地点をキューに入れて、その点の距離を0にする
    que.put((sx, sy))
    d[sx][sy] = 0
    
    # キューが空になるまでループ
    while que.qsize() > 0:
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を(nx, ny)とする
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            if 0 <= nx < H and 0 <= ny < W:
                if board[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    que.put((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

def solve():
    res = bfs()
    sharp_num = 0
    for l in board:
        for c in l:
            if c == "#":
                sharp_num += 1
    print(H*W - res - sharp_num - 1)
    
    
    
solve()

Submission status: Wrong Answer

Solution code:
def D_Grid_Repainting():
    H,W=map(int, input().split())
    A=[]
    count=0
    for i in range(H):
        A.append(input())

    for i in range(H):
        for j in range(W):
            if A[i][j]=='#':
                count +=1
    print(H*W-(H+W-1)-count)
    
D_Grid_Repainting()

Submission status: Wrong Answer

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, h, w, v, q):
    if q.empty(): return -1
    while True:
        k, i, j = q.get()
        if (i, j) not in v:
            v.add((i, j))
            break;
    if i == h - 1 and j == w - 1: return k
    if i > 1 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
    if i < h - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
    if j > 1 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
    if j < w - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
    return s(m, h, w, v, q)

h, w = map(int, raw_input().split())
m = [raw_input()[:w] for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
c = s(m, h, w, set(), q)
if c == -1: print -1
else:
    a = 0
    for row in m:
        a += row.count('#')
    print h * w - c - a

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
s = [[-1 if w == "#" else 9999 for w in input()] for h in range(H)]
black = sum([ sum([ 1 for w in range(W) if s[h][w] == -1]) for h in range(H)])

neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]
s[0][0] = 1
check_list = [(0, 0)]
index = 0
while index < len(check_list):
    check = check_list[index]
    for neighbor in [(check[0] + neighbor[0], check[1] + neighbor[1]) for neighbor in neighbors]:
        if 0 <= neighbor[0] < H and 0 <= neighbor[1] < W and s[neighbor[0]][neighbor[1]] != -1:
            if s[neighbor[0]][neighbor[1]] > s[check[0]][check[1]] + 1:
                s[neighbor[0]][neighbor[1]] = s[check[0]][check[1]] + 1
                check_list.append(neighbor)
    index += 1

if s[H - 1][W - 1] == -1:
    print(-1)
else:
    print(W*H - black - s[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(" "))

s = [list(input()) for _ in range(0, H)]

visited = {}
def walk(i, j):
	if (i, j) not in visited:
		visited[(i, j)] = True
		if i+1 < H and s[i+1][j] == '.':
			walk(i+1, j)
		if j+1 < W and s[i][j+1] == '.':
			walk(i, j+1)

walk(0, 0)
if (H-1, W-1) in visited:
	i = 1
	for l in s:
		for c in l:
			if c == '.':
				i += 1
	print(i - H - W)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
def solve(H, W, s):
    from collections import deque, defaultdict
    dotcount = sum([sum([c == "." for c in row]) for row in s])
    s = [row + "#" for row in s]
    s.append("#" * (W + 1))
    distance = defaultdict(lambda:9999999999999)
    q = deque()
    q.append((0, 0, 0))
    distance[0, 0] = 0
    while q:
        x, y, d = q.popleft()
        for dx, dy in ((-1, 0), (+1, 0), (0, -1), (0, +1)):
            nx, ny, nd = x + dx, y + dy, d + 1
            if s[ny][nx] == "." and nd < distance[nx, ny]:
                distance[nx, ny] = nd
                q.append((nx, ny, nd))
    return dotcount - distance[W - 1, H - 1] - 1

H, W = [int(_) for _ in input().split()]
s = [input() for y in range(H)]

print(solve(H, W, s))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [[i for i in input()]for i in range(H)]
maze = [[False for i in range(W)] for i in range(H)]
bknum = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            maze[i][j]=True
        else:
            maze[i][j]=False
            bknum += 1


def ncell(i, j):
    tmp = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
    out = []
    for p in tmp:
        if 0<=p[0]<H and 0<=p[1]<W and maze[i][j]:
            out.append(p)
    return out

d = [[1000 for j in range(W)] for i in range(H)]
prev = [[-1 for j in range(W)] for i in range(H)]
d[0][0]=0
Q = set()
for i in range(H):
    for j in range(W):
        if maze[i][j]:
            Q.add(i*W+j)
while(len(Q)!=0):
    u = list(Q)[0]
    du = d[u//W][u%W]
    for v in Q:
        if d[v//W][v%W]<du:
            du = d[v//W][v%W]
            u=v
    Q -=set([u])
    for v in ncell(u//W, u%W):
        if d[v[0]][v[1]]>d[u//W][u%W]+1:
            d[v[0]][v[1]]=d[u//W][u%W]+1
            prev[v[0]][v[1]]=u
length=d[H-1][W-1]
if length != 1000:
    print(H*W-length-1-bknum)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="#"):
            bla+=1
        else:
            whi+=1
flag=1
for i in range(W):
    if(s[0][i]=="#"):
        flag=0
        for j in range(H):
            if(s[j][i]!="#"):
                flag=1
    if(flag==0):
        print(-1)
        sys.exit()
flag=1
for i in range(H):
    if(s[i][0]=="#"):
        flag=0
        for j in range(W):
            if(s[i][j]!="#"):
                flag=1
    if(flag==0):
        print(-1)
        sys.exit()
area=W*H
step=W+H-1
score=area-step-bla
print(score)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
s = [[-1 if w == "#" else 9999 for w in input()] for h in range(H)]
black = sum([ sum([ 1 for w in range(W) if s[h][w] == -1]) for h in range(H)])

neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]
s[0][0] = 1
check_list = [(0, 0)]
index = 0
while index < len(check_list):
    check = check_list[index]
    for neighbor in [(check[0] + neighbor[0], check[1] + neighbor[1]) for neighbor in neighbors]:
        if 0 <= neighbor[0] < H and 0 <= neighbor[1] < W:
            if s[neighbor[0]][neighbor[1]] > s[check[0]][check[1]] + 1:
                s[neighbor[0]][neighbor[1]] = s[check[0]][check[1]] + 1
                check_list.append(neighbor)
    index += 1

if s[H - 1][W - 1] == -1:
    print(-1)
else:
    print(W*H - black - s[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
src = [input() for i in range(H)]
walls = 0
for row in src:
    walls += row.count('#')

visited = [[0 for j in range(W)] for i in range(H)]
q = deque([(0,0,0)])
dxs = [1,0,-1,0]
dys = [0,1,0,-1]
dist = 0
while q:
    d,x,y = q.popleft()
    if (x,y) == (W-1,H-1):
        print(H*W - walls - dist - 2)
        exit()
    dist = max(dist,d)
    for dx,dy in zip(dxs,dys):
        nx,ny = x+dx, y+dy
        if not(0 <= nx < W) or not(0 <= ny < H): continue
        if src[ny][nx] == '#' or visited[ny][nx]: continue
        q.append((dist+1,nx,ny))
        visited[ny][nx] = 1

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, v, q):
    if q.empty(): return -1
    k, i, j = q.get()
    if i == len(m) - 1 and j == len(m[i]) - 1: return k
    if i > 1 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
        v.add((i - 1, j))
    if i < len(m) - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
        v.add((i + 1, j))
    if j > 1 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
        v.add((i, j - 1))
    if j < len(m[i]) - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
        v.add((i, j + 1))
    return s(m, v, q)

h, w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
v = set((0, 0))
c = s(m, v, q)
if c == -1: print -1
else:
    a = 0
    for row in m:
        a += row.count('#')
    print h * w - c - a

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
num_sharp = 0
for r in maze:
    for c in r:
        if c == "#":
            num_sharp += 1


def search(x, y):
    if x == h - 1 and y == w - 1:
        return True
    elif x >= h or y >= w or maze[x][y] == "#":
        return False
    else:
        return search(x + 1, y) or search(x, y + 1)


if search(0, 0):
    print(h * w - h - w + 1 - num_sharp)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
src = [input() for i in range(H)]
walls = 0
for row in src:
    walls += row.count('#')

visited = [[0 for j in range(W)] for i in range(H)]
q = deque([(0,0,0)])
dxs = [1,0,-1,0]
dys = [0,1,0,-1]
dist = 0
while q:
    d,x,y = q.popleft()
    visited[y][x] = 1
    if (x,y) == (W-1,H-1):
        print(H*W - walls - dist - 2)
        exit()
    dist = max(dist,d)
    for dx,dy in zip(dxs,dys):
        nx,ny = x+dx, y+dy
        if not(0 <= nx < W) or not(0 <= ny < H): continue
        if src[ny][nx] == '#' or visited[ny][nx]: continue
        q.append((dist+1,nx,ny))

print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
num_sharp = 0
for r in maze:
    for c in r:
        if c == "#":
            num_sharp += 1


def search(cur):
    if cur == [h - 1, w - 1]:
        return True
    elif cur[0] >= h or cur[1] >= w or maze[cur[0]][cur[1]] == "#":
        return False
    else:
        return search([cur[0] + 1, cur[1]]) or search([cur[0], cur[1] + 1])


if search([0, 0]):
    print(h * w - h - w + 1-num_sharp)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

field = [input() for _ in range(h)]

dist = [[h*w*100 for i in range(w)] for j in range(h)]
dist[0][0] = 1

import queue

q = queue.Queue()
q.put((0,0))

dx = [-1,1,0,0]
dy = [0,0,1,-1]
while not q.empty() :
    (x,y) = q.get()
    for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)] :
        nx = x + dx
        ny = y + dy
        if nx < 0 or nx >= h or ny < 0 or ny>= w :
            continue
        if field[nx][ny] == '#':
            continue
        if dist[nx][ny] > dist[x][y] :
            dist[nx][ny] = dist[x][y] + 1
            q.put((nx,ny))

# print(dist)

ans = h*w - dist[h-1][w-1]
for v in field:
    for c in v:
        if c == '#':
            ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

field = [input() for _ in range(h)]

dist = [[h*w*100 for i in range(w)] for j in range(h)]
dist[0][0] = 1

for i in range(1,w) :
    if field[0][i] == '.':
        dist[0][i] = dist[0][i-1] + 1

for i in range(1,h) :
    if field[i][0] == '.':
        dist[i][0] = dist[i-1][0] + 1
    for j in range(1,w) :
        if field[i][j] == '.':
            dist[i][j] = min(dist[i-1][j], dist[i][j-1]) + 1

# print(dist)

ans = h*w - dist[h-1][w-1]
for v in field:
    for c in v:
        if c == '#':
            ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

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

map_ = [[10**9]*w for i in range(h)]
# map_[0][0] = 10*

num_black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            num_black += 1


dq = deque([[0, 0, 1]])


ans = 0
while(len(dq) > 0):
    y, x, dis = dq.popleft()

    if map_[y][x] > dis:
        map_[y][x] = dis
    else:
        continue

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_[y+i][x+j] <= dis:
            continue
        if s[y+i][x+j] == "#":
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1])

ans = map_[-1][-1]
# print(map_)

if ans == 10**9:
    print(-1)
else:
    print(w*h-ans-num_black)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        i, j = q.popleft()
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if i+x < 1 or i+x > h or j+y < 1 or j+y > w or grid[i+x - 1][j+y - 1] != ".":
                continue
            v[i + x - 1][j + y -
                         1] = v[i - 1][j - 1] + 1
            q.append((i + x, j + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("#"))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        i, j = q.popleft()
        grid[i - 1][j - 1] = "*"
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if i+x < 1 or i+x > h or j+y < 1 or j+y > w or grid[i+x - 1][j+y - 1] != ".":
                continue
            v[i + x - 1][j + y -
                         1] = v[i - 1][j - 1] + 1
            q.append((i + x, j + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("#"))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        now = q.popleft()
        grid[now[0] - 1][now[1] - 1] = "*"
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if now[0]+x < 1 or now[0]+x > h or now[1]+y < 1 or now[1]+y > w or grid[now[0]+x - 1][now[1]+y - 1] != ".":
                continue
            v[now[0] + x - 1][now[1] + y -
                              1] = v[now[0] - 1][now[1] - 1] + 1
            q.append((now[0] + x, now[1] + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("#"))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def cal():
    from collections import deque
    h, w = map(int, input().split())
    s, count = [], 0
    for _ in range(h):
        a = input()
        count += a.count('#')
        s.append(list(a))
    ans = float('inf')
    q = deque()
    q.append([0, 0, 1])
    while q:
        c0, c1, c2 = q.popleft()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#':
                    q.append((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)