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())
grid = []
for _ in range(H):
  grid.append(input())

def get_adj(pos):
  ans = []
  for v in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    adj = (pos[0] + v[0], pos[1] + v[1])
    if adj[0] >= 0 and adj[0] < H and adj[1] >= 0 and adj[1] < W:
      ans.append(adj)
  return ans

start = (0, 0)
goal = (H-1, W-1)

q = deque()
q.append((start, 1))
visited = {}

while q:
  pos, dist = q.popleft()
  if grid[pos[0]][pos[1]] == '#':
    continue
  if pos in visited:
    continue
  visited[pos] = dist
  if pos == goal:
    break
  for adj in get_adj(pos):
    q.append((adj, dist+1))

cnt_walls = sum([row.count('#') for row in grid])

if goal in visited:
  print(H*W-visited[goal]-cnt_walls)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque 

R,W = map(int,input().split())
sy,sx = 1,1
gy,gx = R,W
C = [list(input()) for i in range(0,R,1)]

task_list = deque([])
ans = 0

siro = 0
for i in range(R):
    for j in range(W):
        if C[i][j]==".":
            siro += 1
def bfs(y,x,count):#関数にしない方がわかりやすいかも

    if x==gx-1 and y==gy-1:
        return True

    if x < 0 or  W <= x or y < 0 or R <= y:
        return False
    if C[y][x]=="#":
        return False#何もしない
    if C[y][x]==".":
        C[y][x]="#"
        task_list.append([y+1,x,count+1])
        task_list.append([y-1,x,count+1])
        task_list.append([y,x-1,count+1])
        task_list.append([y,x+1,count+1])
    

task_list.append([sy-1,sx-1,0])
ok = False
while(len(task_list)):
    y,x,t = task_list.popleft()
    ans = t
    if bfs(y,x,t):
        ok = True
        break
print(siro-1-ans if ok else -1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()
st.append([0,0,0])


d=[[0,1],[-1,0],[1,0],[0,-1]]
while st:
  h1,w1,i=st.popleft()

  if 0<=h1<h and 0<=w1<w and vi[h1][w1]==-1 and s[h1][w1]==".":
    vi[h1][w1]=i+1
    for m in d:
      st.append([h1+m[0],w1+m[1],i+1])

print("".join(s).count(".")-vi[h-1][w-1] if vi[h-1][w-1]!=-1 else -1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()
st.append([0,0,1])
vi[0][0]=1
while st:
  h1,w1,i=st.popleft()
  d=[[0,1],[-1,0],[1,0],[0,-1]]
  for m in d:
    if h1+m[0]==h-1 and w1+m[1]==w-1:
      vi[h-1][w-1]=i+1
      st.clear()
    if 0<=h1+m[0]<h and 0<=w1+m[1]<w:
      if vi[h1+m[0]][w1+m[1]]==-1 and s[h1+m[0]][w1+m[1]]==".":
        st.append([h1+m[0],w1+m[1],i+1])
        vi[h1+m[0]][w1+m[1]]=i+1

print("".join(s).count(".")-vi[h-1][w-1] if vi[h-1][w-1]!=-1 else -1)

Submission status: Accepted

Solution code:
from collections import deque

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


#白マス数える
white=0
for i in range(h):
    for j in range(w):
        if G[i][j]=='.':
            white+=1


def sur(v):
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy+1),(vx,vy-1)]
    E=[]
    for nv in preE:
        if 0<=nv[0]<=h-1 and 0<=nv[1]<=w-1:
            if G[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

#bfs
dist=[[0]*w for i in range(h)]
q=deque()

dist[0][0]=1
q.append((0,0))
while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]>0:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1

        if next==(h-1,w-1):
            print(white-dist[h-1][w-1])
            break
    else:
        continue
    break
else:
    print(-1)

Submission status: Accepted

Solution code:
import copy
h,w = map(int,input().split())
g = [[False]*(w+2) for _ in range(h+2)]
d = [[-1]*(w+2) for _ in range(h+2)]
ans = 0
for i in range(h):
    l = list(input())
    for j in range(w):
        if l[j] == ".":
            ans += 1
            g[i+1][j+1] = True
def f(i,j):
    return [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
now = f(1,1)
d[1][1] = 0
nxt = []
cnt = 1
while now:
    for l in now:
        i,j = l[0],l[1]
        if d[i][j] == -1 and g[i][j]:
            d[i][j] = cnt
            for l2 in f(i,j):
                nxt.append(l2)
    cnt += 1
    now = copy.copy(nxt)
    nxt = []
if d[h][w] == -1:
    print(-1)
else:
    print(ans-d[h][w]-1)

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    maze=["#"*(w+2)]+["#"+input()+"#" for _ in range(h)]+["#"*(w+2)]
    total_white=sum([row.count(".") for row in maze])

    seen=[[-1]*(w+2) for _ in range(h+2)]
    if maze[1][1]=="#" : print(-1);exit()
    seen[1][1]=1
    token=1
    bfs_new=[(1,1)]

    while bfs_new:
        token+=1
        bfs_old=bfs_new[:]
        bfs_new=[]
        for x in bfs_old:
            for move in [(1,0),(-1,0),(0,1),(0,-1)]:
                ywork=x[0]+move[0]
                xwork=x[1]+move[1]
                if maze[ywork][xwork]=="#" : continue
                if seen[ywork][xwork]>=0 : continue
                seen[ywork][xwork]=token
                bfs_new.append((ywork,xwork))
    
    if seen[h][w]==-1 : print(-1)
    else : print(total_white-seen[h][w])

main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
white_count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            white_count += 1

d = [[float("inf")] * w for _ in range(h)]

que = deque()
que.append((0, 0))
d[0][0] = 1
while que:
    x, y = que.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and s[ny][nx] == '.' and d[ny][nx] == float("inf"):
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1

res = d[h-1][w-1]
if res == float("inf"):
    print(-1)
else:
    print(white_count - res)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
 
    return d[gy][gx]

h, w = MAP()
s = [input() for i in range(h)]
sy = sx = 0
gy, gx = h-1, w-1

if bfs() == inf:
    ans = -1
else:
    count = 0
    for i in range(h):
        count += s[i].count('#')
    ans = h*w - bfs() - 1 - count

print(ans)

Submission status: Accepted

Solution code:
def conv(S,index,c):
	lstS = list(S)
	lstS[index] = c
	S = ''.join(lstS)

	return S


def DFS(stack,MAP,size,count,goal):
	ret = -1
	newstack = []
	for p in stack:
		if p == goal:
			ret = count
		elif ret == -1:
			y = p[0]
			x = p[1]
			Y = size[0]-1
			X = size[1]-1
			if y != 0:
				if MAP[y-1][x] == '.':
					MAP[y-1] = conv(MAP[y-1],x,'*')
					newstack.append([y-1,x])
			if y != Y:
				if MAP[y+1][x] == '.':
					MAP[y+1] = conv(MAP[y+1],x,'*')
					newstack.append([y+1,x])
			if x != 0:
				if MAP[y][x-1] == '.':
					MAP[y] = conv(MAP[y],x-1,'*')
					newstack.append([y,x-1])
			if x != X:
				if MAP[y][x+1] == '.':
					MAP[y] = conv(MAP[y],x+1,'*')
					newstack.append([y,x+1])
	
	if ret == -1:
		if len(newstack) == 0:
			ret = -1
		else:
			ret = DFS(newstack,MAP,size,count+1,goal)

	return ret


if __name__ == '__main__':
	H, W = map(int, input().split())

	MAP = []
	black = 0

	for y in range(H):
		IN = input() 
		MAP.append(IN)
		black += IN.count('#')

	step = DFS([[0,0]],MAP,[H,W],0,[H-1,W-1])

	if step == -1:
		ans = -1
	else:
		ans = H*W - step - 1 - black

	print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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



def bfs(maze,maze_s,sy,sx):
  maze_s[sy][sx] = 0
  queue = deque([[sy,sx]])
  while queue:
    y,x = queue.popleft()
    if maze[y][x] == "g":
      return maze_s[y][x]
    else:
      for j,k in [(0,1),(0,-1),(1,0),(-1,0)]:
        new_y,new_x = y+j, x+k
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
          if maze[new_y][new_x] != "#" and maze_s[new_y][new_x] == -1:
            maze_s[new_y][new_x] = maze_s[y][x] + 1
            queue.append([new_y,new_x])
  else:
    print(-1)
    exit()

maze_s = list([-1] * W for i in range(H))
count = 0
for row in maze:
  count += row.count(".")

maze[H-1][W-1] = "g"

ans = count - bfs(maze,maze_s,0,0) -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    Map = []
    Visited = [[False for j in range(w)]for i in range(h)]
    DYDX = [[0,1],[1,0],[0,-1],[-1,0]]
    white = 0
    black = 0
    for i in range(h):
        tmp = [i for i in input()]
        white += tmp.count('.')
        black += tmp.count('#')
        #print(tmp)
        Map.append(tmp)
    q = deque()
    q.append((0,0,0))
    ans = 0
    while q:
        y,x,cnt = q.popleft()
        if y<0 or y>=h or x<0 or x>=w:
            continue
        if Visited[y][x]:
            continue
        if Map[y][x]=='#':
            continue
        if y==h-1 and x==w-1:
            ans = cnt
            break
        Visited[y][x] = True
        cnt += 1
        for dy,dx in DYDX:
            q.append((y+dy,x+dx,cnt))
    if ans == 0:
        print('-1')
    else:
        print(white-ans-1) 

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque
def cango(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
    
q = deque([(-1,-1,0,0,0)]) 
been = [[False]*W for _ in range(H)]

reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.popleft()
    
    cand = cango(x_now,y_now)
    
    if x_now==H-1 and y_now==W-1:
        reach=True
        break
    
    for x_new,y_new in cand:
        if not been[x_new][y_new] and s[x_new][y_new]==".":
            q.append((x_now,y_now,x_new,y_new,time+1))
            been[x_new][y_new]=True
if reach:
    print( sum(ss.count(".") for ss in s)-time-1 )
else:
    print(-1)

Submission status: Accepted

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

vist=[[0]*W  for i in range(H)]
dxdy=[[-1,0],[1,0],[0,-1],[0,1]]

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


ans=0

while len(d)>0:
    a=d.popleft()
    x,y,z=a[0],a[1],a[2]

    if x==H-1 and y==W-1:
        ans=z
        break
    
    elif arr[x][y]=="." and vist[x][y]==0:
        vist[x][y]=1
        for dx,dy in dxdy:
            if (0<=x+dx<H) and (0<=y+dy<W):
                if arr[x+dx][y+dy]==".":
                    d.append([x+dx,y+dy,z+1])

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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
mapa=[]
mapa.append(''.join(['#' for _ in range(w+2)]))
dotn = 0
for i in range(h):
    temp = input()
    dotn+=temp.count('.')
    mapa.append('#'+temp+'#')
mapa.append(''.join(['#' for _ in range(w+2)]))
passed = [[False for _ in range(w+2)] for _ in range(h+2)]

def dircheck(cy,cx):
    if mapa[cy][cx]=='.' and not passed[cy][cx]:
        passed[cy][cx]=True
        return True
    else:
        return False    

q=deque()
q.append((1,1))
step=0
goaled=False
while True:
    newq=deque()
    while len(q)!=0:
        (y,x) = q.pop()
        if (y,x)==(h,w):
            goaled=True
            break
        else:
            for dy,dx in zip((y-1,y+1,y,y),(x,x,x-1,x+1)):
                if dircheck(dy,dx):newq.append((dy,dx))
    q = newq
    step+=1
    if goaled:
        print(dotn-step)        
        break
    if len(newq)==0:
        print(-1)
        break

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[]
count=0
for _ in range (H):
    A=list(input())
    for a in A:
        if a=='.':
            count+=1
    S.append(A)
 
mas=deque([(0,0,0)])
while mas:
    y,x,n=mas.popleft()
    if 0<=y<=H-1 and 0<=x<=W-1:
        if S[y][x]=='.':
            S[y][x]=n
            mas.append((y+1,x,n+1))
            mas.append((y,x+1,n+1))
            mas.append((y-1,x,n+1))
            mas.append((y,x-1,n+1))
short=S[H-1][W-1]
if short=='.':
    print(-1)
else:
    print(count-(short+1))

Submission status: Accepted

Solution code:
from collections import deque

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

S = [[] for _ in range(h)]
# まず、最初にある白マスの数を数えておく
ans = 0
for i in range(h):
    S[i] = input()
    ans += S[i].count('.')

direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]

# BFS
# 距離を初期化.
D = [[-1] * w for _ in range(h)]
D[0][0] = 0

# 現在地でキューを初期化.
que = deque([[0, 0]])

# キューがなくなるまで探索を行う.
while que:
    # キュー（右から）を一つ取り出す.
    chi, cwi = que.pop()

    for (dh, dw) in direct:
        # 迷路の範囲外なら探索しない.
        if not (0 <= chi + dh <= h - 1 and 0 <= cwi + dw <= w - 1):
            continue
        # 探索済みや探索不可なところは探索しない.
        if D[chi + dh][cwi + dw] != -1 or S[chi + dh][cwi + dw] == '#':
            continue
        # 距離の計算.
        D[chi + dh][cwi + dw] = D[chi][cwi] + 1
        # 次に探索する場所の追加.
        que.appendleft([chi + dh, cwi + dw])

dist = D[-1][-1]
# もともとあった白マスの数 - (ゴールまでに辿る最小の白マス+スタートの1マス)
if dist != -1:
    print(ans - (dist + 1))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

def get_adj(pos):
    ans = []
    for v in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        adj = (pos[0] + v[0], pos[1] + v[1])
        if adj[0] >= 0 and adj[0] < H and adj[1] >= 0 and adj[1] < W:
            ans.append(adj)
    return ans

start = (0, 0)
goal = (H-1, W-1)

q = deque()
q.append((start, 1))
visited = {}

while q:
    pos, dist = q.popleft()
    if field[pos[0]][pos[1]] == '#':
        continue
    if pos in visited:
        continue
    visited[pos] = dist
    if pos == goal:
        break
    for adj in get_adj(pos):
        q.append((adj, dist+1))

count_walls = sum([row.count('#') for row in field])

if goal in visited:
    print(H*W-visited[goal]-count_walls)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w = list(map(int, input().split()))
s = [None]*h
for i in range(h):
    s[i] = input()
start = (0,0)
# 高さh, 幅w
from queue import deque
vals = [None] * (w*h)
q = deque([(0, start)]) # (距離, ノード番号)
vals[start[0]*w+start[1]] = 0
dx = [0,1,0,-1]
dy = [1,0,-1,0]
while q:
    val, (x,y) = q.popleft()
    for i, j in zip(dx,dy):
        xx, yy = x+i, y+j
        if xx<0 or xx>=h or yy<0 or yy>=w or s[xx][yy]=="#":
            continue
        if vals[xx*w+yy] is None:
            vals[xx*w+yy] = val+1
            q.append((vals[xx*w+yy], (xx,yy)))

dist = vals[-1]
if dist is None:
    ans = -1
else:
    ans = (h*w) - (dist+1) - sum(sum(item=="#" for item in ss) for ss in s)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
l = [list(input()) for i in range(h)]
h1,w1= 0,0
#"."のかず
cou = 0
for i in l:
  for j in i:
    if j=='.':
      cou += 1
k = [[-1]*w for i in range(h)]
def bfs(a,b):
  d = deque()
  d.append([a,b])
  k[a][b]=0
  while d:
    c,e = d.popleft()
    m = [1,0,-1,0]
    n = [0,1,0,-1]
    for i in range(4):
      c1 = c+m[i]
      e1 = e+n[i]
      if 0<=c1 and 0<=e1 and c1<h and e1<w:
        if l[c1][e1]=="." and k[c1][e1]==-1:
          k[c1][e1]  =k[c][e] +1
          d.append([c1,e1])
  return k
bfs(h1,w1)        
if k[-1][-1]!=-1:
  print(cou-k[-1][-1]-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 1001001001
from collections import deque

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, w="#"):
	gp = w*(len(mxy[0])+2)
	return [gp,]+[w+vx+w for vx in mxy]+[gp,]

vD = [(0,1),(1,0),(0,-1),(-1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	sr,sc = 1,1
	gr,gc = H,W
	mM = [input().rstrip() for _ in "*"*H]
	walls = sum(s.count("#") for s in mM)
	mM = pad(mM,"#")
	#print(mM)#
	
	res = 0
	cnt = 0
	
	mV = [[INF,]*(W+2) for _ in "*"*(H+2)]
	#for sr in range(1,H+1):
	#	for sc in range(1,W+1):
	#		if mM[sr][sc]==".":
	#			continue
	mV[sr][sc] = 0
	vQ_app((sr,sc))
	
	while vQ:
		r,c = vQ_popl()
		now_cost = mV[r][c]
		for dr,dc in vD:
			nr,nc = r+dr, c+dc
			if mM[nr][nc]!=".":
				continue
			if now_cost + 1 < mV[nr][nc]:
				vQ_app((nr,nc))
				mV[nr][nc] = now_cost + 1
				#res = max(now_cost+1, res)
		
		cnt += 1
		#print(res,cnt,X,Y,H)
		if cnt>4999999: break
	
	res = mV[gr][gc]
	if res == INF:
		res = -1
	else:
		res = H*W - res - walls - 1
	print(res)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
maze=[]
white=0
for i in range(H):
    s=input()
    c=s.count(".")
    white+=c
    maze.append(s)
path=[[None]*W for _ in range(H)]
path[0][0]=1
q=deque([[0,0]])
while q:
    h,w=q.popleft()
    for nh,nw in ([h+1,w],[h-1,w],[h,w+1],[h,w-1]):
        if nh<0 or nh>H-1 or nw<0 or nw>W-1:
            continue
        if maze[nh][nw]=="#" or path[nh][nw]!=None:
            continue
        q.append([nh,nw])
        path[nh][nw]=path[h][w]+1
        if nh==H-1 and nw==W-1:
            print(white-path[nh][nw])
            exit()
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
S = [[] for _ in range(h)]
ans = 0
for i in range(h):
    S[i] = list(input())
    ans += S[i].count('.')

direct = [[0,1],[0,-1],[1,0],[-1,0]]
# BFS
## 距離を初期化.
D = [[-1]*w for _ in range(h)]
D[0][0] = 0
## 現在地でキューを初期化.
que = deque([[0,0]])
## キューがなくなるまで探索を行う.
while que:
    ### キューを一つ取り出す.
    chi, cwi = que.pop()
    for (dh,dw) in direct:
        #### 迷路の範囲外なら探索しない.
        if not (0<=chi+dh<=h-1 and 0<=cwi+dw<=w-1): continue
        #### 探索済みや探索不可なところは探索しない.
        if D[chi+dh][cwi+dw]!=-1 or S[chi+dh][cwi+dw]=='#': continue
        #### 距離の計算.
        D[chi+dh][cwi+dw] = D[chi][cwi]+1
        #### 次に探索する場所の追加.
        que.appendleft([chi+dh, cwi+dw])
dist = D[-1][-1]
print(ans-(dist+1) if dist!=-1 else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    black = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': black += 1

    q = deque([(0, 0, 0)]) # (i, j, move_count)
    dist = -1
    visited = {(0, 0)}
    while q:
        i, j, c = q.popleft()
        if i == H - 1 and j == W - 1:
            dist = c
            break
        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if (ni, nj) in visited: continue
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                q.append((ni, nj, c + 1))
                visited.add((ni, nj))

    if dist == -1:
        print(-1)
    else:
        print(H * W - black - dist - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def read():
    H, W = map(int, input().split(' '))
    Ss = []
    for _ in range(H):
        Ss.append(input())
    return H, W, Ss
 
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
def add(p1, p2):
    return (p1[0] + p2[0], p1[1] + p2[1])
 
def ans(H, W, Ss):
    if Ss[0][0] == '#':
        print('0,0 #')
        return -1
    ds =[ [-1 for _ in range(W)] for _ in range(H)]
    ds[0][0] = 1
    q = [(0, 0)]
    while q:
        p = q.pop()
        d = ds[p[1]][p[0]]
        for dr in DIRS:
            x, y = add(p, dr)
            if x < 0 or x >= W or y < 0 or y >= H:
                continue # 範囲外へは移動できない
            if Ss[y][x] == '#':
                continue # 行き止まりへは移動できない
            if ds[y][x] >= 0 and ds[y][x] <= d + 1: # すでに訪れていて短縮にもなっていない
                continue
            ds[y][x] = d + 1
            q.append((x, y))
    if ds[H-1][W-1] < 0:
        return -1
    # 白マスを数える
    ws = sum([l.count('.') for l in Ss])
    return ws - ds[H-1][W-1]
 
if __name__ == '__main__':
    H, W, Ss = read()
    print(ans(H, W, Ss))

Submission status: Accepted

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

move=[[1,0],[-1,0],[0,1],[0,-1]]
start=[1,1]

cheak = [[-1]*(W+2) for _ in range(H+2)]
cheak[1][1] = 0

que = deque()
que.append(start)
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if MAP[nx][ny] == "." and cheak[nx][ny] == -1:
            que.append([nx,ny])
            cheak[nx][ny]=cheak[x][y]+1
if cheak[H][W] == -1:
    print(-1)
else:
    print(cnt-cheak[H][W]-1)#スタート地点も白くなくてはいけないので-1

Submission status: Accepted

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
from collections import deque
# import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H, W, = map(int, input().split())
Map = [input().rstrip() for _ in range(H)]
# print(Map)

White = 0
White += Map[0].count('.', 1)
for i in range(1, H - 1):
    White += Map[i].count('.')
White += Map[-1].count('.', 0, -1)

s = (0, 0)
e = (H-1, W-1)

dis = [[-1]*W for _ in range(H)]

q = deque()
q.append(s)
dis[q[0][0]][q[0][1]] = 0
while q:
    for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        y, x = [o + d for o, d in zip(q[0], delta)]
        if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
            pass
        elif Map[y][x] == '#':
            pass
        elif dis[y][x] != -1:
            pass
        else:
            dis[y][x] = dis[q[0][0]][q[0][1]] + 1
            q.append((y, x))
            if (y, x) == e:
                break
    else:
        q.popleft()
        continue
    break

if dis[e[0]][e[1]] == -1:
    print(-1)
else:
    print(White-(dis[e[0]][e[1]]-1))

Submission status: Accepted

Solution code:
from collections import deque

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

mp = ['#'*(W+1)]
memo = [[-1]*(W+1) for _ in range(H+1)]

cnt = 0
for _ in range(H):
  s = '#'+input()
  cnt += s.count('.')
  mp.append(s)
  
ds = [[1,0], [-1,0], [0,1], [0,-1]]
h = deque([[1,1,1]])
while h:
  l = h.popleft()
  for d in ds:
    if l[0]+d[0] <= W and l[1]+d[1] <= H:
      if mp[l[1]+d[1]][l[0]+d[0]] == '.' and memo[l[1]+d[1]][l[0]+d[0]] == -1:
        memo[l[1]+d[1]][l[0]+d[0]] = l[2] + 1
        h.append([l[0]+d[0], l[1]+d[1], l[2] + 1])
  if memo[H][W] > -1:
    print(cnt-memo[H][W])
    exit()
    
print(memo[H][W])

Submission status: Accepted

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

def clear_maze(sx, sy, gx, gy, maze):

	INF = 100000000

	field_x_length = len(maze)
	field_y_length = len(maze[0])
	distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
#	distance = [[INF]*field_y_length]*field_x_length

	def bfs():
		queue = []

		queue.insert(0, (sx, sy))

		distance[sx][sy] = 0

		while len(queue):
			x, y = queue.pop()

			if x == gx and y == gy:
				break

			for i in range(0, 4):
				nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

				if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y] + 1

		return distance[gx][gy]
	return bfs()
if clear_maze(0, 0, h-1, w-1, s) == 100000000:
	print(-1)
else:
	print(white - clear_maze(0, 0, h-1, w-1, s) - 1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
H += 2
W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    move_list = [-1, 1, W, -W]
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in move_list:
            w = v + move
            if grid[w] == '#':
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return dist[-(W+2)]

d = bfs(W+1)
T = grid.count("#")

if d == 10 ** 9:
  print("-1")
else:
  print(H*W - T - (d+1))

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
maze=[list(input()) for i in range(H)]
count=-1

#-------------------------------------------------------------------------
#幅優先探索,再帰関数

def search() :
    flag=[[0]*W for i in range(H)]
    count=[[-1]*W for i in range(H)]
    flag[0][0]=1                               #通った場所はflagを0から1に変更していく
    count[0][0]=0                              #こちらで通る時間を数える
    pos=deque([])
    pos.append([0,0])

    while len(pos)>0 :
        y,x=pos.popleft()
        if y==H-1 and x==W-1 :
            return count[H-1][W-1]
            break

        for p,q in [[1,0],[-1,0],[0,1],[0,-1]] :
            if 0<=y+p<H and 0<=x+q<W and maze[y+p][x+q]=="." and flag[y+p][x+q]==0 :
                flag[y+p][x+q]=1     
                pos.append([y+p,x+q])
                count[y+p][x+q]=count[y][x]+1    

    if y!=H-1 and x!=W-1 :
        print(-1)
        exit()         

#-------------------------------------------------------------------------
#スコア求める,始めに白の個数を数えて、後で通った白の数だけ引く

for i in range(H) :
    for j in range(W) :
        if maze[i][j]=="." :    
            count+=1

ans=count-search()

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def MI(): return map(int, input().split())
INF=float('inf')
def bfs():
  que=deque()
  que.append((sx,sy))
  dist=[[INF] *W for _ in range(H)]
  dist[sx][sy]=0
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  while que:
    x,y=que.popleft()
    if x==gx and y==gy:
      break
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=dist[x][y]+1
            que.append((nx,ny))
  return dist[gx][gy]
H,W=MI()
Map=[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 Map[i][j]=='.':
      white+=1
res=bfs()
if 0<res<INF:
  print(white-res-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
INF=10**18
h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=[[INF for _ in range(w)]for _ in range(h)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
sx,sy=0,0
gx,gy=h-1,w-1
d[sx][sy]=1
q=deque([(sx,sy)])
while q:
  x,y=q.popleft()
  if (x,y)==(gx,gy):break
  for i in range(4):
    nx,ny=x+dx[i],y+dy[i]
    if 0<=nx<h and 0<=ny<w:
      if a[nx][ny]=='.' and d[nx][ny]==INF:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
if d[gx][gy]==INF:print(-1)
else:
  cnt=0
  for i in a:
    cnt+=i.count('.')
  print(cnt-d[gx][gy])