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:
from collections import deque
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dist = [[99999] * w for _ in range(h)]
kuromasu_count = 0
for i in maze:
    kuromasu_count += i.count("#")

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()    
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] != 99999:
                continue      
            dist[nx][ny] = dist[x][y] + 1            
            q.append((nx, ny))



dist[0][0] = 0
goal_x, goal_y = h-1, w-1
bfs(0, 0)
shiromasu = dist[goal_x][goal_y]
if shiromasu == 99999:
    print("-1")
else:
    answer = h * w - (shiromasu + 1) - kuromasu_count
    print(answer)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())

m = [list(input()) for _ in range(h)]
# '#'の数を数えておく
sharp_num = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '#':
            sharp_num += 1

def bfs(s):
    que = deque([s])
    log = [[0]*w for _ in range(h)]
    while len(que):
        y,x = que.popleft()
        for dy, dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y + dy
            nx = x + dx
            if not (0<=ny<h and 0<=nx<w) or m[ny][nx] == '#' or log[ny][nx] != 0:
                continue
            log[ny][nx] = log[y][x] + 1
            if (ny,nx) == (h-1, w-1):
                return log[ny][nx]

            que.append((ny,nx))

    return 0

result = bfs((0,0))

if result:
    print(h*w - sharp_num - (result+1))
else:
    print('-1')

Submission status: Accepted

Solution code:
from collections import deque

icase=0
if icase==0:
    r,c=map(int,input().split())
#    xy=[[[0] for i in range(c+2)] for i in range(r+2)]
#    xy=[[-1] *(c+2) for i in range(r+2)]
#    for i in range(1,r+1):
#        xy[i]=[-1]+list(map(int,input().split()))+[-1]
    xy=[["#"] *(c+2) for i in range(r+2)]
    for i in range(1,r+1):
        xy[i]=["#"]+list(input())+["#"]
elif icase==1:
    c,r=3,3       
    xy=[["#","#","#","#","#"],
        ["#",".",".","#","#"],
        ["#","#",".",".","#"],
        ["#",".",".",".","#"],
        ["#","#","#","#","#"]]

sc=[0,1,-1,0]
sr=[1,0,0,-1]
        
g=[[[] for j in range(c+2)] for i in range(r+2)]

for ri in range(1,r+1):
    for ci in range(1,c+1):
        if xy[ri][ci]==".":
            for i in range(4):
                if xy[ri+sr[i]][ci+sc[i]]==".":
                    g[ri][ci].append((ri+sr[i],ci+sc[i]))

#-----------------------------------------
sy,sx=1,1
gy,gx=r,c
#xy[sy][sx]=-1
q=deque()
q.append((sy,sx))

parent=[[-1]*(c+2) for i in range(r+2)]
parent[sy][sx]=0
dist=[[-1]*(c+2) for i in range(r+2)]
dist[sy][sx]=1
yn=""
while q:
    sty,stx = q.popleft()
    for vy,vx in g[sty][stx]:
        xy[vy][vx]=-1
        if vy==gy and vx==gx:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            yn="yes"
            break
        elif parent[vy][vx] !=-1:
            continue
        else:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            q.append((vy,vx))
#            print(q0)
    if yn=="yes":
        break

if yn!="yes":
    print(-1)
else:
    icnt=0
    for ri in range(1,r+1):
        for ci in range(1,c+1):
            if xy[ri][ci]=="." or xy[ri][ci]==-1:
                icnt+=1
    print(icnt-dist[gy][gx])    
#-----------------------------------------

Submission status: Accepted

Solution code:
from collections import deque

H,W = list(map(int, input().split()))
S = [input() for _ in range(H)]
dist = [[0] * W for i in range(H)]
dist[0][0] = 1

whites = 0
for s in S:
    for w in s:
        if w == ".":
            whites += 1

# Pythonの再帰はおっっそい. 再帰が今回のケースだと使いにくい(探索打ち切り)
def BFS(cur):
    #global dist
    x_path = [-1,0,1,0]
    y_path = [0,-1,0,1]

    q = deque()
    q.append(cur)
    while True:
        if len(q) == 0:
            break
        cur = q.popleft()
        if cur == (H,W):
            break

        for x,y in zip(x_path, y_path):
            nex = (cur[0] + x, cur[1] + y)
            if nex[0] < 1 or nex[0] > H or nex[1] < 1 or nex[1] > W:
                continue
            if S[nex[0]-1][nex[1]-1] == "#":
                continue
            if dist[nex[0]-1][nex[1]-1] > 0:
                continue

            dist[nex[0]-1][nex[1]-1] = dist[cur[0]-1][cur[1]-1] + 1 
            q.append(nex)


BFS((1,1))
if dist[H-1][W-1] == 0:
    print(-1)
else:
    print(whites - dist[H-1][W-1])

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
import sys

M = []
H = 0
W = 0
qx = deque()
qy = deque()
qc = deque()

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))

    startX = 0
    startY = 0
    dot = 0
    for i in range(H):
        for j in range(W):
            if M[i][j]=='.':
                dot += 1
    
    cnt = bfs(0,0)
    if(cnt>=0):
        print(dot-cnt)
    else:
        print(-1)

def bfs(y,x):
    global M,H,W
    Mtemp = deepcopy(M)
    Mtemp[y][x] = '#'
    qx.append(x)
    qy.append(y)
    qc.append(1)

    while len(qx) !=0:
        x =  qx.popleft()
        y =  qy.popleft()
        cnt = qc.popleft()
        if(x==W-1 and y==H-1):
            return cnt

        if x-1>=0:
            if Mtemp[y][x-1] == '.':
                Mtemp[y][x-1] = '#'
                qx.append(x-1)
                qy.append(y)
                qc.append(cnt+1)
        if x+1<W:
            if Mtemp[y][x+1] == '.':
                Mtemp[y][x+1] = '#'
                qx.append(x+1)
                qy.append(y)
                qc.append(cnt+1)
        if y-1>=0:
            if Mtemp[y-1][x] == '.':
                Mtemp[y-1][x] = '#'
                qx.append(x)
                qy.append(y-1)
                qc.append(cnt+1)
        if y+1<H:
            if Mtemp[y+1][x] == '.':
                Mtemp[y+1][x] = '#'
                qx.append(x)
                qy.append(y+1)
                qc.append(cnt+1)

    return -1




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]

from collections import deque
q = deque([(0,0)])
dist = [[-1]*w for _ in range(h)]
dist[0][0]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

count=0
for i in range(h):
    for j in range(w):
        if u[i][j]=='.':
            count+=1
if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(count-dist[h-1][w-1]-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
cnt=0
s=[input() for _ in range(h)]
for x in s:
	cnt+=x.count(".")
ans=0
inf=10**8
dp=[[inf]*w for _ in range(h)]
dp[0][0]=0
from collections import deque
queue=deque([(0,0)])
d=((0,1),(0,-1),(1,0),(-1,0))
while queue:
	r=queue.popleft()
	for x in d:
		xx=r[0]+x[0];yy=r[1]+x[1]
		if 0<=xx<h and 0<=yy<w:
			if s[xx][yy]=="." and dp[xx][yy]==inf:
				dp[xx][yy]=dp[r[0]][r[1]]+1
				queue.append((xx,yy))
if dp[-1][-1]==inf:
	print(-1)
	exit()
print(cnt-dp[-1][-1]-1)

Submission status: Accepted

Solution code:

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

s = []
bl = 0

for i in range(H):

    tmp = list(input())
    s.append(tmp)

for i in range(H):

    for j in range(W):

        if s[i][j] == "#":
            bl += 1

d = [[float("inf")] * W for i in range(H)]
d[0][0] = 1

from collections import deque
q = deque([(0,0)])

while len(q) > 0:

    now = q.popleft()
    x,y = now

    if s[x][y] == "#":
        continue

    if x != 0 and d[x-1][y] > d[x][y] + 1:
        d[x-1][y] = d[x][y] + 1
        q.append( (x-1,y) )

    if x != H-1 and d[x+1][y] > d[x][y] + 1:
        d[x+1][y] = d[x][y] + 1
        q.append( (x+1,y) )

    if y != 0 and d[x][y-1] > d[x][y] + 1:
        d[x][y-1] = d[x][y] + 1
        q.append( (x,y-1) )

    if y != W-1 and d[x][y+1] > d[x][y] + 1:
        d[x][y+1] = d[x][y] + 1
        q.append( (x,y+1) )

if d[-1][-1] == float("inf"):
    print (-1)
else:
    print (H*W - bl - d[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque

H, W = list(map(int,input().split()))
s = []
for i in range(H):
    s.append(input())
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
sx, sy = 0, 0
gx, gy = W - 1, H - 1

def bfs():
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        if x == gx and y == gy:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "#" and d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d[gy][gx]
                
ret = bfs()   

count = 0
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            count += 1           
        
ans = H * W - (ret - 1) - count - 2
if ret == -1:
  	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
count_dot = 0
dist = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if map[i][j] == '.':
      count_dot +=1
def bfs():
  while q:
    x,y = q.popleft()
    if x == H-1 and y ==W-1:
      break
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < H and 0 <= ny < W and map[nx][ny]=='.' and dist[nx][ny] == 0:
        q.append((nx,ny))
        dist[nx][ny] = dist[x][y] + 1
q = deque()
q.append((0,0))
bfs()
dist_min = dist[H-1][W-1]
if dist_min ==0:
  print(-1)
else:
  print(count_dot-dist_min-1)

Submission status: Accepted

Solution code:
from collections import deque

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

maze = []
white_count = 0
for _ in range(H):
    line = list(input())
    white_count += line.count('.')
    maze.append(line)

queue = deque()
queue.append((0, 0, 1))

min_step = -1
while len(queue) > 0:
    y, x, step = queue.popleft()
    if maze[y][x] != '.':
        continue
    else:
        maze[y][x] = '#'

    if y == H - 1 and x == W - 1:
        min_step = step
        break

    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx

        if 0 <= ny < H and 0 <= nx < W:
            queue.append((ny, nx, step + 1))

if min_step == -1:
    print(min_step)
else:
    print(white_count - min_step)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
ttt=0
d=["#"]
c=[]
for i in range(h):
    ca=input()
    ttt+=ca.count("#")
    ca=list(ca)
    b=["#"]
    b.extend(ca)
    b.extend(d)
    c.append(b)
c.insert(0,['#']*(w+2))
c.append(['#']*(w+2))
# print(a,c)

kouho=deque([[1,1]])
kouho2=deque([])
ans=0
for _ in range(10**9):
    if kouho==deque([]):
        ans+=1
        if kouho2==deque([]):
            print(-1)
            exit()
        kouho=kouho2
        # print(kouho,ans)
        kouho2=deque([])
    a,b=kouho.popleft()
    # print(a,b)
    if a==h and b==w:
        print(h*w-ans-1-ttt)
        exit()
    if c[a][b]=='.':
        c[a][b]='#'
        kouho2.append([a,b-1])
        kouho2.append([a-1,b])
        kouho2.append([a+1,b])
        kouho2.append([a,b+1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    def bfs(current):
        q = deque()
        q.append([current, 1])
        while q:
            (x, y), dist = q.popleft()
            if x == h and y == w:
                return dist
            if not visited[x][y]:
                visited[x][y] = True
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if expanded_grid[nx][ny] == '.' and not visited[nx][ny]:
                        q.append([(nx, ny), dist+1])
        return 0

        

    
    h, w = mi()
    grid = [input() for _ in range(h)]
    expanded_grid = []
    expanded_grid.append('#' * (w + 2))
    for line in grid:
        expanded_grid.append('#' + line + '#')
    expanded_grid.append('#' * (w + 2))

    visited = [[False] * (w + 2) for _ in range(h + 2)]

    initial_black = sum([line.count('#') for line in grid])
    d = bfs((1, 1))
    if d > 0:
        print(h*w - d - initial_black)
    else:
        print(-1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10**9
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
h, w = map(int, input().split())
s = [input() for _ in range(h)]
def conv_coor(i, j):
    return i*w+j
def update(i, j, d,  q):
    if dist[conv_coor(i, j)] != INF:
        return
    dist[conv_coor(i, j)] = d
    q.append((i, j))

dist = [INF]*h*w
dist[0] = 0
q = [(0,0)]
while len(q) > 0:
    current = q.pop(0)
    i = current[0]
    j = current[1]
    for direction in range(4):
        ni = i + di[direction]
        nj = j + dj[direction]
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if s[ni][nj] == "#":
            continue
        d = dist[conv_coor(i, j)]
        update(ni, nj, d+1, q)
if dist[conv_coor(h-1,w-1)] == INF:
    print(-1)
    exit()
b_num = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            b_num += 1
print(h*w-b_num-dist[conv_coor(h-1, w-1)]-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
m = []
count = 0
for i in range(H):
    s = input()
    count += s.count('.')
    m.append(list(s))

que = [(0,0)]
keiro = {}
keiro[(0,0)] = 1
# print(m)
while que:
    h, w = que.pop(0)
    # print(h,w)
    if h+1 < H:
        if m[h+1][w] == '.':
            if (h+1,w) in keiro:
                keiro[(h+1,w)] = min(keiro[(h+1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h+1,w)] = keiro[(h,w)]+1
                que.append((h+1,w))
    if w+1 < W:
        if m[h][w+1] == '.':
            if (h,w+1) in keiro:
                keiro[(h,w+1)] = min(keiro[(h,w+1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w+1)] = keiro[(h,w)]+1
                que.append((h,w+1))
    if h-1 >= 0:
        if m[h-1][w] == '.':
            if (h-1,w) in keiro:
                keiro[(h-1,w)] = min(keiro[(h-1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h-1,w)] = keiro[(h,w)]+1
                que.append((h-1,w))
    if w-1 >= 0:
        if m[h][w-1] == '.':
            if (h,w-1) in keiro:
                keiro[(h,w-1)] = min(keiro[(h,w-1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w-1)] = keiro[(h,w)]+1
                que.append((h,w-1))

if (H-1,W-1) in keiro:
    print(count-keiro[(H-1,W-1)])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

INF = 10**10
dist = [[INF for _ in range(w)] for _ in range(h)]
dist[0][0] = 0

DX = [0, 0, 1, -1]
DY = [1, -1, 0, 0]

def bfs(sx, sy):
    d = deque([[sx, sy]])
    while len(d) > 0:
        x, y = d.popleft()
        for dx, dy in zip(DX, DY):
            nx = x+dx; ny = y+dy
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == "." and dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    d.append([nx, ny])

bfs(0, 0)

if dist[h-1][w-1] == INF:
    print(-1)
else:
    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                ans += 1
    print(ans-dist[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
white = 0
s = []
for i in range(h):
    line = list(input())
    white += len([j for j in line if j == '.'])
    s.append(line)

Q = deque([[0, 0]])
stamp = [[0]*w for _ in range(h)]

while Q:
    row, col = Q.popleft()
    for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        new_row, new_col = row+i, col+j
        if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w:
            continue
        if s[new_row][new_col] == '#' or stamp[new_row][new_col] > 0:
            continue
        stamp[new_row][new_col] = stamp[row][col] + 1
        Q.append([new_row, new_col])

if stamp[-1][-1] == 0:
    print(-1)
else:
    print(white - stamp[-1][-1] - 1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
cnt = 0
L = []
for i in range(h):
    s = input()
    cnt +=s.count("#")
    L.append(list(s))
#print(L,cnt)

d = [[-1]*w for i in range(h)]
d[0][0] = 0
from collections import deque
q = deque([[0,0]])
#print(d,q)

li = ((1,0),(0,1),(-1,0),(0,-1))

while q:
    j,i = q.popleft()
    for dy,dx in li:
        ny,nx = j+dy,i+dx
        if (ny < 0 or ny >= h) or (nx < 0 or nx >= w) or L[ny][nx] == "#":
            continue
        else:
            if d[ny][nx] == -1:
                d[ny][nx] = d[j][i] + 1
                q.append((j+dy,i+dx))

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

Submission status: Accepted

Solution code:
from collections import deque


def bfs(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if (ni, nj) not in visited and 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.':
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' for i in range(H) for j in range(W)) - len(path))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in visited:
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' for i in range(H) for j in range(W)) - len(path))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in visited:
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' and (i, j) not in path for i in range(H) for j in range(W)))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
s = [input() for i in range(H)]
Map = [[0]*W for i in range(H)]
num_b = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == '#':
      num_b += 1
      Map[i][j] = -1

dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([[0, 0]])
Map[0][0] = 1
while que:
  x, y = que.popleft()
  for dx, dy in dxy:
    xx, yy = x + dx, y + dy
    if 0<=xx<H and 0<=yy<W and Map[xx][yy] == 0:
      Map[xx][yy] = Map[x][y] + 1
      if (xx, yy) == (H-1, W-1):
        print(H*W - Map[xx][yy] - num_b)
        quit()
      que.append([xx, yy])

print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

h,w = map(int,input().split())
maze = [list(input().rstrip()) for _ in range(h)]
#print(maze)

from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = deque([])
q.append((0,0))
checked[0][0] = 1
while len(q)>0:
    pos = q.popleft()
    if pos == (h-1,w-1):
        b = (checked[h-1][w-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '#' and checked[pos[0] - 1][pos[1]] == INF:
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] - 1, pos[1]))

    if pos[0] < h - 1:
        if not maze[pos[0] + 1][pos[1]] == '#' and checked[pos[0] + 1][pos[1]] == INF:
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '#' and checked[pos[0]][pos[1] - 1] == INF:
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] - 1))

    if pos[1] < w - 1:
        if not maze[pos[0]][pos[1] + 1] == '#' and checked[pos[0]][pos[1] + 1] == INF:
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
if not b == 0:
    print(sum(a)-b)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1
def bfs():
  d = [[float('inf')]*w for i in range(h)]
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  que = deque([])
  que.append((sx, sy))
  d[sx][sy] = 0
  while que:
    p = que.popleft()
    if p[0] == gx and p[1] == gy:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == float('inf'):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gx][gy]
white = 0
for i in range(h):
  for j in range(w):
    if maze[i][j] == '.':
      white += 1
res = bfs()
if 0 < res < float('inf'):
  print(white - res - 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
q = deque([(0, 0)])
INF = 10**5
dist = [[INF]*w for _ in range(h)]
dist[0][0] = 0
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
while q:
    x, y = q.popleft()
    for dx, dy in dxdy:
        if not(0<=x+dx<w and 0<=y+dy<h):
            continue
        if s[y+dy][x+dx]=='#' or dist[y+dy][x+dx]<INF:
            continue
        dist[y+dy][x+dx] = dist[y][x] + 1
        q.append((x+dx, y+dy))
if dist[h-1][w-1]==INF:
    print(-1)
else:
    white = 0
    for r in s:
        white += r.count('.')
    print(white-dist[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
m = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
temp = [[-1]*(w+2) for i in range(h+2)]
sy,sx = 1,1
temp[sy][sx] = 0
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque([(sy,sx)])
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            dq.append((y1,x1))

cnt = 0
for i in m:
    cnt+=i.count("#")
if temp[h][w] == -1:
    print(-1)
else:
    print((h+2)*(w+2)-cnt-temp[h][w]-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s_l, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[0][0] = 0
    while q:
        y, x = q.popleft()
        if [y, x] == [gy, gx]:
            return visited[gy][gx]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y, n_x = y+j, x+k
            if n_y >= h or n_x >= w or n_y < 0 or n_x < 0:
                continue
            if s_l[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x] + 1
                q.append([n_y,n_x])
    return -1

def main():
    h, w = map(int, input().split()) 
    s_l = []
    all_dot_cnt = 0
    for i in range(h):
        row = list(input())
        s_l.append(row)
        all_dot_cnt += row.count('.')
    
    visited = [ [-1]*w for i in range(h)]
    res = bfs(s_l, visited, 0, 0, h-1, w-1, h, w)
    if res == -1:
        print(-1)
    else:
        # print(res)
        # print(all_dot_cnt)
        print(all_dot_cnt-res-1)

if __name__ == "__main__":
    main()