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: Accepted

Solution code:
arr=[]
numbero=list(map(int, input().split()))
for i in range(numbero[0]):
    arr.append(input())
way=[[0 for i in range(numbero[1])] for j in range(numbero[0])]
way[0][0]=1
head=0
whoop=[[0,0]]
while head<len(whoop):
    u=whoop[head][0]
    v=whoop[head][1]
    head+=1
    if u>0:
        if way[u-1][v]==0 and arr[u-1][v]=='.':
            way[u-1][v]=way[u][v]+1
            whoop.append([u-1,v])
    if v>0:
        if way[u][v-1]==0 and arr[u][v-1]=='.':
            way[u][v-1]=way[u][v]+1
            whoop.append([u,v-1])
    if u<numbero[0]-1:
        if way[u+1][v]==0 and arr[u+1][v]=='.':
            way[u+1][v]=way[u][v]+1
            whoop.append([u+1,v])
    if v<numbero[1]-1:
        if way[u][v+1]==0 and arr[u][v+1]=='.':
            way[u][v+1]=way[u][v]+1
            whoop.append([u,v+1])
if way[numbero[0]-1][numbero[1]-1]==0:
    print(-1)
else:
    head=0
    for i in arr:
        head+=i.count('.')
    print(head-way[numbero[0]-1][numbero[1]-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    # g = defaultdict(list)
    # for i, r in enumerate(S):
    #     for j, c in enumerate(r):
    #         if c == '.':
    #             if i > 0 and j > 0:
    #                 g[(i, j)].append((i-1, j-1))
    #     # g[u].append((v, (a, b)))
    #     # g[v].append((u, (a, b)))

    def d(s):
        dist = defaultdict(lambda : sys.maxsize)
        q =[]
        dist[s] = 0
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            i, j = u
            g = []            
            if i > 0 and S[i-1][j] == '.':
                g.append((i-1, j))

            if j > 0 and S[i][j-1] == '.':
                g.append((i, j-1))

            if i < H-1 and S[i+1][j] == '.':
                g.append((i+1, j))

            if j < W-1 and S[i][j+1] == '.':
                g.append((i, j+1))
            
            for v in g:
                alt = dist[u] + 1
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist = d((0, 0))[(H-1, W-1)]
    if dist == sys.maxsize:
        return -1
    return (H * W - sum(map(lambda x: x.count('#'), reduce(add, S)))) - dist - 1


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]

    
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
p=0
for i in range(h):
    t=list(input())
    p+=t.count("#")
    s.append(t)
t=[[0]*w for i in range(h)]
t[0][0]=1
u=[(0,0)]
while u:
    (x,y)=u[0]
    for i,j in [(0,-1),(0,1),(-1,0),(1,0)]:
        xx=x+i
        yy=y+j
        if (xx!=-1 and xx!=h and yy!=-1 and yy!=w):
            if s[xx][yy]=="."and t[xx][yy]==0:
                u.append((xx,yy))
                if t[xx][yy]==0:
                    t[xx][yy]+=t[x][y]+1
                else:
                    t[xx][yy]+=min(t[xx][yy],t[x][y]+1)
    u.pop(0)
if t[h-1][w-1]==0:
    print(-1)
else:
    print(h*w-p-t[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append([j for j in input()])

parent = [[-1 for j in range(w)] for i in range(h)]


def bfs(s):
    q = deque()
    check = [[0 for j in range(w)] for i in range(h)]

    q.append(s)
    check[s[0]][s[1]] = 1
    while len(q) != 0:
        u = q.popleft()
        x, y = u[0], u[1]
        if x > 0 and grid[x-1][y] == "." and check[x-1][y] == 0:
            check[x-1][y], parent[x-1][y] = 1, u
            q.append((x-1, y))
        if y > 0 and grid[x][y-1] == "." and check[x][y-1] == 0:
            check[x][y-1], parent[x][y-1] = 1, u
            q.append((x, y-1))
        if x < h-1 and grid[x+1][y] == "." and check[x+1][y] == 0:
            check[x+1][y], parent[x+1][y] = 1, u
            q.append((x+1, y))
        if y < w-1 and grid[x][y+1] == "." and check[x][y+1] == 0:
            check[x][y+1], parent[x][y+1] = 1, u
            q.append((x, y+1))

        check[x][y] = 2


def main():
    bfs((0, 0))

    if parent[h-1][w-1] != -1:
        x, y = h-1, w-1
        while x != 0 or y != 0:
            grid[x][y] = "#"
            x, y = parent[x][y]
        grid[0][0] = "#"

        pt = 0
        for i in range(h):
            for j in range(w):
                if grid[i][j] == ".":
                    pt += 1

    else:
        pt = -1

    print(pt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append([j for j in input()])

parent = [[-1 for j in range(w)] for i in range(h)]


def bfs(s):
    q = deque()
    check = [[0 for j in range(w)] for i in range(h)]

    q.append(s)
    check[s[0]][s[1]] = 1
    while len(q) != 0:
        u = q.popleft()
        for i in range(h):
            for j in range(w):
                if grid[i][j] == '.' and check[i][j] == 0:
                    dx, dy = abs(i-u[0]), abs(j-u[1])
                    if dx <= 1 and dy <= 1 and dx + dy < 2:
                        check[i][j] = 1
                        parent[i][j] = u
                        q.append((i, j))
        check[u[0]][u[1]] = 2


def main():
    bfs((0, 0))

    if parent[h-1][w-1] != -1:
        x, y = h-1, w-1
        while x != 0 or y != 0:
            grid[x][y] = "#"
            x, y = parent[x][y]
        grid[0][0] = "#"

        pt = 0
        for i in range(h):
            for j in range(w):
                if grid[i][j] == ".":
                    pt += 1

    else:
        pt = -1

    print(pt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

grid=[]
S=""
for i in range(W+2):
    S = S+'#'
grid.append(S)
for i in range(H):
    grid.append('#'+input()+'#')
grid.append(S)

reached=[]
for i in range(H+2):
    reached.append([0*j for j in range(W+2)])

number_of_black_grid=0
for row in grid:
    number_of_black_grid += row.count('#')
s_x=1
s_y=1
g_x=W
g_y=H

def isGoal(x,y,g_x,g_y):
    if x==g_x and y==g_y:
        return True
    else:
        return False

def BFS_search(s_x, s_y, g_x, g_y):
    queue=[]
    queue.append([s_y, s_x, 0])
    reached[s_y][s_x]=0
    while len(queue)>0:
        v=queue.pop(0)
        if grid[v[0]+1][v[1]]=='.' and reached[v[0]+1][v[1]]==0 and [v[0]+1, v[1]]!=[s_y, s_x]:
            reached[v[0]+1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]+1, g_x, g_y):
                break
            else:
                queue.append([v[0]+1, v[1], v[2]+1])
        if grid[v[0]][v[1]+1]=='.' and reached[v[0]][v[1]+1]==0 and [v[0], v[1]+1]!=[s_y, s_x]:
            reached[v[0]][v[1]+1]=v[2]+1
            if isGoal(v[1]+1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]+1, v[2]+1])
        if grid[v[0]-1][v[1]]=='.' and reached[v[0]-1][v[1]]==0 and [v[0]-1, v[1]]!=[s_y, s_x]:
            reached[v[0]-1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]-1, g_x, g_y):
                break
            else:
                queue.append([v[0]-1, v[1], v[2]+1])
        if grid[v[0]][v[1]-1]=='.' and reached[v[0]][v[1]-1]==0 and [v[0], v[1]-1]!=[s_y, s_x]:
            reached[v[0]][v[1]-1]=v[2]+1
            if isGoal(v[1]-1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]-1, v[2]+1])

BFS_search(s_x, s_y, g_x, g_y)
if reached[g_y][g_x] == 0:
    print(-1)
else:
    maximum_score = ((H+2)*(W+2)-number_of_black_grid)-(reached[g_y][g_x]+1)
    print(maximum_score)

Submission status: Accepted

Solution code:
from collections import deque

def main():
	h, w = list(map(int, input().split()))

	cs = [list(input()) for _ in range(h)]
	ds = [[10 ** 10 for _ in range(w)] for _ in range(h)]

	goal = (h - 1, w - 1)
	move = [(1, 0), (0, -1), (-1, 0), (0, 1)]
	q = deque()
	
	ds[0][0] = 0
	q.append((0, 0))

	while len(q) >= 1:
		cur = q.popleft()
		if cur == goal:
			break

		for i in range(4):
			if 0 <= cur[0] + move[i][0] < h and 0 <= cur[1] + move[i][1] < w:
				if cs[cur[0] + move[i][0]][cur[1] + move[i][1]] == ".":
					if ds[cur[0] + move[i][0]][cur[1] + move[i][1]] == 10 ** 10:
						q.append((cur[0] + move[i][0], cur[1] + move[i][1]))
						ds[cur[0] + move[i][0]][cur[1] + move[i][1]] = ds[cur[0]][cur[1]] + 1

	if ds[goal[0]][goal[1]] < 10 ** 10:
		print(counter(cs) - ds[goal[0]][goal[1]] - 1)
	else:
		print(-1)

def counter(cs):
	ans = 0
	for c in cs:
		ans += c.count(".")
	return ans

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
import queue

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


white = 0
	
maze = []

for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

if maze[0][0] == '#' or maze[H-1][W-1] == '#':
	print (-1)
	sys.exit()

	
maze[H-1][W-1] =	'g'
	
q = queue.Queue()
q.put([0,0,0])

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if maze[y][x] == 'g':
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)
	
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

R, C = map(int, input().split())
c = [["#" for _ in range(C + 2)]] + [["#"] + list(input()) + ["#"] for _ in range(R)] + [["#" for _ in range(C + 2)]]
tekazu = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

def bfs(start, goal):
	queue = deque([start])
	visited = []
	while queue:
		#print(queue)
		label = queue.pop()
		
		if label == goal:
			visited.append(label)
			return True

		if label not in visited:
			visited.append(label)
			#print(visited)
			if c[label[0] + 1][label[1]] == "." and [label[0] + 1, label[1]] not in visited:
				queue.appendleft([label[0] + 1, label[1]])
				tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1

			if c[label[0] - 1][label[1]] == "." and [label[0] - 1, label[1]] not in visited:
				queue.appendleft([label[0] - 1, label[1]])
				tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1

			if c[label[0]][label[1] + 1] == "." and [label[0], label[1] + 1] not in visited:
				queue.appendleft([label[0], label[1] + 1])
				tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1

			if c[label[0]][label[1] - 1] == "." and [label[0], label[1] - 1] not in visited:
				queue.appendleft([label[0], label[1] - 1])
				tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
		#print(visited)
	return False

if bfs([1, 1], [R, C]) == False:
	print(-1)
else:
	num = 0
	for r in c:
		num += r.count(".")
	print(num - tekazu[R][C] - 1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
if s[0][0] == '#' or s[H-1][W-1] == '#':
    print(-1)
    exit()
m = s[:]
goal = [H-1,W-1]
move = ((-1,0),(1,0),(0,-1),(0,1))
queue = deque()
queue.append((0,0))
m[0][0] = 0
while queue:
    now = queue.popleft()
    count = m[now[0]][now[1]] + 1
    for h,w in move:
        y,x = now[0]+h,now[1]+w
        if y < 0 or y >= H or x < 0 or x >= W:
            continue
        if m[y][x] == '.':
            m[y][x] = count
            queue.append((y,x))
    if m[H-1][W-1] != '.':
        break
if m[H-1][W-1] == '.':
    print(-1)
    exit()
ans = H*W - m[H-1][W-1] - 1 - sum([i.count('#') for i in s])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]
flag = [[-1 for i in range(W)] for j in range(H)]
whites = sum(grid[i].count('.') for i in range(H))
#BFS
q = deque()
q.append([0,0])
flag[0][0] = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
    v = q.popleft()
    for j in range(4):
        if 0 <= v[0] + dx[j] < H and 0 <= v[1] + dy[j] < W and grid[v[0]+dx[j]][v[1]+dy[j]] == '.' and flag[v[0]+dx[j]][v[1]+dy[j]] == -1:
            flag[v[0]+dx[j]][v[1]+dy[j]] = flag[v[0]][v[1]] + 1
            q.append([v[0]+dx[j], v[1]+dy[j]])
if flag[H-1][W-1] == -1:
    print(-1)
else:
    print(whites - flag[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
import queue

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

temp = [[-1 for j in range(W+2)]]
B = temp+[[] for i in range(H)]+temp

dot = 0
for i in range(1,H+1):
    S = input()
    B[i].append(-1)
    for s in S:
        if s==".":
            B[i].append(H*W)
            dot += 1
        else:
            B[i].append(-1)
    B[i].append(-1)
    
Q = queue.Queue()
Q.put((1,1))
B[1][1]=1

min_root = dot
isok = False
while(not Q.empty()):
    y,x = Q.get()
    L = [[y-1,x],[y+1,x],[y,x-1],[y,x+1]]
    move = B[y][x]+1
    for dy,dx in L:
        if move < B[dy][dx]:
            Q.put((dy,dx))
            B[dy][dx] = move
            if dy==H and dx==W: isok=True
    #print(B)

if isok:
    print(dot-B[H][W])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = {(i,j):c for i in range(h) for j, c in enumerate(input())}

blacks = sum(c == '#' for c in maze.values())

def bfs(i, j):
    dq = deque()
    dq.appendleft((1, (i, j)))
    while dq:
        steps, (i, j) = dq.pop()
        if (i, j) == (h-1, w-1):
            return steps
        if maze.get((i, j), '#') == '#':
            continue
        maze[(i, j)] = '#'
        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
        dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs)

res = bfs(0, 0)
print(-1 if res is None else h*w - res - blacks)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
dot_cnt = 0
for g in grid:
    dot_cnt += g.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1

deq = deque()
deq.append((0, 0))
grid[0][0] = 0

y_list = [-1, 1, 0, 0]
x_list = [0, 0, -1, 1]

while deq:
    y, x = deq.popleft()
    if y == gy and x == gx:
        break
    for i in range(len(y_list)):
        dy = y + y_list[i]
        dx = x + x_list[i]
        if dy < 0 or H <= dy or dx < 0 or W <= dx:
            continue
        if grid[dy][dx] == '.':
            deq.append((dy, dx))
            grid[dy][dx] = grid[y][x] + 1
if grid[gy][gx] == '.':
    print(-1)
else:
    print(dot_cnt - (grid[gy][gx] + 1))

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
S = [input() for i in range(H)]
queue = [(0,0,1)]
done ={(0,0)}
count = sum(row.count("#") for row in S)

def bfs(x,y,c):
    if(x<0 or y<0 or x>=W or y>=H or S[y][x]=="#"):
        return
    
    if(x,y) in done:
        return
    
    queue.append((x,y,c+1))
    done.add((x,y))

dx = [1,-1,0,0]
dy = [0,0,1,-1] 
flag= -1
while queue:
    x,y,c = queue.pop(0)
    if x==W-1 and y==H-1:
        flag=1
        break
    for i in range(4):
        bfs(x+dx[i],y+dy[i],c)

print(flag if flag == -1 else (H*W-count-c))

Submission status: Accepted

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

L = [[-1] * W for i in range(H)]
L[0][0] = 0
Open = deque([np.array([0,0])])
D = np.array([[0,1], [1,0], [-1,0], [0,-1]])
white = 0
for s in S:
    for s2 in s:
        if s2 == ".":
            white += 1
while True:
    if len(Open) == 0:
        print(-1)
        exit()
    n = Open.popleft()
    for d in D:
        nNew = n+d
        if not(0 <= nNew[0] < H and 0 <= nNew[1] < W):
            continue
        if S[nNew[0]][nNew[1]] == "#":
            continue
        if L[nNew[0]][nNew[1]] == -1:
            L[nNew[0]][nNew[1]] = L[n[0]][n[1]] + 1
            Open.append(nNew)
        if (nNew == np.array([H-1,W-1])).all():
            print(white - L[H-1][W-1] - 1)
            exit()

Submission status: Accepted

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
visit[0][0]=True
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
                visit[ny][nx]=True
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
visit[0][0]=True
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
                visit[ny][nx]=True
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
c = []

for i in range(h):
    ci = list(input())
    ans += ci.count(".")
    c.append(ci)

sy = 0
sx = 0
gy = h-1
gx = w-1

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

que = deque([(sy,sx)])
c[sy][sx] = 1
while bool(que):
    y, x = que.popleft()
    if y == gy and x == gx:
        break
    for i in range(4):
        yi = y + dy[i]
        xi = x + dx[i]
        if 0 <= yi < h and 0 <= xi < w and c[yi][xi] == ".":
            que.append((yi,xi))
            c[yi][xi] = c[y][x] + 1

if c[gy][gx] == ".":
    print(-1)
else:
    print(ans - c[gy][gx])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
                if e == (H, W):
                    return white_num - D[H][W]
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

Submission status: Accepted

Solution code:
from collections import deque
h, w =map(int, input().split())
s = [input() for i in range(h)]
s_x, s_y = 0, 0
##ある場所を塗る。その上でBFS。最大値を求める。
#最短経路で辿り着く時、塗りつぶす手は最大になる。
#最短経路の時は、通るますが考えうる中で一番少ないからねえ。そりゃそうか。
max = 0
c = [[0] * w for i in range(h)]
#cを定義する時は、横に並べてからそれを縦に並べる。つまり、列数を指定してから、その外で
#行数を指定する。ただ、要素にアクセスするときは、c[行番号][列番号]
#外側ほど、左側の要素になる？
def BFS():
    q = deque()
    q.append((s_x, s_y))

    while len(q) > 0:
        y, x = q.popleft()
        if y == h - 1 and x == w - 1:
            return c[y][x]
        if x < w - 1:
            if s[y][x+1] == '.' and c[y][x+1] == 0:
                q.append((y, x+1))
                c[y][x+1] = c[y][x] + 1
        if x > 0:
            if s[y][x-1] == '.' and c[y][x-1] == 0:
                q.append((y, x-1))
                c[y][x-1] = c[y][x] + 1
        if y < h - 1:
            if s[y+1][x] == '.' and c[y+1][x] == 0:
                q.append((y+1, x))
                c[y+1][x] = c[y][x] + 1
        if y > 0:
            if s[y-1][x] == '.' and c[y-1][x] == 0:
                q.append((y-1, x))
                c[y-1][x] = c[y][x] + 1

    return(-1)

area = h*w
blunk_num_origin = 0
for ch1 in s:
    for ch2 in ch1:
        if ch2 == '#':
            blunk_num_origin += 1

min_grid = BFS()
if min_grid == -1:
    print(min_grid)
else:
    sol = area-blunk_num_origin-2-(min_grid-1)
    #print(area,min_grid,blunk_num_origin)
    print(sol)

Submission status: Accepted

Solution code:
import numpy as np
H,W = map(int,input().split())
H += -1
W += -1
import sys
ma = [[c for c in l.strip()] for l in sys.stdin]
ya = []
for s in ma:
  ya.extend(s)
count = ya.count(".")
ma = np.array(ma,"U10")
ma[0][0] = 1
que = []
que.append([0,0])
while len(que) > 0:
  y,x = que.pop(0)
  if y == H and x == W:
    break
  score = ma[y][x]
  try:
    if y != 0:
      y1 = ma[y-1][x] 
  except:
    pass
  try:
    y2 = ma[y+1][x]
  except:
    pass
  try:
    if x != 0:
      x1 = ma[y][x-1]
  except:
    pass
  try:
    x2 = ma[y][x+1] 
  except:
    pass
  try:
    if y1 == ".":
      ma[y-1][x] = str(int(score) + 1)
      que.append([y-1, x])
  except:
    pass
  try:
    if y2 == ".":
      ma[y+1][x] = str(int(score) + 1)
      que.append([y+1, x])
  except:
    pass
  try:
    if x1 == ".":
      ma[y][x-1] = str(int(score) + 1)
      que.append([y, x-1])
  except:
    pass
  try:
    if x2 == ".":
      ma[y][x+1] = str(int(score) + 1)
      que.append([y, x+1])
  except:
    pass
  x1 = 999
  x2 = 999
  y1 = 999
  y2 = 999
if ma[H][W] == ".":
  print(-1)
else:
  ten = int(ma[H][W])
  print(count - ten)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
white = 0
que = deque([])
visited = []
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = -1

for i in range(h):
  temp = list(input())
  white += temp.count('.')
  maze.append(temp)

for i in range(h):
  visited.append([0]*w)

visited[0][0] = 1
que.append([0, 0, 1])

while len(que):
  y, x, count = que.popleft()
  # print(y, x)
  if x == w-1 and y == h-1:
    ans = white - count
    break
  
  for dir in dirs:
    if y+dir[0] < 0 or y+dir[0] >= h or x+dir[1] < 0 or x+dir[1] >= w:
      continue

    if maze[y+dir[0]][x+dir[1]] == '.' and visited[y+dir[0]][x+dir[1]] == 0:
      visited[y+dir[0]][x+dir[1]] = 1
      que.append([y+dir[0], x+dir[1], count+1])

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [input() for i in range(h)]

memo = [[0]*w for i in range(h)]

from collections import deque
q = deque()
q.append((0, 0))

while len(q) > 0:
    y, x = q.popleft()
    if y == h-1 and x == w-1:
        break
    if x > 0:
        if s[y][x-1] == "." and memo[y][x-1] == 0:
            q.append((y, x-1))
            memo[y][x-1] = memo[y][x] + 1
    if x < w-1:
        if s[y][x+1] == "." and memo[y][x+1] == 0:
            q.append((y, x+1))
            memo[y][x+1] = memo[y][x] + 1
    if y > 0:
        if s[y-1][x] == "." and memo[y-1][x] == 0:
            q.append((y-1, x))
            memo[y-1][x] = memo[y][x] + 1
    if y < h-1:
        if s[y+1][x] == "." and memo[y+1][x] == 0:
            q.append((y+1, x))
            memo[y+1][x] = memo[y][x] + 1

count = 0

for H in range(h):
    for W in range(w):
        if s[H][W] == "#":
            count += 1

if memo[h-1][w-1] == 0:
    print(-1)
else:
    print(w*h - memo[h-1][w-1]-1 - count)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain
H, W = map(int, input().split(' '))
Maze = [list(input()) for _ in range(H)]
White = list(chain.from_iterable(Maze)).count('.')
Maze[0][0] = 1
q = deque([])
current = [0, 0]
q.append(current)

dir_x = [1, -1, 0, 0]
dir_y = [0, 0, 1, -1]
while len(q) > 0:
    now_y, now_x = q.popleft()
    if now_y == H-1 and now_x == W-1 : break
    for (dx, dy) in zip(dir_x, dir_y):
        if 0 <= now_y + dy <= H-1 and 0 <= now_x + dx <= W-1 and Maze[now_y + dy][now_x + dx] == '.':
            Maze[now_y + dy][now_x + dx] = Maze[now_y][now_x] + 1
            q.append([now_y + dy, now_x + dx])


if Maze[H-1][W-1] == '.': print(-1)
else: print(White - Maze[H-1][W-1])

Submission status: Accepted

Solution code:
import queue
h, w = map(int, input().split())
masu = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
INF = 100000
cood = (0, 0)
d = [[INF for _ in range(w)] for _ in range(h)]
d[0][0] = 0

black_num = 0
for i in range(h):
    black_num += masu[i].count('#')

que = queue.Queue()
que.put((0, 0))
while not que.empty():
    cood = que.get()
    if cood[0] == h-1 and cood[1] == w-1:
        break
    for i in range(4):
        ncood = (cood[0] + dy[i], cood[1] + dx[i])
        if 0 <= ncood[0] and ncood[0] < h and 0 <= ncood[1] and ncood[1] < w and masu[ncood[0]][ncood[1]] != '#' and d[ncood[0]][ncood[1]] == INF:
            que.put(ncood)
            d[ncood[0]][ncood[1]] = d[cood[0]][cood[1]] + 1


if d[h-1][w-1] == INF:
    print(-1)
else:
    print(h*w - d[h-1][w-1] - 1 - black_num)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[[] for j in range(h)]
t=[[0]*w for k in range(h)]
t[0][0]=1
q=0
u=[]
for i in range(h):
    s[i]+=list(input())
    q+=s[i].count("#")
u.append((0,0))
while u!=[]:
    (x,y)=u[0]
    if x!=h-1:
        if t[x+1][y]==0 and s[x+1][y]==".":
            t[x+1][y]=t[x][y]+1
            u.append((x+1,y))
    if y!=w-1:        
        if t[x][y+1]==0 and s[x][y+1]==".":
            t[x][y+1]=t[x][y]+1
            u.append((x,y+1))
    if x!=0:        
        if t[x-1][y]==0 and s[x-1][y]==".":
            t[x-1][y]=t[x][y]+1
            u.append((x-1,y))
    if y!=0:        
        if t[x][y-1]==0 and s[x][y-1]==".":
            t[x][y-1]=t[x][y]+1
            u.append((x,y-1))
    u.pop(0)
if t[h-1][w-1]==0:
    print(-1)
else:    
    print((h*w-t[h-1][w-1])-q)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
s=[]
for i in range(H):
    s.append(input().strip())
dist=[[float("inf")]*W for i in range(H)]
Q=[]
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            Q.append((i,j))
dist[0][0]=0
while len(Q) > 0:
    Q=sorted(Q,key=lambda x: dist[x[0]][x[1]])
    pt=Q.pop(0)
    if pt==(H-1,W-1):
        break
    dpt = dist[pt[0]][pt[1]]
    for nbr in [(pt[0]-1,pt[1]),(pt[0],pt[1]-1),(pt[0]+1,pt[1]),(pt[0],pt[1]+1)]:
        if nbr in Q:
            dist[nbr[0]][nbr[1]] = min(dist[nbr[0]][nbr[1]],dpt+1)
    
#全体-黒マスー最短路
print(max(H*W-sum(i.count("#") for i in s)-dist[-1][-1]-1,-1))

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
a=deque()
while (q != a):
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

if (Dis[H-1][W-1]==-1):
    print(-1)
else:
    print(Shiro-Dis[H-1][W-1]-1)

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().split())
grid = [raw_input() for y in range(h)]
dist = [[-1]*w for y in range(h)]
que = [(0,0)]
dist[0][0] = 0
while que != []:
    cx, cy = que.pop(0)
    for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
        nx, ny = cx+dx, cy+dy
        if (0 <= nx < w) and (0 <= ny < h) and (grid[ny][nx] == '.') and (dist[ny][nx] == -1):
            que.append((nx, ny))
            dist[ny][nx] = dist[cy][cx] + 1
d = dist[h-1][w-1]
if d == -1:
    print -1
else:
    print (h*w - d - 1 - sum([len(filter(lambda c: c=="#", line)) for line in grid]))