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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(-1,0),(0,1),(0,-1)]
def solve():
    h,w = LI()
    s = [input() for i in range(h)]
    bfs = [[0]*w for i in range(h)]
    bfs[0][0] = 1
    q = deque([(0,0)])
    gy,gx = h-1,w-1
    while q:
        y,x = q.popleft()
        if (y,x) == (gy,gx):
            break
        nb = bfs[y][x] + 1
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if s[ny][nx] == "#":
                    continue
                if not bfs[ny][nx]:
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    ans = bfs[gy][gx]
    if not ans:
        print(-1)
        return
    c = sum([i.count("#") for i in s])
    print(h*w-c-ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

dist = [[-1]*w for _ in range(h)]
dist[0][0]=0
que = [(0,0)]
move = [(0,1),(0,-1),(1,0),(-1,0)]

n_white = 0
for i in range(h):
    n_white += s[i].count(".")

while que!=[]:
    (x , y) = que.pop(0)
    
    for m in move:
        nx = x + m[0]
        ny = y + m[1]
        if (0<=nx<h and 0<=ny<w):
            if dist[nx][ny] != -1: continue
            
            if s[nx][ny] == ".":
                dist[nx][ny] = dist[x][y]+1
                que.append((nx,ny))
distance = dist[-1][-1]
if distance == -1:
    print(-1)
else:
    print(n_white - distance - 1)

Submission status: Accepted

Solution code:
from collections import deque

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

dx = [0,1,0,-1]
dy = [1,0,-1,0]
seen = [[0]*W for i in range(H)]
que = deque([[0,0]])
seen[0][0] = 1
while True:
    if len(que) == 0: break #たどり着けない
    h,w = que.popleft()
    if h == H-1 and w == W-1: break #ゴール
    for i in range(0,4):
        if (h+dy[i]<0 or h+dy[i]>=H or w+dx[i]<0 or w+dx[i]>=W): continue
        if S[h+dy[i]][w+dx[i]] == "." and seen[h+dy[i]][w+dx[i]] == 0:
            seen[h+dy[i]][w+dx[i]] = seen[h][w]+1
            que.append([h+dy[i],w+dx[i]])

cnt = 0
for a in range(H):
    for b in range(W):
        if S[a][b] == ".": cnt += 1

if seen[H-1][W-1] == 0:
    print(-1)
else:
    print(cnt-seen[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    M = [list(input()) for _ in range(h)]
    D = [[10**10] * w for _ in range(h)]
    D[0][0] = 0

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

    que = deque([])
    que.append((0, 0))
    while que:
        p = que.popleft()
        if p == (h-1, w-1):
            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 M[ny][nx] != "#" and D[ny][nx] == 10**10:
                D[ny][nx] = D[p[0]][p[1]] + 1
                que.append((ny, nx))

    if D[h-1][w-1] == 10**10:
        print(-1)
        exit()

    n_white = 0
    for r in M:
        n_white += len([s for s in r if s == "."])
    print(n_white - D[h-1][w-1] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
black = 0
data = []
for _ in range(h):
    s = input()
    for i in range(w):
        if s[i] == "#":
            black += 1
    data.append(s)

dist = [[-1]*w for _ in range(h)]
queue = deque()
queue.append((0, 0))
dist[0][0] = 0

while queue:
    x, y = queue.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        tox, toy = x + dx, y + dy
        if 0 <= tox < h and 0 <= toy < w and dist[tox][toy] == -1 and data[tox][toy] == '.':
            dist[tox][toy] = dist[x][y] + 1
            queue.append((tox, toy))

print(h * w - black - dist[-1][-1] - 1 if dist[-1][-1] != -1 else -1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs():
    INF = float('inf')
    check = [[INF] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    check[sy][sx] = 1
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] != '#' and check[ny][nx] == INF:
                que.append((ny, nx))
                check[ny][nx] = check[y][x] + 1
    return check[gy][gx]


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

sy = 0
sx = 0
gy = H - 1
gx = W - 1
ret = bfs()
if ret == float('inf'):
    print(-1)
else:
    ans = H * W - black - ret
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def BFS_grid(grid,visited,start,goal):
    y,x = start
    visited[y][x] = 1
    q = deque([start])
    delta = [[-1,0],[0,-1],[1,0],[0,1]]
    h = len(grid)
    w = len(grid[0])
    flag = False
    while q:
        y,x = q.popleft()
        for dy,dx in delta:
            if (0<= x+dx < w) and (0<= y+dy<h) :
                if visited[y+dy][x+dx] == 0 and grid[y+dy][x+dx]==".":
                    visited[y+dy][x+dx] = visited[y][x] +1
                    q.append([y+dy,x+dx])
                    if [y+dy,x+dx] == goal:
                        flag = True
    return flag


h,w = map(int,input().split())
mz = []
white = 0

for i in range(h):
    mz.append(list(input()))
    white += mz[-1].count(".")

visited = [[0]*w for i in range(h)]
if BFS_grid(mz,visited,[0,0],[h-1,w-1]):
    print(white - (visited[h-1][w-1]-visited[0][0]+1))
else:
    print(-1)

Submission status: Accepted

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

ll=[[-1 for i in range(w)] for j in range(h)]
ld=deque()

ld.append([0,0])
ll[0][0]=0
while len(ld)!=0:
    k=ld.popleft()
    y=k[0]
    x=k[1]
    p=ll[y][x]
    if 0<=y+1<h and 0<=x<w and ll[y+1][x]==-1 and l[y+1][x]!="#":
        ld.append([y+1,x])
        ll[y+1][x]=p+1
    if 0<=y-1<h and 0<=x<w and ll[y-1][x]==-1 and l[y-1][x]!="#":
        ld.append([y-1,x])
        ll[y-1][x]=p+1
    if 0<=y<h and 0<=x+1<w and ll[y][x+1]==-1 and l[y][x+1]!="#":
        ld.append([y,x+1])
        ll[y][x+1]=p+1
    if 0<=y<h and 0<=x-1<w and ll[y][x-1]==-1 and l[y][x-1]!="#":
        ld.append([y,x-1])
        ll[y][x-1]=p+1
        
s=0
if ll[h-1][w-1]==-1:
    print(-1)
else:
    for i in range(h):
        s+=l[i].count("#")
    print(h*w-s-ll[h-1][w-1]-1)

Submission status: Accepted

Solution code:
import collections

####入力
H,W = map(int,input().split())
#gridの定義
grid = []
flat_grid = []
for i in range(H):
  S = input()
  tasu = [S[i] for i in range(W) ]
  grid.append(tasu )
  flat_grid = flat_grid + tasu
####入力終了

sx,sy = 0,0
gx,gy = W-1,H-1

#seenとtodoの初期設定
l_seen = [[False for i in range(W)] for j in range(H) ]
l_todo = []
dist = [[0 for i in range(W)] for j in range(H) ]

#seenに出発地点を決めてやる、今回は[0][0]である
l_seen[sy][sx] = True 

#pに隣接する頂点４つについて初期設定
for i in [[sx+1,sy],[sx,sy+1],[sx-1,sy],[sx,sy-1] ]:
  #場外アウトしたり、移動先が壁の場合はスルー
  if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
    continue
  #移動先が壁の場合スルー
  if grid[i[1]][i[0]] == "#":
    continue  
  dist[i[1]][i[0]] = 1 
  #pに隣接する頂点を探索済みにする
  l_seen[i[1]][i[0]] = True 
  #pに隣接する頂点をtodoリストに追加
  l_todo = l_todo + [i]


#探索
while len(l_todo) != 0:

  #幅優先探索 todoリストから次のターゲットを取り出す
  v = l_todo.pop(0) 

  for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
    #場外アウトしたり、移動先が壁の場合はスルー
    if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
      continue
    #移動先が壁の場合スルー
    if grid[i[1]][i[0]] == "#":
      continue
    #移動先が探索済みの場合スルー
    if l_seen[i[1]][i[0]] == True:
      continue  

    if l_seen[i[1]][i[0]] == False:
      l_seen[i[1]][i[0]] = True
      l_todo = l_todo + [i]
      dist[i[1]][i[0]]=dist[v[1]][v[0]]+1

d = dist[gy][gx]
w_num = collections.Counter(flat_grid)["."]
if d == False:
  print(-1)
else:
  print(w_num -(d+1)) #d+1はスタート地点からゴールまでのますの数

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Map = [input() for _ in range(H)]
black_no1 = 0
A = [[0 for __ in range(W)] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if Map[i][j] == '#':
      black_no1 += 1
      A[i][j] = 1
pos = [[0, 0]]
dfs = 1
clr = -1
while pos != []:
  dfs += 1
  n = len(pos)
  for i in range(n):
    p = pos[0]
    if p[0] > 0:
      if A[p[0]-1][p[1]] == 0:
        A[p[0]-1][p[1]] = 1
        pos.append([p[0]-1, p[1]])
      if p[0] - 1 == H - 1 and p[1] == W - 1:
        clr = 0
    if p[0] < H - 1:
      if A[p[0]+1][p[1]] == 0:
        A[p[0]+1][p[1]] = 1
        pos.append([p[0]+1, p[1]])
      if p[0] + 1 == H - 1 and p[1] == W - 1:
        clr = 0
    if p[1] > 0:
      if A[p[0]][p[1]-1] == 0:
        A[p[0]][p[1]-1] = 1
        pos.append([p[0], p[1]-1])
      if p[0] == H - 1 and p[1] - 1 == W - 1:
        clr = 0
    if p[1] < W - 1:
      if A[p[0]][p[1]+1] == 0:
        A[p[0]][p[1]+1] = 1
        pos.append([p[0], p[1]+1])
      if p[0] == H - 1 and p[1] + 1 == W - 1:
        clr = 0
    pos = pos[1:]
    if clr == 0:
      break
  if clr == 0:
    break
if clr == 0:
  print(H*W-dfs-black_no1)
else:
  print(clr)

Submission status: Accepted

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

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
INF = float("inf")
ss = [[INF] * w for i in range(h)]
def bfs():
    q = queue.Queue()
    ss[0][0] = 1
    q.put([0, 0])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            if nextx >= 0 and nexty >= 0 and nextx < h and nexty < w:
                if s[nextx][nexty] == "." and ss[nextx][nexty] == INF:
                    ss[nextx][nexty] = ss[nowx][nowy] + 1
                    q.put([nextx, nexty])

bfs()
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            cnt += 1

if ss[h - 1][w - 1] == INF:
    print("-1")
else:  
    print(cnt - ss[h - 1][w - 1])

Submission status: Accepted

Solution code:
from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))
if maze[0][0] == '#' or maze[h-1][w-1] == '#':
    print(-1)
    exit()


d = [[INF] * w for i in range(h)]
def bfs():
    #d = [[INF] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(0, 0)])
    d[0][0] = 0

    while len(que) != 0:
        val = que.popleft()
        if val[0] == h-1 and val[1] == w-1:
            break
        for i in range(4):
            nx = val[0] + dx[i]
            ny = val[1] + dy[i]
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == INF):
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    return d[h-1][w-1]
ans = bfs()
if ans == INF:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                cnt += 1
    print(cnt - (ans+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
black = 0
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

r,c = [int(x) for x in input().split()]
sy,sx = [0,0]
gy,gx = [r-1,c-1]
m = []
for _ in range(r):
    m.append(list(input()))

##########################################

q = deque()
d = [[-1]*c for i in range(r)]

q.append([sy,sx])
d[sy][sx] = 0
while q:
    v = q.popleft()
    if v == [gy,gx]:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0]+i[0]
        nx = v[1]+i[1]
        if 0<=ny<r and 0<=nx<c and m[ny][nx] == "." and d[ny][nx] == -1:
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

##########################
count = 0
for i in m:
    for j in i:
        if j==".":
            count += 1
if d[gy][gx] == -1:
    print(-1)
else:
    ans = count - d[gy][gx] - 1
    print(ans)

Submission status: Accepted

Solution code:
INF = 1000000000

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

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

dist = [[INF for i in range(w)] for j in range(h)]

dist[0][0] = 1

que = [[0, 0]]

while len(que) > 0:
    p = que.pop(0)

    if p == [h-1, w-1]:
        break

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

        if 0 <= nx < h and 0 <= ny < w and S[nx][ny] == '.' and dist[nx][ny] == INF:
            que.append([nx, ny])
            dist[nx][ny] = dist[p[0]][p[1]] + 1

if dist[h-1][w-1] == INF:
    print(-1)
else:
    ans = 0
    for s in S:
        ans += s.count('.')
    ans -= dist[h-1][w-1]
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
visited = [[-1]*W for _ in range(H)]
que = [[0,0]]
direction = [[1,0],[0,1],[-1,0],[0,-1]]
visited[0][0] = 1
while que:
  h, w = que.pop(0)
  for dh, dw in direction:
    if h+dh<0 or H<=h+dh or w+dw<0 or W<=w+dw:
      continue
    if G[h+dh][w+dw] == '#':
      continue
    if visited[h+dh][w+dw] != -1:
      continue
    que.append([h+dh, w+dw])
    visited[h+dh][w+dw] = visited[h][w]+1
cnt = 0
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      cnt += 1
if visited[H-1][W-1] != -1:
  ans = H*W-visited[H-1][W-1]-cnt
else:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    q = deque()
    st = [1, 1]
    go = [h, w]
    q.append(st)
    d[1][1] = 1
    v = [1, -1]
    while q:
        u = q.popleft()
        x, y = u[0], u[1]
        for i in range(2):
            if s[x + v[i]][y] == "." and d[x + v[i]][y] == 0:
                q.append([x + v[i], y])
                d[x + v[i]][y] = d[x][y] + 1
        for i in range(2):
            if s[x][y + v[i]] == "." and d[x][y + v[i]] == 0:
                q.append([x, y + v[i]])
                d[x][y + v[i]] = d[x][y] + 1
    c = 0
    for i in s:
        for j in i:
            if j == ".":
                c += 1
    if d[h][w] == 0:
        return -1
    return c - d[h][w]

h, w = map(int, input().split())
s = [["#"] + list(input()) + ["#"] for _ in range(h)]
t = ["#" for _ in range(w + 2)]
s.append(t)
s.insert(0, t)
d = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
print(bfs())

Submission status: Accepted

Solution code:
import queue

def bfs(s1,s2):
    global ans
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    s[s1][s2] = 0
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[x][y] + 1
                queueX.put(nextX)
                queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            cnt += 1
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]
bfs(0,0)
if s[H - 1][W - 1] == '.':
    print(-1)
else:
    print(H * W - cnt - s[H - 1][W - 1] - 1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = []
nb = 0
for _ in range(H):
    s.append(list(input()))
    nb += s[-1].count("#")

nw = H * W - nb

sy, sx = 0, 0
gy, gx = H - 1, W - 1

q = [[sy, sx]]
visited = [[int(1e10)]*W for _ in range(H)]
visited[sy][sx] = 0
while q:
    ty, tx = q.pop(0)
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = ty + dy, tx + dx
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "#":
            if visited[ny][nx] > visited[ty][tx] + 1:
                visited[ny][nx] = visited[ty][tx] + 1
                q.append([ny, nx])
    if [gy, gx] in q:
        temp = visited[gy][gx]
        break
if visited[gy][gx] == int(1e10):
    print(-1)
else: print(nw - temp - 1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs():
    d = [[float("inf")]*w for i in range(h)]
    que = deque([])
    que.append((0, 0))
    d[0][0] = 1

    while que:
        p = que.popleft()
        if p[0] == h - 1 and p[1] == w - 1:
            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 f[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[h-1][w-1]


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

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

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

ans = bfs()
if ans != float("inf"):
    print(white - ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque([(0, 0, 1)])
minDist = [[10**10] * W for _ in range(H)]

while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    if (h, w) == (H - 1, W - 1):
        break

    for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
        toH, toW = h + dh, w + dw
        if 0 <= toH < H and 0 <= toW < W and A[toH][toW] == '.':
            que.append((toH, toW, d + 1))

if minDist[H - 1][W - 1] == 10**10:
    print(-1)
    exit()

white = sum([a.count('.') for a in A])
print(max(0, white - minDist[H - 1][W - 1]))

Submission status: Accepted

Solution code:
from collections import deque

def dfs(sx, sy ,gx, gy):             
    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

    white = 0

    for m in maze:
        white += m.count(".")

    while que:
        # キューの左端を取り出す
        now = que.popleft()
        # ゴールにたどり着いていれば終了
        if now[0] == gx and now[1] == gy:
            break
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[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[now[0]][now[1]] + 1

    if d[gx][gy] == float("inf"):
       return -1
    else:
        return white - d[gx][gy] - 1

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

print(dfs(0, 0, h - 1, w - 1))

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['#' for _ in range(W+2)])
ans = [[0 for _ in range(W+2)]for _ in range(H+2)]
score = 0
for i in range(H):
    tmp = list('#'+input()+'#')
    c.append(tmp)
    for j in range(W+2):
        if tmp[j] == '.':
            score += 1

c.append(['#' for _ in range(W+2)])
q = deque()

def bfs(x,y):
    q.append([x,y])
    while q:
        x,y = q.popleft()
        if [x,y] == [W,H]:
            return ans[H][W]
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'
    return -1

tmp = bfs(1,1)
if tmp == -1:
    print(-1)
else:
    print(score - tmp - 1)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sy,sx):
    dis=[[0]*W for i in range(H)]
    q=deque()
    q.append([sy,sx])
    while(len(q)!=0):
        y=q[0][0]
        x=q[0][1]
        q.popleft()
        for dy,dx in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if field[ny][nx]=="#":
                continue
            if dis[ny][nx]!=0:
                continue
            dis[ny][nx]=dis[y][x]+1
            q.append([ny,nx])
    if dis[H-1][W-1]==0:
        print(-1)
        exit()
    return dis[H-1][W-1]


H,W=map(int,input().split())
field=[input() for i in  range(H)]
O=0
for i in range(H):
    O+=field[i].count(".")
ans=O-1-bfs(0,0)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]
def bfs(y, x):
    for i in range(4):
        next_y = y + dir_y[i]
        next_x = x + dir_x[i]
        if 0 <= next_y < H and 0 <= next_x < W and maze[next_y][next_x] == "." and dist[next_y][next_x] == -1:
            que.append((next_y, next_x))
            dist[next_y][next_x] = dist[y][x] + 1


H, W = map(int, input().split())
sy, sx = 0, 0
maze = []
empty_count = 0
for i in range(H):
    maze.append(input())
    empty_count += maze[i].count(".")

dist = [[-1]*(W+1) for _ in range(H+1)]
dist[sy][sx] = 0
que = deque([(sy, sx)])

while len(que) > 0:
    y, x = que.popleft()
    bfs(y, x)

if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(empty_count - (dist[H-1][W-1] + 1))

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
maze = [['']*w]*h
wcnt = 0
for i in range(h):
  temp = list(input())
  wcnt += temp.count('.')
  maze[i] = temp
que = deque()
que.append([0,0])
d = [[float('inf')]*w for i in range(h)]
d[0][0] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
            d[nx][ny] = d[px][py] + 1
            que.append([nx,ny])
if d[h-1][w-1] == float('inf'):
    ans = -1
else:
    ans = wcnt - d[h-1][w-1] - 1
print(ans)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
grid = []
for _ in range(H):
    grid.append(list(input()))
dist_grid = [[-1 for _ in range(W)] for __ in range(H)]

queue = [(0, 0)]
dist_grid[0][0] = 1
while queue:
    h, w = queue.pop(0)
    nexts = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
    for y, x in nexts:
        if y < 0 or H <= y or x < 0 or W <= x:
            continue
        if dist_grid[y][x] == -1 and grid[y][x] == '.':
            dist_grid[y][x] = dist_grid[h][w] + 1
            queue.append((y, x))
            
sharp_num = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            sharp_num += 1

if dist_grid[-1][-1] == -1:
    print(-1)
else:
    print(H * W - dist_grid[-1][-1] - sharp_num)

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=["#"*W]
m=0
for i in range(H):
    s.append(input())
    m+=s[-1].count(".")
s.append("#"*W)
for i in range(H+2):
    s[i]="#"+s[i]+"#"
l=[[-1]*(W+2) for i in range(H+2)]
l[1][1]=1
b=[(1,1)]
c=2
while b:
    a=[]
    for i in b:
        if s[i[0]][i[1]+1]=="." and l[i[0]][i[1]+1]==-1:
            l[i[0]][i[1]+1]=c
            a.append((i[0],i[1]+1))
        if s[i[0]-1][i[1]]=="." and l[i[0]-1][i[1]]==-1:
            l[i[0]-1][i[1]]=c
            a.append((i[0]-1,i[1]))
        if s[i[0]+1][i[1]]=="." and l[i[0]+1][i[1]]==-1:
            l[i[0]+1][i[1]]=c
            a.append((i[0]+1,i[1]))
        if s[i[0]][i[1]-1]=="." and l[i[0]][i[1]-1]==-1:
            l[i[0]][i[1]-1]=c
            a.append((i[0],i[1]-1))
    c+=1
    b=a
if l[-2][-2]==-1:
    print(-1)
else:
    print(m-l[-2][-2])

Submission status: Accepted

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]

que = deque()
que.append((0,0))
dis[0][0] = 1

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

ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')

if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
s=[]
for i in range(H):
    S=input()
    s.append(S)
w_count=0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            w_count+=1
count=[[10**9 for i in range(W)]for j in range(H)]
chk=[[0 for i in range(W)]for j in range(H)]
rl=[1,-1]
up=[1,-1]
q=deque([(0,0)])
count[0][0]=1
chk[0][0]=1

while(q):
    #print(q)
    a,b=q.popleft()
    #print(q)
    for i in rl:
        r=b+i
        if r>=0 and r<W:
            if s[a][r]==".":
                count[a][r]=min(count[a][r],count[a][b]+1)
                #print("ON")
                if chk[a][r]==0:
                    q.append((a,r))
                chk[a][r]=1
    for i in up:
        u=a+i
        if u>=0 and u<H:
            if s[u][b]==".":
                count[u][b]=min(count[u][b],count[a][b]+1)
                #print("ON")
                if chk[u][b]==0:
                    q.append((u,b))
                chk[u][b]=1

ans=w_count-count[H-1][W-1]
#print(count)
if count[-1][-1]==10**9:
    print(-1)
    exit()

#print(w_count)
#print(count[-1][-1])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(S,H,W):
    que = deque([(0,0)])
    dist = [[2**60]*W for _ in range(H)]
    dist[0][0] = 0
    while que:
        u = que.popleft()
        d = [-1,1]
        y,x = u
        for i in range(2):
            s = x+d[i]
            t = y+d[i]
            if 0 <= s < W:
                if S[y][s] == '.':
                    if dist[y][s] == 2**60:
                        que.append((y,s))
                    dist[y][s] = min(dist[y][s],dist[y][x]+1)
            if 0 <= t < H:
                if S[t][x] == '.':
                    if dist[t][x] == 2**60:
                        que.append((t,x))
                    dist[t][x] = min(dist[t][x],dist[y][x]+1)
    return dist[-1][-1]

def main():
    H,W = map(int,input().split(" "))
    S = []
    total = -1
    for _ in range(H):
        s = input()
        total += s.count('.')
        S.append(s)
    num = bfs(S,H,W)
    if num == 2**60:
        ans = -1
    else:
        ans = total-num
    
    print(ans)

if __name__ == "__main__":
    main()