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
def main():
    # 最短距離に使うマス以外を黒に塗る
    # そもそも右下のゴールに辿り着けないなら-1
    # ans = 元の白個数-最短距離 if ゴール到達可能 else -1
    H,W = map(int, input().split())
    sx,sy = 0,0
    road = [[False]*W for _ in range(H)]
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1

    # H*Wのマスをs->gへ移動
    # ゴールできるか + ゴールまでの"最短距離"を知る
    gx,gy = (H-1),(W-1)
    directions = [(1,0),(0,1),(-1,0),(0,-1)] # 東西南北に移動可能
    depth = [[0]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    arrived[sx][sy] = True
    que = deque([(sx,sy)]) # BFS:appendleftとpopでキュー
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            # 枠外
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            # 壁
            if not road[x2][y2]:
                continue
            # 探索済み
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            depth[x2][y2] = depth[x1][y1]+1
            if (x2,y2)==(gx,gy):
                print(origWhite-(depth[x2][y2]+1))
                return
    print(-1)


main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
maze = []
visited = [[0]*(w) for _ in range(h)]
mx = 0
for _ in range(h):
    s = input()
    mx += s.count('.')
    maze.append(list(s))
sy,sx = 0, 0
gy, gx = h-1, w-1
que = deque([(sy,sx,1)])

while que:
    y,x,c = que.popleft()
    if visited[y][x] != 0:
        continue
    visited[y][x] = c
    for dy,dx in zip((1,-1,0,0), (0,0,1,-1)):
        ny,nx = y+dy, x+dx
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]=='.':
                que.append((ny,nx,c+1))

print(mx-visited[gy][gx] if visited[gy][gx]!=0 else -1)

Submission status: Accepted

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

white = sum([s[i].count('.') for i in range(H)])
que = deque([(0, 0, 0)])
s[0][0] = '#'
while que:
    y, x, d = que.popleft()
    if (y, x) == (H - 1, W - 1):
        break
    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx
        if ny < 0 or ny > H - 1 or nx < 0 or nx > W - 1:
            continue
        if s[ny][nx] == '#':
            continue
        s[ny][nx] = '#'
        que.append((ny, nx, d + 1))
else:
    print(-1)
    sys.exit()

print(white - d - 1)

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	ol = queue.Queue()
	m=[input() for _ in range(h)]
	b = [[-1]*w for _ in range(h)]
	b[0][0]=1
	ol.put(0)
	while not ol.empty():
		p = ol.get()
		x, y = p//1000, p%1000
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if x+dx<0 or x+dx>=h or y + dy <0 or y+dy >= w:
				continue
			if m[x+dx][y+dy]=='#':
				continue
			if b[x+dx][y+dy]>=0:
				continue
			b[x+dx][y+dy]=b[x][y]+1
			ol.put((x+dx)*1000+(y+dy))
	#print(b)
	if b[-1][-1]==-1:
		return -1
	return sum([s.count('.') for s in m])- b[-1][-1]
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 088 D - Grid Repainting

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().strip().split())
S = []
start_counter = 0  # 始状態の # をカウントする
for _ in range(H):
    s = list(map(str, sys.stdin.readline()))
    S.append(s)
    for i in s:
        if i == '#':
            start_counter += 1


# 幅優先で最短経路を探索　最短経路で通る白ますの数を求める
fp = [[True] * W for _ in range(H)]  # FootPrint 探索済みか記録する
q = deque()
q.append((0, 0, 1))
fp[0][0] = False

ans_counter = -1
while q:
    ux, uy, counter = q.popleft()
    # print(f'ux: {ux}, uy: {uy}, counter: {counter}')

    if (ux == W - 1) and (uy == H - 1):
        ans_counter = counter
        break

    for i in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        vx = ux + i[0]
        vy = uy + i[1]

        if (vx < 0) or (vx >= W):
            continue
        if (vy < 0) or (vy >= H):
            continue
        if fp[vy][vx] is False:
            continue
        if S[vy][vx] == '#':
            continue

        q.append((vx, vy, counter + 1))
        fp[vy][vx] = False

if ans_counter == -1:
    print(-1)
else:
    print(H * W - start_counter - ans_counter)

Submission status: Accepted

Solution code:
from collections import deque

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


d=deque()
d.append([0,0,0])
s[0][0]="0"
mx=[1,0,-1,0]
my=[0,1,0,-1]
ans=0

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

while len(d)>0:
    t,y,x=d.popleft()
    if [y,x]==[H-1,W-1]:
        break
    for m in range(4):
        if 0<=y+my[m]<H and 0<=x+mx[m]<W and s[y+my[m]][x+mx[m]]==".":
            d.append([t+1,y+my[m],x+mx[m]])
            s[y+my[m]][x+mx[m]]=str(t+1)

if s[-1][-1]==".":
    print(-1)
else:
    print(white-int(s[-1][-1]))

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
sharp = 0
for i in range(h):
	t = input()
	sharp += t.count("#")
	s.append(t)

queue = deque([[0,0]])

visited = [[-1 for i in range(w)] for j in range(h)]
visited[0][0] = 0
d = [(1,0),(0,1),(-1,0),(0,-1)]
while queue:
	i, j = queue.popleft()
	for n, m in d:
		x = i+n
		y = j+m
		if x < 0 or x >= h or y < 0 or y >= w or s[x][y] == "#" or visited[x][y] != -1:
			continue
		visited[x][y] = visited[i][j] + 1
		queue.append([x,y])
if visited[h-1][w-1] == -1:
	print (-1)
else:
	ans = h*w-visited[h-1][w-1]-1-sharp
	print (ans)

Submission status: Accepted

Solution code:
R,C = map(int,input().split())
sy,sx = 1,1
gy,gx = R,C
maze = [list(input()) for _ in range(R)]
mx = 0
for m in maze:
  mx += m.count('.')


sx,sy = sx-1, sy-1
gx,gy = gx-1, gy-1

def bfs(R,C,sy,sx,gy,gx,maze):
    from collections import deque
    import numpy as np
    INF = np.inf
    visited = [[INF]*C for _ in range(R)]
    visited[sy][sx] = 0
    que = deque([(sy,sx)])
    while que:
        y,x = que.popleft()
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            ny,nx = y+i, x+j
            if 0<=ny<R and 0<=nx<C:
                if (maze[ny][nx]!='#') and visited[ny][nx]==INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append((ny,nx))
    if visited[gy][gx]!=INF:
      return visited[gy][gx]
    else:
      return -1

ans = bfs(R,C,sy,sx,gy,gx,maze)
print(mx-ans-1 if ans!=-1 else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import numpy as np


def main():
    H, W = map(int, input().split())
    s_x = 1
    s_y = 1
    g_x = H
    g_y = W
    dp = - np.ones((H+2, W+2))
    black = 0
    for i in range(1, H+1):
        line = input()
        for j in range(1, W+1):
            if line[j - 1] == '.':
                dp[i][j] = 0
            else:
                black += 1
    queue = deque()
    queue.append((s_x, s_y))
    dp[s_x][s_y] = 1
    while len(queue) != 0:
        now_x, now_y = queue.popleft()
        for x in range(-1, 2):
            for y in range(-1, 2):
                if (x + y) % 2 == 0:
                    continue
                next_x = now_x + x
                next_y = now_y + y
                if dp[next_x][next_y] == 0:
                    dp[next_x][next_y] = dp[now_x][now_y] + 1
                    queue.append((next_x, next_y))
    if dp[g_x][g_y] == -1 or dp[g_x][g_y] == 0:
        print(-1)
    else:
        print(int(H * W - black - dp[g_x][g_y]))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 7)  # ここが足りないと " RecursionError: maximum recursion depth exceeded in comparison " が出る


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

grid = ['#'] * (W+2)  #外枠の塀を作る
for _ in range(H):
    grid += ['#'] + list(input()) + ['#']
grid += ['#'] * (W+2)

cnt = grid.count(".")

move = [1,-1,W+2,-(W+2)]    #グラフの左、右移動を作る


start = W+2
goal = (H+1)*(W+2)-2
flg = False
visit = set([start]) # 到達可能

next_set = deque()
next_set.append((start, 1))

while next_set:    # q = [] になったら止める
    x, t = next_set.popleft()     # 要素を消去して、消去した要素を出力
    for dx in move:
        y = x+dx
        if grid[y] == '#':
            continue
        if y in visit:
            continue
        if y == goal:
            flg = True
            break
        visit.add(y)   # すでに到達した道を記憶
        next_set.append((y, t + 1))     # yに移動
    if flg:
        break
if not flg:
    print(-1)
else:
    print(cnt - t )

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

white = 0
for i in range(h):
    white += s[i].count(".")
#print(white)
inf = 100000
smap = [[inf]*w for _ in range(h)]
smap[0][0] = 1
visited = [[0]*w for _ in range(h)]
visited[0][0] = 1

q = deque()
q.append(0)
q.append(0)

while q:
    y = q.popleft()
    x = q.popleft()
    if x != 0 and s[y][x-1] == "." and visited[y][x-1] == 0:
        lx = x-1
        q.append(y)
        q.append(lx)
        visited[y][lx] = 1
        smap[y][lx] = min(smap[y][lx], smap[y][x] + 1)

    if x != w-1 and s[y][x+1] == "." and visited[y][x+1] == 0:
        rx = x+1
        q.append(y)
        q.append(rx)
        visited[y][rx] = 1
        smap[y][rx] = min(smap[y][rx], smap[y][x] + 1)

    if y != 0 and s[y-1][x] == "." and visited[y-1][x] == 0:
        uy = y-1
        q.append(uy)
        q.append(x)
        visited[uy][x] = 1
        smap[uy][x] = min(smap[uy][x], smap[y][x] + 1)

    if y != h-1 and s[y+1][x] == "." and visited[y+1][x] == 0:
        dy = y+1
        q.append(dy)
        q.append(x)
        visited[dy][x] = 1
        smap[dy][x] = min(smap[dy][x], smap[y][x] + 1)


if smap[h-1][w-1] == inf:
    print(-1)
else:
    print(white-smap[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

sx,sy = 0,0
gx,gy = w-1,h-1
#bfsで最短経路を求めて、それ以外のマスを塗りつぶせばよい
black = 0
for i in range(h):
    for j in range(w):
        if map_input[i][j]=='#':
            black+=1

mx = [0,0,1,-1]
my = [1,-1,0,0]

queue = deque([[sx,sy]])
visited = [[0]*w for i in range(h)]
visited[sy][sx] = 1

def bfs(queue,visited):
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+mx[i]
            ny = y+my[i]
            if 0<=nx<w and 0<=ny<h:
                if visited[ny][nx]!=0:
                    continue
                if map_input[ny][nx]=='#':
                    continue
                if nx==gx and ny==gy:
                    return visited[y][x]+1
                visited[ny][nx]=visited[y][x]+1
                queue.append([nx,ny])
    return -1

tmp = bfs(queue,visited)
if tmp==-1:
    print(-1)
else:
    ans = h*w-tmp-black
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
score = H * W
S = [[] for i in range(H)]
for i in range(H):
    for s in input():
        if s == "#":
            score -= 1
        S[i].append(s)


ls = deque([[0, 0]])
dir = [[1,0], [-1,0], [0,1], [0,-1]]
dp = [[float("inf") for i in range(W)] for j in range(H)]
dp[0][0] = 0
while len(ls) > 0:
    x, y = ls.popleft()

    if x == H-1 and y == W-1:
        print(score-dp[H-1][W-1]-1)
        break

    for dx, dy in dir:
        if (x+dx < 0) or (x+dx > H-1) or (y+dy < 0) or (y+dy > W-1):
            continue
        else:
            if S[x+dx][y+dy] == "." and dp[x][y]+1 < dp[x+dx][y+dy]:
                dp[x+dx][y+dy] = dp[x][y] + 1
                ls.append([x+dx, y+dy])

else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

Y,X=map(int,input().split())

cs=[list(input()) for i in range(Y)]

q=deque()
dist=[[-1 for i in range(X)] for j in range(Y)]
dist[0][0]=0
q.append([0,0])
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while(len(q)!=0):
    v=q.popleft()
    for i in range(4):
        nv =[v[0]+dy[i], v[1]+dx[i]]
        if nv[0] < 0 or nv[0] > Y-1 or nv[1] < 0 or nv[1] > X-1:
            continue
        if dist[nv[0]][nv[1]]!=-1 or cs[nv[0]][nv[1]] == "#":
            continue
        dist[nv[0]][nv[1]] = dist[v[0]][v[1]]+1
        q.append(nv)
        
black=0
res=dist[Y-1][X-1]
for i in range(Y):
    for j in range(X):
        if cs[i][j]=="#":
            black+=1
            

if res ==-1:
    print(-1)
else:
    print(Y*X-res-1-black)

Submission status: Accepted

Solution code:
# 最短距離を全白マス数から引く

import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
grid = [None] * H
white = 0
for i in range(H):
  grid[i] = readline().rstrip()
  white += grid[i].count(".")

from collections import deque
q = deque()
# y,x,距離
q.append([0,0,1])
visited = set()
cases = ((0,1),(0,-1),(1,0),(-1,0))
while q:
  y,x,dist = q.popleft()
  if grid[y][x] == "#":
    continue
  if (y,x) in visited:
    continue
  visited.add((y,x))
  if y == H - 1 and x == W - 1:
    print(white - dist)
    break
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      q.append([y + c[0],x + c[1],dist + 1])
else:
  print(-1)

Submission status: Accepted

Solution code:
# ほぼ最短路を求めるだけ

import heapq as hp
import numpy as np

H,W = map(int,input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.pad(S,1,'constant')
visited = np.zeros_like(S,dtype=np.bool)

dist = np.inf

h = []
hp.heappush(h,(0,1,1))

while h:
  d,x,y = hp.heappop(h)
  if x == H and y == W:
    dist = d
    break
  for dx,dy in [[0,1],[1,0],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    if S[nx,ny] == '.' and not visited[nx,ny]:
      visited[nx,ny] = True
      hp.heappush(h,(d+1,nx,ny))
      
if dist == np.inf:
  print(-1)
else:
  print((S == '.').sum() - dist - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    G = [0] * H
    for i in range(H):
        G[i] = readline().strip()
    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        if x == H - 1 and y == W - 1:
            break
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and G[nx][ny] == '.' and dist[nx][ny] == -1:
                queue.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[H - 1][W - 1] == -1:
        print(-1)
    else:
        ans = sum(row.count('.') for row in G) - dist[H - 1][W - 1]
        print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    G = [0] * H
    for i in range(H):
        G[i] = readline().strip()
    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        if x == H - 1 and y == W - 1:
            break
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and G[nx][ny] == '.' and dist[nx][ny] == -1:
                queue.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[H - 1][W - 1] == -1:
        print(-1)
    else:
        blacks = sum(row.count('#') for row in G)
        print(H * W - dist[H - 1][W - 1] - blacks)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque

""" 最短の距離でスタートからゴールまで行けば残りの移動可能部分はすべてスコアにすることができる。
    ただ、たどり着けない場合も考える必要がある
"""

def bfs(h, w, board, start, goal):

    bfs_deque = deque()
    bfs_deque.append(start)

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    x, y = start
    reached_area[y][x] = 0

    min_distance = INF

    while len(bfs_deque) > 0:

        coord = bfs_deque.popleft()
        x, y= coord

        if coord == goal:
            # 終了処理 いろいろ書く
            if min_distance > reached_area[y][x]:
                min_distance = reached_area[y][x]


        # 4方向に移動
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]

            # 移動してキューに加える
            if 0 <= nx < w and 0 <= ny < h and board[ny][nx] != "#" and reached_area[ny][nx] == INF:
                # 到達済みリストに距離を記録
                reached_area[ny][nx] = reached_area[y][x] + 1
                # キューに座標を加える
                bfs_deque.append([nx, ny])

    if min_distance != INF:
        return min_distance
    else:
        return -1


h, w = map(int, input().split())
board = [input().rstrip() for i in range(h)]

start = [0, 0]
goal = [w-1, h-1]

movable_area_count = 0
INF = 999
reached_area = [[INF for i in range(w)] for j in range(h)]

# 移動可能なエリアを算出
for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            movable_area_count += 1

# 最短手数を算出
min_distance = bfs(h, w, board, start, goal)

if min_distance != -1:
    print(movable_area_count - min_distance -1)
else:
    print(min_distance)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=[(0,0)]
while d:
    y,x=d.pop(0)
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if h>t>=0<=u<w and a[t][u]=="." and b[t][u]>b[y][x]+1:
            d+=[(t,u)]
            b[t][u]=b[y][x]+1
print(max(-1,sum([i.count(".") for i in a])-b[-1][-1]))

Submission status: Accepted

Solution code:
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.popleft()
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if h>t>=0<=u<w:
            if a[t][u]=="." and b[t][u]>b[y][x]+1:
                d.append([t,u])
                b[t][u]=b[y][x]+1
print(max(-1,sum([i.count(".") for i in a])-b[-1][-1]))

Submission status: Accepted

Solution code:
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.popleft()
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if 0<=t<h and 0<=u<w:
            if a[t][u]=="." and b[t][u]>b[y][x]+1:
                d.append([t,u])
                b[t][u]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))

Submission status: Accepted

Solution code:
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.pop()
    if y<h-1:
        if a[y+1][x]=="." and b[y+1][x]>b[y][x]+1:
            d.append([y+1,x])
            b[y+1][x]=b[y][x]+1
    if x<w-1:
        if a[y][x+1]=="." and b[y][x+1]>b[y][x]+1:
            d.append([y,x+1])
            b[y][x+1]=b[y][x]+1
    if y>0:
        if a[y-1][x]=="." and b[y-1][x]>b[y][x]+1:
            d.append([y-1,x])
            b[y-1][x]=b[y][x]+1
    if x>0:
        if a[y][x-1]=="." and b[y][x-1]>b[y][x]+1:
            d.append([y,x-1])
            b[y][x-1]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [0]*(h+2)
for i in range(1,h+1):
    s[i] = ["#"] + list(input()) + ["#"]
s[0] = ["#"]*(w+2)
s[-1] = ["#"]*(w+2)

from collections import deque
qx = deque([])
qy = deque([])
qx.append(1)
qy.append(1)
r = [[0 for j in range(w+2)] for i in range(h+2)]
r[1][1] = 1
ans = 0
while qx:
    x = qx.popleft()
    y = qy.popleft()
    
    if s[x-1][y] == "." and r[x-1][y] == 0:
        qx.append(x-1)
        qy.append(y)
        r[x-1][y] = r[x][y] + 1
    if s[x+1][y] == "." and r[x+1][y] == 0:
        qx.append(x+1)
        qy.append(y)
        r[x+1][y] = r[x][y] + 1
    if s[x][y-1] == "." and r[x][y-1] == 0:
        qx.append(x)
        qy.append(y-1)
        r[x][y-1] = r[x][y] + 1
    if s[x][y+1] == "." and r[x][y+1] == 0:
        qx.append(x)
        qy.append(y+1)
        r[x][y+1] = r[x][y] + 1

c = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == ".":
            c += 1
if r[h][w] != 0:    
    print(c-r[h][w])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h ,w = map(int, input().split())
s = ['$'*(w+2)] * (h+2)
cnt = 0
for i in range(1,h+1):
    s[i] = '$' + input() + '$'
    cnt += s[i].count('.')

dist = [[-1]*(w+2) for _ in range(h+2)] # スタートからの距離の記録をするリスト
dist[1][1] = 0 # スタート地点を0 にする
q = deque()
q.append((1,1))
while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    for i in range(4):
        nx = x + vx[i]
        ny = y + vy[i]
        if s[nx][ny] == '$' or s[nx][ny] == '#': continue # 壁なら通れないね！
        if dist[nx][ny] != -1: continue # もう最短距離がわかってるなら飛ばす
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく

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

Submission status: Accepted

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

from collections import deque

ans = 0
stack = deque([[0,0,1]])
dxdy = [(0,1),(0,-1),(1,0),(-1,0)]
visited = [[0 for i in range(w)] for j in range(h)]
minus = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            visited[i][j] = 1
            minus += 1


ans = -1
while(stack):
    ne = stack.popleft()
    x,y = ne[0],ne[1]
    if x < 0 or x > h-1: continue
    if y < 0 or y > w-1: continue
    if visited[x][y] == 1: continue
    if x== h -1 and y == w-1:
        ans = h*w - ne[2] - minus

    visited[x][y] = 1

    for dx,dy in dxdy:
        stack.append([dx+x,dy+y,ne[2]+1])

print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
route = [[0, 0]]
visited = copy.deepcopy(s)
visited[0][0] = '#'
q = deque([[0, 0, route]])
score = -1

while q:
    y, x, route = q.popleft()
    r = copy.deepcopy(route)
    if [y, x] == [H-1, W-1]:
        score = sum(len(l) for l in s) - (sum(l.count('#') for l in s) + len(route))
        break
    if y > 0 and visited[y-1][x] == '.':
        visited[y-1][x] = '#'
        r.append([y-1, x])
        q.append([y-1, x, r])
        r = copy.deepcopy(route)
    if y < H-1 and visited[y+1][x] == '.':
        visited[y+1][x] = '#'
        r.append([y+1, x])
        q.append([y+1, x, r])
        r = copy.deepcopy(route)
    if x > 0 and visited[y][x-1] == '.':
        visited[y][x-1] = '#'
        r.append([y, x-1])
        q.append([y, x-1, r])
        r = copy.deepcopy(route)
    if x < W-1 and visited[y][x+1] == '.':
        visited[y][x+1] = '#'
        r.append([y, x+1])
        q.append([y, x+1, r])
        r = copy.deepcopy(route)

print(score)

Submission status: Accepted

Solution code:
from collections import deque
def main():
  h,w = map(int,input().split())
  s = [input() for _ in range(h)]
  #print(sum([i.count(".") for i in s]))
  
  def bfs(st):
    que = deque([st])
    c = [[0]*w for _ in range(h)]
    while que:
      ph,pw = que.popleft()
      step = c[ph][pw] + 1
      for dh,dw in ((1,0),(0,1),(-1,0),(0,-1)):
        nh = ph+dh
        nw = pw+dw
        if nh<0 or nw<0 or nh>=h or nw>=w:
          continue
        if s[nh][nw]=="#" or c[nh][nw] != 0:
          continue
        c[nh][nw] = step
        if (nh,nw) == (h-1,w-1):
          return step
        que.append((nh,nw))
  
  result = bfs((0,0))
  if result:
    return sum([i.count(".") for i in s])-result-1
  else:
    return -1

print(main())

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [input() for i in range(h)]
reach = [[0]*w for i in range(h)]
reach[0][0]=1
from collections import deque
q = deque([(0,0)])

goal = False
while q:
    x,y = q.popleft()
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+i<h and 0<=y+j<w:
            if reach[x+i][y+j]==0 and s[x+i][y+j]=='.':
                reach[x+i][y+j] = reach[x][y]+1
                if x+i==h-1 and y+j==w-1:
                    goal = True
                    break
                q.append([x+i,y+j])

c = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            c += 1

if goal:
    print(c-reach[h-1][w-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
maze = SLs(H)

count = 0
for item in maze:
  for i in item:
    if i == ".":
      count += 1
      
dx = [0,0,1,-1]
dy = [1,-1,0,0]

d = [[-1 for j in range(W)] for i in range(H)] 
d[0][0] = 0
q = deque([(0,0)])
while q:
  x,y = q.popleft()
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<=nx<W and 0<=ny<H:
      if maze[ny][nx] == ".":
        if d[ny][nx] == -1:
          d[ny][nx] = d[y][x] + 1
          q.append((nx,ny))
if d[H-1][W-1] == -1:
  print(-1)
else:
  print(count- d[H-1][W-1] -1)