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:
def main():
	H, W = map(int,input().split())
	pos = [""]*H
	for i in range(H):
		pos[i] = input()
	x = min(W, H)
	can_clear = True
	for dist in range(H+W-1):
		impossible_range = True
		for i in range(H):
			if i > dist:
				break
			if dist-i > W:
				continue
			if pos[i][dist-i] == ".":
				impossible_range = False
				break
		if impossible_range:
			can_clear = False
			break
	if not can_clear:
		print(-1)
		return

	offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	def bfs(s, h, w):
		queue = [[0, 0, 0]]
		is_visited = [[False for _ in range(w)] for _ in range(h)]
		is_visited[0][0] = True
		while queue:
			cur = queue.pop(0)
			for o in offset:
				y, x = cur[0]+o[0], cur[1]+o[1]
				if x < 0 or x >= w or y < 0 or y >= h:
					continue
				if x == w-1 and y == h-1:
					return cur[2]+1
				if is_visited[y][x]:
					continue
				if s[y][x] == ".":
					queue.append([y, x, cur[2]+1])
					is_visited[y][x] = True
		return -1

	white_num = 0
	for i in range(H):
		for j in range(W):
			if pos[i][j] == ".":
				white_num += 1
	print(white_num-bfs(pos, H, W)-1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[0][0]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
Grid[0][0] = 0
if  flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[H-1][W-1]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
if Grid[0][0] and flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
if Grid[0][0]:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**9]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
if Grid[0][0]:
    print(H*W - bfs(Grid,0,0,queue) - 1 - black)
else:
    print(-1)

Submission status: Runtime Error

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

map_list = []
black = 0
for i in range(H):
    map_list.append(input())
    black += map_list[i].count('#')

queue = [(0,0)]
check = [(0,0)]
C = [0,0]
count = 0
hNow,wNow = 0,0

while 1:
    count += 1
    if len(queue) != 0:
        if queue[0] == (H-1,W-1):
            print(H*W - black -1 - max(C))
            break # ゴールか判定
    if len(check) == H * W:
        print(-1)
        break
    hNow,wNow = queue[0][0],queue[0][1]
    queue.pop(0)
    if hNow < H-1:
        if map_list[hNow+1][wNow] != "#":
            if (hNow+1,wNow) not in check:
                queue.append((hNow+1,wNow))
                check.append((hNow+1,wNow))
                C.append(C[count]+1)
    if wNow < W-1:
        if map_list[hNow][wNow+1] != "#":
            if (hNow,wNow+1) not in check:
                queue.append((hNow,wNow+1))
                check.append((hNow,wNow+1))
                C.append(C[count]+1)
    if hNow > 0:
        if map_list[hNow-1][wNow] != "#":
            if (hNow-1,wNow) not in check:
                queue.append((hNow-1,wNow))
                check.append((hNow-1,wNow))
                C.append(C[count]+1)
    if wNow > 0:
        if map_list[hNow][wNow-1] != "#":
            if (hNow,wNow-1) not in check:
                queue.append((hNow,wNow-1))
                check.append((hNow,wNow-1)) #近いやつを入れる
                C.append(C[count]+1)
    #print(queue)
#print(count)
#print(C)
#print(black)

Submission status: Runtime Error

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

map_list = []
black = 0
for i in range(H):
    map_list.append(input())
    black += map_list[i].count('#')

queue = [(0,0)]
check = [(0,0)]
C = [0,0]
count = 0
hNow,wNow = 0,0

while 1:
    count += 1
    if len(queue) != 0:
        if queue[0] == (H-1,W-1):
            break # ゴールか判定

    hNow,wNow = queue[0][0],queue[0][1]
    queue.pop(0)
    if hNow < H-1:
        if map_list[hNow+1][wNow] != "#":
            if (hNow+1,wNow) not in check:
                queue.append((hNow+1,wNow))
                check.append((hNow+1,wNow))
                C.append(C[count]+1)
    if wNow < W-1:
        if map_list[hNow][wNow+1] != "#":
            if (hNow,wNow+1) not in check:
                queue.append((hNow,wNow+1))
                check.append((hNow,wNow+1))
                C.append(C[count]+1)
    if hNow > 0:
        if map_list[hNow-1][wNow] != "#":
            if (hNow-1,wNow) not in check:
                queue.append((hNow-1,wNow))
                check.append((hNow-1,wNow))
                C.append(C[count]+1)
    if wNow > 0:
        if map_list[hNow][wNow-1] != "#":
            if (hNow,wNow-1) not in check:
                queue.append((hNow,wNow-1))
                check.append((hNow,wNow-1)) #近いやつを入れる
                C.append(C[count]+1)
    #print(queue)
#print(count)
#print(C)
#print(black)
print(H*W - black -1 - max(C))

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)
                if new_row == goal_x and new_column == goal_y:
                    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:
from collections import deque

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

cnt = 0
for i in range(H):
    cnt += s[i].count('.')

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

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque([[0,0]])
    visited[0][0] = 1

    while queue:
        y,x = queue.popleft()

        if y == H - 1 and x == W - 1:
            return visited[y][x]
        
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != '#' and visited[ny][nx] == float('inf'):
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1

print(cnt - bfs())

Submission status: Runtime Error

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

visit = [[False for j in range(W)] for i in range(H)]


queue = [[0,0]]
count = 0
while len(queue) > 0:
    count += 1
    next = []
    for now in queue:
        visit[now[0]][now[1]] = True
        for i, j in [[0,-1], [1,0], [0,1], [-1,0]]:
            if 0 <= now[0]+i <= H-1 and 0 <= now[1]+j <= W-1:
                if not visit[now[0]+i][now[1]+j]:
                    if grid[now[0]+i][now[1]+j] == ".":
                        next.append([now[0]+i, now[1]+j])
    if visit[-1][-1]:
        break
    queue = list(set(next[:]))


black = count
for i in range(H):
    black += grid[i].count("#")

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

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)

bfs(0,0)

count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            count += 1
 
ans = -1
if cost[H-1][W-1] != INF:
    ans = H*W-count-cost[-1][-1]
print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)

bfs(0,0)

count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            count += 1
 
ans = -1
if cost[H-1][W-1] != INF:
    ans = H*W-count-cost[]-1][-1]
print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)

bfs(0,0)

count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            count += 1
 
ans = -1
if d[H-1][W-1] != INF:
    ans = H*W-count-d[-1][-1]
print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)

bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    if 0<=h<H and 0<=w<W:
        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=h+dh<H and 0<=w+dw<W:
                if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                    cost[h+dh][w+dw] = cost[h][w]+1
                    return bfs(h+dh,w+dw)

bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] == INF:
                cost[h+dh][w+dw] = cost[h][w]+1
                return bfs(h+dh,w+dw)

bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)
bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]

cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    if h-1>=0:
        if s[h-1][w] == '.' and cost[h-1][w] > cost[h][w]+1:
            cost[h-1][w] = cost[h][w]+1
            bfs(h-1,w)
    if h+1<H:
        if s[h+1][w] == '.' and cost[h+1][w] > cost[h][w]+1:
            cost[h+1][w] = cost[h][w]+1
            bfs(h+1,w)
    if w-1>=0:
        if s[h][w-1] == '.' and cost[h][w-1] > cost[h][w]+1:
            cost[h][w-1] = cost[h][w]+1
            bfs(h,w-1)
    if w+1<W:
        if s[h][w+1] == '.' and cost[h][w+1] > cost[h][w]+1:
            cost[h][w+1] = cost[h][w]+1
            bfs(h,w+1)

bfs(0,0)

if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
count=0
queue=deque([[0,0,0]])
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs(x,y,k):
    if (not 0<=x<h) or (not 0<=y<w):
        return
    if field[x][y]=='#':
        return
    queue.append([x,y,k+1])
#    print(queue)
#    print(field)
while True:
    x,y,k=queue.popleft()
    if x==h-1 and y==w-1:
        print(count-k-1)
        sys.exit()
    field[x][y]='#'
    bfs(x+1,y,k)
    bfs(x-1,y,k)
    bfs(x,y-1,k)
    bfs(x,y+1,k)
print(-1)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
sw = [input() for _ in range(H)]

white = 0
for i in range(H):
	white += sw[i].count(".")
# print(white)

count = [[None]*W for _ in range(H)]
q = deque([])

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]
def BFS():
	i, j = q.popleft()
	
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= ny <= H-1 and 0 <= nx <= W-1 and sw[ny][nx] != '#' and count[ny][nx] == None:
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

	if len(q) != 0:
		BFS()


q.append((0, 0))
count[0][0] = 0

BFS()
# for i in count:
# 	print(i)
print(white-(count[H-1][W-1]+1))

Submission status: Runtime Error

Solution code:
from collections import deque

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

q = deque()
q.append((0, 0))
dist = [[0 for j in range(W)] for i in range(H)]
dr = [(1,0),(-1,0),(0,1),(0,-1)]

while (True):
    r = q.popleft()
    x = r[1]
    y = r[0]
    now = dist[y][x]
    if y == H-1 and x == W-1:
        break
    for d in range(4):
        nx = x + dr[d][0]
        ny = y + dr[d][1]
        if 0 <= nx < W and 0 <= ny < H:
            if S[ny][nx] != "#" and dist[ny][nx] == 0:
                dist[ny][nx] = now+1
                q.append((ny,nx))
sharp = sum([i.count("#") for i in S])
print(H * W - now - sharp - 1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
a=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a+=1

visited = [[0]*w for _ in range(h)]

def dfs(s,visit,h,w):
    stack=[[0,0,1]]
    visit[0][0]=1
    while stack:
        sh,sw,c=stack.pop(0)
        if sh==h-1 and sw==w-1:
            return c
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = sh+j, sw+k
            if new_h < 0 or new_h >= h or new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != "#" and visit[new_h][new_w] == 0:
                visit[new_h][new_w] = 1
                stack.append([new_h,new_w,c+1])
    return -1
  
if dfs(s,visited,h,w)==-1:
    print(-1)
else:
    print(h*w-c-a)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
try:
    print(ans-bfs(m,visited)-1)
except RuntimeError:
    print(-1)
    sys.exit()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    except RuntimeError:
        print(-1)


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
try:
    print(ans-bfs(m,visited)-1)
except RuntimeError:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    except RuntimeError:
        print(-1)


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
print(ans-bfs(m,visited)-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    except RuntimeError:
        return -1


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print(p if p==-1 else ans-p-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def bfs(maze, visited):
    sy,sx=0,0
    gy,gx=H-1,W-1
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]

        p=[]
        if x>0 : p.append([0,-1])
        if x<W-1: p.append([0,1])
        if y>0: p.append([-1,0])
        if y<H-1: p.append([1,0])
        for j, k in p:
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
print(ans-bfs(m,visited)-1)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


H, W = map(int, input().split())
white = 0
s = ['#' * (W + 2)]
for i in range(H):
    s_i = '#' + input() + '#'
    white += s_i.count('.')
    s.append(s_i)
s.append('#' * (W + 2))

visited = [[-1] * (W+2) for i in range(H+2)]
shortest = bfs(s, visited, 1, 1, H, W)
print(white - shortest - 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y,visit, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
        return 0
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0,[[0]*W for _ in range(H)] ,1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
visit =[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        visit[x][y] = 1
        global dist
        if n < dist:
            dist = n
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0, 1)
if not visit[H-1][W-1]:
    print(-1)
else:
    print(white - dist)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
from itertools import chain

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

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S_initial = deepcopy(S)

    
def bfs():
    S[0][0] = "#"
    dq = deque() ## (y, x, dist from start)
    dq.append((0,0,0))
    while dq:
        y,x,d = dq.popleft()
        for dy,dx in dire:
            ny = y + dy; nx = x + dx
            if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
                continue
            if (ny,nx) == (H-1,W-1):
                return d+1
            if S[ny][nx] == ".":
                dq.append((ny,nx,d+1))
                S[ny][nx] = "#"

dist = bfs()
S_flatten = list(chain.from_iterable(S_initial))
cnt_dot = S_flatten.count('.') - (dist+1)
print(cnt_dot)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
matrix = [input() for _ in range(H)]
(sy, sx) = (0, 0)
(gy, gx) = (H - 1, W - 1)

dist = [[None for _ in range(W)] for _ in range(H)]

q = deque([(sy, sx)])
dist[sy][sx] = 1

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

while q:
    cy, cx = q.popleft()
    if (cy, cx) == (gy, gx):
        break

    for (dy, dx) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        ny, nx = cy + dy, cx + dx

        if 0 <= nx < W and 0 <= ny < H and matrix[ny][nx] == ".":
            if dist[ny][nx] is None:
                q.append((ny, nx))
                dist[ny][nx] = dist[cy][cx] + 1

print(count_dots - dist[gy][gx])