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:
H,W=map(int,input().split())
sq=[list(input()) for i in range(H)]
ans=False
c=H*W
pos=[[0,0,0]]

while pos!=[]:
    y,x,depth=pos.pop(0)

    if x==W-1 and y==H-1:
        ans=True
        break

    if 0<=x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
            
    if 0<=x-1<=W-1:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
            
    if 0<=y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])
            sq[y+1][x]="!"
            
    if 0<=y-1<=H-1:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    
    
for j in range(H):
    for k in range(W):
        if sq[j][k]=="#":
            c-=1

if ans==True:
    print(c-depth-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
queue=deque()
s=[list(input()) for _ in range(h)]
seen=[[False]*w for _ in range(h)]
queue.append([0,0])
ans=[[1000000000]*w for _ in range(h)]
seen[0][0]=True
ans[0][0]=1
for i in range(h*w*10):
    if len(queue)==0:
        break
    cnt=queue.popleft()
    if cnt[0]!=0:
        if seen[cnt[0]-1][cnt[1]]==False and s[cnt[0]-1][cnt[1]]==".":
            queue.append([cnt[0]-1,cnt[1]])
            ans[cnt[0]-1][cnt[1]]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]-1][cnt[1]]=True
    if cnt[1]!=0:
        if seen[cnt[0]][cnt[1]-1]==False and s[cnt[0]][cnt[1]-1]==".":
            queue.append([cnt[0],cnt[1]-1])
            ans[cnt[0]][cnt[1]-1]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]][cnt[1]-1]=True
    if cnt[0]!=h-1:
        if seen[cnt[0]+1][cnt[1]]==False and s[cnt[0]+1][cnt[1]]==".":
            queue.append([cnt[0]+1,cnt[1]])
            ans[cnt[0]+1][cnt[1]]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]+1][cnt[1]]=True
    if cnt[1]!=w-1:
        if seen[cnt[0]][cnt[1]+1]==False and s[cnt[0]][cnt[1]+1]==".":
            queue.append([cnt[0],cnt[1]+1])
            ans[cnt[0]][cnt[1]+1]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]][cnt[1]+1]=True
cnt2=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            cnt2+=1
if seen[-1][-1]==False:
    print(-1)
else:
    print(cnt2-ans[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	h,w=MI()
	G=[]
	G+=["#"]*(w+2)
	for _ in range(h):
		G+=["#"]+list(RD())+["#"]
	G+=["#"]*(w+2)

	cnt=G.count(".")


	Q=deque()
	Q.append([w+3,1])
	G[w+3]=1

	while Q:
		now,d=Q.popleft()
		for i in [1,-1,w+2,-w-2]:
			if G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])

	ans=-1
	if G[(w+2)*(h+2)-(w+4)]!=".":
		ans=cnt-G[(w+2)*(h+2)-(w+4)]

	print(ans)












if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start, goal):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == goal:
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                continue
            if (ni, nj) not in visited:
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))
    return []


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0), (H - 1, W - 1))
if shortest_path:
    print(sum(v == "." for row in field for v in row) - len(shortest_path))
else:
    print(-1)

Submission status: Accepted

Solution code:
t,*g=open(0);h,w=map(int,t.split());v=[[0]*w for _ in range(h)];v[0][0]=1;q=[(0,0)]
while q:
	a,b=q.pop(0)
	for c,d in((-1,0),(0,-1),(1,0),(0,1)):
		x=a+c;y=b+d
		if w>x>=0<=y<h and v[y][x]<1 and g[y][x]==".":q+=[(x,y)];v[y][x]=v[b][a]+1
t=v[-1][-1];print((-1,sum(c.count(".")for c in g)-t)[t>0])

Submission status: Accepted

Solution code:
from collections import deque


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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


# 色を変える前のマップ上の白色マスを数える
def count_white():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '.':
                res += 1
    return res


# 色を変えずにスタートからゴールまでの最短歩数を数える
def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    # BFS
    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '#':
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(count_white() - step if step else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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


# 色を変える前のマップ上の黒色マスを数える
def count_black():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '#':
                res += 1
    return res


# 色を変えずにスタートからゴールまでの最短歩数を数える
def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    # BFS
    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '#':
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(H * W - step - count_black() if step else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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


def count_black():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '#':
                res += 1
    return res


def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '#':
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(H * W - step - count_black() if step else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


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


def LSH(h):
    return [list(input()) for _ in range(h)]


H, W = LI()
MAP = LSH(H)
d = deque()
d.append([0, 0])
looked = [[0 for i in range(W)]for j in range(H)]
looked[0][0] = 1
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    x = d.popleft()
    h = x[0]
    w = x[1]
    for i in move:
        a = h+i[0]
        b = w+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or looked[a][b] != 0 or MAP[a][b] == "#":
            continue
        d.append([a, b])
        looked[a][b] = looked[h][w]+1
if looked[H-1][W-1] == 0:
    print(-1)
    sys.exit()

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

print(white-looked[H-1][W-1])

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
h,w = readInts()
block = [input() for _ in range(h)]

allcnt = 0
for i in range(w):
    for j in range(h):
        if block[j][i] == '.':
            allcnt += 1
INF = float('inf')
AR = [[INF] * w for _ in range(h)]
dy = [1,0,0,-1]
dx = [0,-1,1,0]
def bfs():
    d = deque()
    d.append([0,0])
    while d:
        y,x = d.popleft()
        if y == 0 and x == 0:
            AR[y][x] = 0
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (not 0 <= ny < h) or (not 0 <= nx < w):
                continue
            if AR[ny][nx] == INF and block[ny][nx] != '#':
                AR[ny][nx] = AR[y][x] + 1
                d.append([ny,nx])
bfs()
if AR[h-1][w-1] == INF:
    print(-1)
else:
    print(allcnt - (AR[h-1][w-1]+1)) # start地点の分

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
t = [[-1]*W for _ in range(H)]
q = deque([[0,0]])
t[0][0] = 0
while len(q) > 0:
  qq = q.popleft()
  dh = [-1,0,1,0]
  dw = [0,1,0,-1]
  for i in range(4):
    h = qq[0] + dh[i]
    w = qq[1] + dw[i]
    if 0 <= h < H and 0 <= w < W:
      if s[h][w] == "#" or t[h][w] != -1: continue
      t[h][w] = t[qq[0]][qq[1]] + 1
      q.append([h,w])

X = 0
for i in range(H):
  c = Counter(s[i])
  X += c["."]
if t[H-1][W-1] == -1:
  print(-1)
else:
  print(X-1-t[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == (H - 1, W - 1):
            return path
        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
            ):
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0))
if shortest_path is None:
    print(-1)
    exit()
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == "." and (i, j) not in shortest_path:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

h,w = MI()
maze = LS(h)
sy = 1
sx = 1
gy = h
gx = w
sy -= 1
sx -= 1
gy -= 1
gx -= 1

d = [ [INF]*w for _ in range(h) ]

def bfs(sy,sx,gy,gx):
    q = deque()
    q.append([sy,sx])
    d[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y==gy and x==gx:
            break
        else:
            for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
                ny = y + j
                nx = x + i
                if nx==-1 or ny==-1 or nx==w or ny==h:
                    pass
                elif maze[ny][nx]=="#":
                    pass
                elif d[ny][nx]!=INF:
                    pass
                else:
                    q.append([ny,nx])
                    d[ny][nx] = d[y][x] + 1
    return d[gy][gx]

count = 0
for i in range(h):
    c = maze[i].count('.')
    count += c

d = bfs(sy,sx,gy,gx) 
# print(f'd={d}')  
if d==INF:
    print('-1')
else:
    print(count-2-(d-1))

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
dist = [[-1 for _ in range(W)] for _ in range(H)]
que = deque([(0,0,0)])
dist[0][0] = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and S[i][j+1]=="." and dist[i][j+1]<0:
        dist[i][j+1] = d+1
        que.append((i,j+1,d+1))
    if i-1>=0 and S[i-1][j]=="." and dist[i-1][j]<0:
        dist[i-1][j]=d+1
        que.append((i-1,j,d+1))
    if j-1>=0 and S[i][j-1]=="." and dist[i][j-1]<0:
        dist[i][j-1]=d+1
        que.append((i,j-1,d+1))
    if i+1<H and S[i+1][j]=="." and dist[i+1][j]<0:
        dist[i+1][j]=d+1
        que.append((i+1,j,d+1))
dmin = dist[H-1][W-1]
if dmin<0:
    print(-1)
else:
    B = H*W-dmin-1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                cnt += 1
    print(B-cnt)

Submission status: Accepted

Solution code:
import numpy as np

h, w, *s = open(0).read().split()
h = int(h)
w = int(w)
all = sum(t.count('#') for t in s)

inf = 1 << 30
d = np.full((h + 1, w + 1), inf, dtype=np.int)

d[0][0] = 0
q = [(0, 0)]
for v in q:
    for nv in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        ny = v[0] + nv[0]
        nx = v[1] + nv[1]
        if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == inf and s[ny][nx] == '.':
            d[ny][nx] = d[v[0]][v[1]] + 1
            q.append((ny, nx))

if d[h - 1][w - 1] == inf:
    print(-1)
else:
    print(h * w - (d[h - 1][w - 1] + 1) - all)

Submission status: Accepted

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

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

M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

sy, sx = 1, 1

from collections import deque
stack = deque()
stack.append((sy, sx))
visit = [[-1]*(w+2) for _ in range(h+2)]
visit[sy][sx] = 0

while stack:
    y, x = stack.popleft()
    if y == h and x == w:
        break
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        new_y, new_x = y+dy, x+dx
        if visit[new_y][new_x] == -1 and M[new_y][new_x] != '#':
            visit[new_y][new_x] = visit[y][x]+1
            stack.append((new_y, new_x))
else:
    print(-1)
    exit()

print(cnt-(visit[h][w]+1))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
import numpy as np
Grid = np.array([[0 if x == '.' else -1 for x in input()] for _ in range(H)],dtype='int64')

def solveMase(Grid, start, goal): #bfsで迷路を解き、スタート-ゴール間の最低必要白マス数を返す
    seen = {start}
    V = [start]
    while len(V) != 0: #bfs
        v = V.pop(0)
        if v == goal:
            return Grid[goal]
        #移動先nvをリストにまとめる
        y,x = v
        nV = []
        if x > 0: nV.append((y,x-1))
        if y > 0: nV.append((y-1,x))
        if x < W-1: nV.append((y,x+1))
        if y < H-1: nV.append((y+1,x))
        #bfs
        for nv in nV:
            if Grid[nv] == -1 or nv in seen:
                continue
            Grid[nv] = Grid[v] + 1
            V.append(nv)
            seen.add(nv)
    return 0

white = len(Grid[Grid == 0])-1
nes_white = solveMase(Grid, (0,0), (H-1,W-1))
print(white-nes_white if nes_white > 0 else -1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
import numpy as np
Grid = np.array([[0 if x == '.' else -1 for x in input()] for _ in range(H)],dtype='int64')

def solveMase(Grid, start, goal):
    seen = {start}
    V = [start]
    while len(V) != 0:
        v = V.pop(0)
        if v == goal:
            return Grid[goal]

        y,x = v
        nV = []
        if x > 0: nV.append((y,x-1))
        if y > 0: nV.append((y-1,x))
        if x < W-1: nV.append((y,x+1))
        if y < H-1: nV.append((y+1,x))

        for nv in nV:
            if Grid[nv] == -1 or nv in seen:
                continue
            Grid[nv] = Grid[v] + 1
            V.append(nv)
            seen.add(nv)
    return 0

white = len(Grid[Grid == 0])-1
nes_white = solveMase(Grid, (0,0), (H-1,W-1))
if nes_white > 0:
    ans = white - nes_white
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    from collections import deque
    H, W = map(int,input().split())
    s = []
    black = 0
    for _ in range(H):
        t = list(input())
        for c in t:
            if c == "#":
                black += 1
        s.append(t)
    q = deque([(0,0,1)])
    s[0][0] = "#"
    while q:
        x,y,d = q.popleft()
        if x == H-1 and y == W-1:
            print(H*W-d-black)
            exit(0)
        for nx,ny in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)]:
            if 0 <= nx < H and 0<= ny < W and s[nx][ny] == ".":
                s[nx][ny] = "#"
                q.append((nx,ny,d+1))
    print(-1)

Submission status: Accepted

Solution code:
import queue
h, w = map(int, input().split())
s = []
black_num = 0
for i in range(h):
    s_ij = input()
    s.append(s_ij)
    for j in range(w):
        if s_ij[j] == "#":
            black_num += 1

already_pass = set()
already_pass.add((1, 1))
q = queue.Queue()
q.put([(1, 1), 1])

while not q.empty():
    x_y, l = q.get()
    x = x_y[0]
    y = x_y[1]
    if x == h and y == w:
        print(h * w - black_num - l)
        break
    next_xy = [(max(1, x - 1), y), (min(h, x + 1), y),
               (x, max(1, y - 1)), (x, min(w, y + 1))]
    for i in next_xy:
        if i not in already_pass and s[i[0] - 1][i[1] - 1] != "#":
            q.put([i, l + 1])
            already_pass.add(i)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


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]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1

# 白いマスを数える
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 = list(map(int, input().split()))

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

c = 0

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

#DFS
q = deque([[0, 0]])
dist = [[10000] * w for _ in range(h)]
dist[0][0] = 0

flag = False

while len(q) > 0:
    i, j = q.popleft()
    if i == h-1 and j == w-1:
        break
    else:
        if i < h-1 and s[i+1][j] == "." and not dist[i+1][j] < 10000:
            q.append([i+1, j])
            dist[i+1][j] = dist[i][j] + 1
        if j < w-1 and s[i][j+1] == "." and not dist[i][j+1] < 10000:
            q.append([i, j+1])
            dist[i][j+1] = dist[i][j] + 1
        if i > 0 and s[i-1][j] == "." and not dist[i-1][j] < 10000:
            q.append([i-1, j])
            dist[i-1][j] = dist[i][j] + 1
        if j > 0 and s[i][j-1] == "." and not dist[i][j-1] < 10000:
            q.append([i, j-1])
            dist[i][j-1] = dist[i][j] + 1

if dist[h-1][w-1] < 10000:
    print(h * w - dist[h-1][w-1] - 1 - c)
else:
    print(-1)

Submission status: Accepted

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

from collections import deque
def bfs(h,w,sy,sx,gy,gx,S):
    maze=[[10**9]*(W)for _ in range(H)]
    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    return maze[gy-1][gx-1]+1

A=0
for s in S:
    A+=s.count('.')

B=bfs(H,W,1,1,H,W,S)
if B>10**9:
    ans=-1
else:
    ans=A-B
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

Y, X = map(int, input().split())
Map = list(input() for _ in range(Y))

def bfs(sy, sx, gy, gx):
    seen = list([-1]*X for _ in range(Y))
    queue = deque()
    queue.append((sy, sx))
    seen[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        search_around(y, x, seen, queue)
        if seen[gy][gx] > 0:
            return seen[gy][gx]

def search_around(y, x, seen, queue):
    count = seen[y][x]
    for u,t in [(y-1,x), (y+1,x), (y,x-1), (y,x+1)]:
        if u < 0 or t < 0 or u >= Y or t >= X:
            continue
        elif Map[u][t] == '#' or seen[u][t] != -1:
            continue
        queue.append((u, t))
        seen[u][t] = count + 1
        
cnt = 0
for M in Map:
    for m in M:
        if m == '#':
            cnt += 1

b = bfs(0,0,Y-1,X-1)
if b == None:
    print(-1)
else:
    print(Y*X - cnt - b - 1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
mp=[['#']*(W+2)]
count=0
for _ in range(H):
    l=list(input())
    mp.append(['#']+l+['#'])
    count+=l.count('.')
mp.append(['#']*(W+2))

dist=[[-1]*(W+2)for _ in range(H+2)]
Q=deque()
Q.append((1,1))
dist[1][1]=1
f=False

while Q:
    y,x=Q.popleft()
    if (y,x)==(H,W):
        f=True
        break
    for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<H+2 and 0<=nx<W+2:
            if mp[ny][nx]=='.' and dist[ny][nx]==-1:
                Q.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1

if f:
    print(count-dist[H][W])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = list(map(int, input().split()))
S = [['#']*(W+2)]
for _ in range(H):
    S.append(list('#' + input() + '#'))
S.append(['#']*(W+2))

mv=[(0,-1),(0,1),(-1,0),(1,0)]
INF = H*W
depth = [[INF]*(W+2) for _ in range(H+2)]
depth[1][1] = 0
stk = deque([[1, 1]])
while len(stk)>0:
    l = stk.pop()
    # print(l)
    x = l[0]
    y = l[1]
    ct = depth[x][y]
    for i, j in mv:
        nx=x+i
        ny=y+j
        if 1<=nx<=H and 1<=ny<=W and S[nx][ny]=='.' and depth[nx][ny]==INF:
            stk.appendleft([nx,ny])
            depth[nx][ny]=ct+1
# print(depth)
if depth[H][W]==INF:
    print(-1)
else:
    dots=0
    for i in range(1,H+1):
        dots+=S[i].count('.')
    # print(dots)
    print(dots-depth[H][W]-1)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
q.append((0, 0, 0))
check = [[0]*w for _ in range(h)]

flag = False
while q:
    y, x, d = q.popleft()
    if y == h-1 and x == w-1:
        g = d
        flag = True
        break
    if check[y][x] == 0:
        check[y][x] = 1
        for xdx, ydy in zip((x, x, x+1, x-1), (y+1, y-1, y, y)):
            if (0 <= xdx < w) and (0 <= ydy < h):
                if check[ydy][xdx] == 0 and s[ydy][xdx] == '.':
                    q.append((ydy, xdx, d+1))
ss = 0
for i in s:
    ss += i.count('#')
print(h*w-ss-d-1 if flag else -1)

Submission status: Accepted

Solution code:
from collections import deque

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

mazo = [list(input()) for _ in range(H)]

cnt = 0 #初期状態の黒の数を数える
for i in range(H):
    for j in range(W):
        if mazo[i][j] == "#":
            cnt += 1

d = deque()
d.append((0,0))

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

visited = [[0]*W for _ in range(H)]

flg = False
while d:
    y, x = d.popleft()
    if (y==H-1) and (x==W-1):
        flg = True
        break

    for u, v in move:
        t = y + u
        s = x + v
        if 0 <= t and t<H and 0<=s and s<W and mazo[t][s]=="." and visited[t][s]==0:
            visited[t][s] = visited[y][x] + 1
            d.append((t, s))

if flg:
    print(H*W - cnt - visited[H-1][W-1] -1)
else:
    print(-1)

Submission status: Accepted

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

def get_next(x, y, costs, S, cost):
    ans = list()
    if x != 0 and costs[x-1][y] == -1 and S[x-1][y] == ".":
        ans.append([x-1, y])
        costs[x-1][y] = cost + 1

    if x != H-1 and costs[x+1][y] == -1 and S[x+1][y] == ".":
        ans.append([x+1, y])
        costs[x+1][y] = cost + 1

    if y != 0 and costs[x][y-1] == -1 and S[x][y-1] == ".":
        ans.append([x, y-1])
        costs[x][y-1] = cost + 1

    if y != W-1 and costs[x][y+1] == -1 and S[x][y+1] == ".":
        ans.append([x, y+1])
        costs[x][y+1] = cost + 1

    return ans

costs = [[-1 for _ in range(W)] for _ in range(H)]
costs[0][0] = 0
q = deque()
q.append([0, 0])
while len(q) and costs[H-1][W-1] == -1:
    now = q.popleft()
    nxt = get_next(now[0], now[1], costs, S, costs[now[0]][now[1]])
    for dot in nxt:
        q.append([dot[0], dot[1]])
    
fin_cost = costs[H-1][W-1]
if fin_cost == -1:
    print(-1)
else:
    w_cnt = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                w_cnt += 1
    print(w_cnt - fin_cost - 1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
C=list(list(input()) for _ in range(H))

def bfs():
	sx, sy= 0, 0
	gx, gy= H-1, W-1
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]

	work_queue=deque([])
	work_queue.append((sx, sy))
	visited=[[float("inf")]*W for _ in range(H)]
	visited[sx][sy]=1

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

		for i in range(4):
			nx, ny = x+dx[i], y+dy[i]

			if 0<=nx<H and 0<=ny<W and visited[nx][ny]==float("inf") and C[nx][ny]!="#":
				work_queue.append((nx, ny))
				visited[nx][ny]= visited[x][y]+1
	return visited[gx][gy]


temp=bfs()

black=0
white=0
for i in range(H):
	for j in range(W):
		if C[i][j]==".":
			white+=1
		else:
			black+=1

if temp==float("inf"):
	print(-1)
else:
	print(white-temp)