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 pprint import pprint
INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]
# 入力
h, w = map(int, input().split())
maze = []
wallcount = 0
for i in range(h):
    l = list(input())
    maze.append(l)
    wallcount += l.count("#")

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))



# 迷路ををグラフにする。
goal = -1
dis = 0
import collections
q = collections.deque( [ (0,0,0) ] ) #x,y,d

while len(q) > 0:
    x, y, d = q.popleft()
    if x == w - 1 and y == h - 1:
        goal = d
    for dir in range(len(dx)):
        nx, ny = x + dx[dir], y + dy[dir]
        if -1 < nx and nx < w and -1 < ny and ny < h:
            if nx == w-1 and ny == h - 1:
                goal = d + 1
                break
            if maze[ny][nx] == ".": # そのマスが壁でないなら
                maze[ny][nx] = d
                q.append( (nx, ny, d + 1) )

    if goal != -1:
        break

# これで結果が出たので
import itertools
if goal == -1:
    print(-1)
else:
    needstep = goal
    res = h * w
    res -= wallcount
    res -= needstep + 1
    print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

reached = [[float('inf') for _ in range(W)] for _ in range(H)]
reached[0][0] = 1

while len(togo):

    h, w = togo[0][0], togo[0][1]
    togo.popleft()

    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if reached[nh][nw] != float('inf'):
            continue
        togo.append((nh, nw))
        reached[nh][nw] = reached[h][w] + 1

if reached[H-1][W-1] == float('inf'):
    print(-1)
else:
    n_wall = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '#':
                n_wall += 1

    n_road = H * W - n_wall
    print(n_road - reached[H-1][W-1])

Submission status: Accepted

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

q=deque()

i=0
j=0
s[0][0]=0
q.appendleft([0,0])
while(len(q)>0):
    qi=q.popleft()
    j,i=qi[0],qi[1]
    num=s[j][i]
    if(i==w-1 and j==h-1):
        print(h*w - wall_num - num - 1)
        sys.exit()
    if(i>0 and s[j][i-1]=="."):
        s[j][i-1]=num+1
        q.append([j,i-1])
    if(i<w-1 and s[j][i+1]=="."):
        s[j][i+1]=num+1
        q.append([j,i+1])
    if(j>0 and s[j-1][i]=="."):
        s[j-1][i]=num+1
        q.append([j-1,i])
    if(j<h-1 and s[j+1][i]=="."):
        s[j+1][i]=num+1
        q.append([j+1,i])

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

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

G = [list(input()) for _ in range(H)]
INF = 1e10
G2 = [[INF] * W for _ in range(H)]

lst = deque()
lst.append((0, 0, 0))
while lst:
    y, x, v = lst.popleft()
    if G2[y][x] < INF: continue
    G2[y][x] = v
    if y == H - 1 and x == W - 1:
        break

    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G[ny][nx] == '.':
                lst.append((ny, nx, v + 1))
if G2[H - 1][W - 1] == INF:
    print(-1)
    exit()

white_cnt = 0
for i in range(H):
    for j in range(W):
        white_cnt += G[i][j] == '.'
print(white_cnt - G2[H-1][W-1]-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

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

G = [list(input()) for _ in range(H)]
INF = 1e10
G2 = [[INF] * W for _ in range(H)]

lst = deque()
lst.append((0, 0, 0))
while lst:
    y, x, v = lst.popleft()
    if G2[y][x] < INF: continue
    G2[y][x] = v
    if y == H - 1 and x == W - 1:
        break

    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G[ny][nx] == '.':
                lst.append((ny, nx, v + 1))
if G2[H - 1][W - 1] == INF:
    print(-1)
    exit()

route_cnt = 0
x, y = W - 1, H - 1
while 1:
    route_cnt += 1
    if x == 0 and y == 0:
        break
    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G2[ny][nx] == G2[y][x] - 1:
                x, y = nx, ny
                break

white_cnt = 0
for i in range(H):
    for j in range(W):
        white_cnt += G[i][j] == '.'
print(white_cnt - route_cnt)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            # dist=1+dist
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])
while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()
            # print(x+xd,y+yd)

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])
# print(grid)
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Submission status: Accepted

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

  countWhite=0
  maze=[]
  maze+=[["#"]*(w+2)]
  for e in sys.stdin.readlines():
    maze+=[["#"]+list(e[:-1])+["#"]]
    countWhite+=e.count(".")
  maze+=[["#"]*(w+2)]
  
  xy=[(1,0),(-1,0),(0,1),(0,-1)]
  
  que=deque()
  que.append([1,1,1])
  shortestPath=0
  while(que):
    point=que.popleft()
    x,y,step=point[0],point[1],point[2]

    if (x,y)==(h,w):
      print(countWhite-step)
      break
    if maze[x][y]!=".":
      continue
    maze[x][y]=str(step)
    for i,j in xy:
      que.append([x+i,y+j,step+1])
  else:
    print(-1)

  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]


def bfs(start, goal):
    q = [[start]]
    while len(q) > 0:
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
        else:
            for sy, sx in zip(dy, dx):
                py = n[0] + sy
                px = n[1] + sx
                if py < 0 or H <= py:
                    continue
                if px < 0 or W <= px:
                    continue
                if S[py][px] == "#":
                    continue
                if visited[py][px]:
                    continue
                visited[py][px] = True
                x = (py, px)
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    q.append(new_path)
    return None


H, W = map(int, input().split())
S = []
for i in range(H):
    S.append([c for c in input()])
# print(S)
visited = [[False for _ in range(W)] for _ in range(H)]
start = (0, 0)
goal = (H-1, W-1)
ans = bfs(start, goal)
if ans is None:
    print(-1)
    exit()
# print(ans)
counter = 0
for i in range(H):
    for j in range(W):
        if (i, j) in ans:
            continue
        if S[i][j] == ".":
            counter += 1
print(counter)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
cnt = 0
grid = [list(input()) for i in range(n)]
grid2 = [[]]*n
for i in range(n):
  cnt += "".join(grid[i]).count("#")
  grid2[i] = ["#"] + grid[i] + ["#"]
  
grid2.insert(0,["#"]*(m+2))
grid2.append(["#"]*(m+2))
grid2[1][1] = 0
loc =[[1,1]]

for k in range(1,n*m):
  next_loc = []
  for y,x in loc:
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
      if grid2[y+i][x+j] == ".":
        grid2[y+i][x+j] = k
        next_loc.append([y+i,x+j])
  loc = next_loc
#  print(loc,k)
  if [n,m] in loc:
    break

ans = n*m - (k+1+cnt)

print(ans if ans >= 0 else -1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

H,W = [int(zz) for zz in input().split()]
map = [['#']*(W+2) for _ in range(H+2)]

ans = 0
for i in range(1,H+1):
    tmp = input()
    s = list('#'+tmp+'#')
    map[i] = s
    ans += tmp.count('#')

check = [[1]*(W+2) for _ in range(H+2)]
count = [[0]*(W+2) for _ in range(H+2)]
q = deque([(1,1)])
check[1][1] = 0
while q:
    x,y = q.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        if check[x+i][y+j] and map[x+i][y+j] == '.':
            check[x+i][y+j] = 0
            q.append((x+i,y+j))
            count[x+i][y+j] = count[x][y]+1
zz = count[H][W]
if zz == 0:
    print(-1)
else:
    count = set((np.array(count)).flatten())
    for i in count:
        if i > zz:
            ans -= 1
    print(H*W-len(count)-ans)

Submission status: Accepted

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

wall_count = 0
s = []
for _ in range(max_h):
    line = input()
    wall_count += line.count("#")
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]

# 迷路と同じサイズの距離表を作成.
# 値が0 -> 未訪問, それ以外 -> スタート地点からそれまでの距離となる
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

que = deque([(1, 1)])

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

  for i in range(4):
    dx, dy = dis_x[i], dis_y[i]
    if s[h+dy][w+dx] == '.' and dist[h+dy][w+dx] == 0:
      dist[h+dy][w+dx] = dist[h][w] + 1
      que.append((h+dy, w+dx))

result = max_h*max_w - wall_count - dist[max_h][max_w] - 1
if dist[max_h][max_w] == 0:
  print(-1)
else:
  print(result)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
m = []
cnt_sharp = 0
for i in range(h):
    tmp = input()
    cnt_sharp += tmp.count('#')
    m.append(tmp)

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

# print(m)
q = deque([])
seen = [[0 for _ in range(w)] for _ in range(h)]
q.append((0, 0, 0))
road = 0
while q:
    y, x, cnt = q.popleft()
    seen[y][x] = 1
    if y == h - 1 and x == w - 1:
        road = cnt + 1
        break
    for ny, nx in zip(dy, dx):
        if 0 <= y + ny < h and 0 <= x + nx < w:
            if seen[y + ny][x + nx] == 0 and m[y + ny][x + nx] == '.':
                seen[y + ny][x + nx] = 1
                # print(y + ny, x + nx, cnt)
                q.append((y + ny, x + nx, cnt + 1))

if road == 0:
    print(-1)
else:
    print(h * w - road - cnt_sharp)

Submission status: Accepted

Solution code:
from collections import deque
H, W = [int(x) for x in input().split()]
maze = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[float('inf')] * W for i in range(H)]
black = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            black += 1

def bfs():
    q = deque()
    q.append([0, 0])
    d[0][0] = 0

    while q:
        x, y = q.popleft()
        if x == H - 1 and y == W - 1:
            break
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    return d[H-1][W-1]

print(-1) if bfs() == float('inf') else print(H*W - black - (bfs() + 1))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [[-1] * (W + 1) for _ in range(H + 1)]
white = 0
for h in range(H):
    for w, c in enumerate(input()):
        if c == ".":
            m[h][w] = 0
            white += 1

gh = H - 1
gw = W - 1
mincount = 0
todo = deque()
todo.append((0, 0))
m[0][0] = 1
while todo:
    h, w = todo.popleft()
    ncount = m[h][w] + 1
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh = h + dh
        nw = w + dw
        if nh == gh and nw == gw:
            mincount = ncount
            todo.clear()
            break
        if m[nh][nw] == 0:
            m[nh][nw] = ncount
            todo.append((nh, nw))

if mincount > 0:
    print(white - mincount)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
s = []
black = 0

for i in range(H):
    line = list(input())
    s.append(line)
    black += line.count('#')

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

q = deque()
dq = deque()
q.append((0, 0))
dq.append(1)

visited = [(0, 0)]
while len(q) != 0:
    pos = q.popleft()
    if pos == (W - 1, H - 1):
        break
    d = dq.popleft()
    for dir in dirs:
        next = (pos[0] + dir[0], pos[1] + dir[1])
        if 0 <= next[0] <= W - 1 and 0 <= next[1] <= H - 1 and \
                next not in visited and s[next[1]][next[0]] == '.':
            q.append(next)
            dq.append(d + 1)
            visited.append(next)
else:
    print(-1)
    sys.exit()

min_d = dq.popleft()
print(H * W - black - min_d)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
s = []
black = 0
for i in range(H):
    l = list(input())
    for j in range(W):
        if l[j] == "#":
            black += 1
    s.append(l)
white = H*W-black
from collections import deque
q = deque([(0,0,0)])
s[0][0] = "#"
while q:
    x,y,cnt = q.popleft()
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        nx,ny = x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and s[nx][ny] != "#":
            if nx == H-1 and ny == W-1:
                print(white-cnt-2)
                exit(0)
            s[nx][ny] = "#"
            q.append((nx,ny,cnt+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    #移動距離　最小値に更新していく
    d = [[float("inf")] * C for _ in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    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):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                #全周を超えない　&　壁でない　&　未探索である
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]

R, C = map(int,input().split())
sy, sx = 0, 0
gy, gx = R-1, C-1

maze = [list(input()) for _ in range(R)]

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

if cnt-bfs()-1 >= 0:
    print(cnt-bfs()-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#%%
INF = 1<<30
dist = [[INF]*W for _ in range(H)]
dist[0][0] = 0

import queue

q = queue.Queue()
q.put([0,0])

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

keiro = [[[] for _ in range(W)] for _ in range(H)]

while not (q.empty()):
    cur = q.get()
    y,x = cur[0],cur[1]
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        d = dist[y][x] + 1
        if nx<0 or nx>=W or ny<0 or ny>=H:
            continue
        elif S[ny][nx] == '#':
            continue
        
        elif dist[ny][nx]>d:
            q.put([ny,nx])
            dist[ny][nx] = d
            keiro[ny][nx] = [y,x]


if dist[H-1][W-1]==INF:
    print(-1)
else:
    white = 0
    for s in S:
        for t in s:
            if t=='.':
                white += 1
    
    ans = white - dist[H-1][W-1] - 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    flag = False
    d = [[float('inf')] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((0, 0))
    d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0]==H-1 and p[1]==W-1:
            flag = True
            break

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!='#' and d[ny][nx]==float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    if flag==False:
        return False

    return d[H-1][W-1]

def notcount(H, W, maze):
    cnt = 0

    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                cnt += 1

    return cnt

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
if bfs()==False:
    print(-1)
else:
    s = (H * W - notcount(H, W, maze)) - (bfs() + 1)
    #bfs()
    print(s)

Submission status: Accepted

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

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

q = [(0,0)]

while q:
    h1,w1 = q.pop(-1)
    if h1 > 0:
        if s[h1-1][w1] == '.':
            if dis[h1][w1] + 1 < dis[h1-1][w1]:
                dis[h1-1][w1] = dis[h1][w1] + 1
                q.append((h1-1,w1))
    if w1 > 0:
        if s[h1][w1-1] == '.':
            if dis[h1][w1] + 1 < dis[h1][w1-1]:
                dis[h1][w1-1] = dis[h1][w1] + 1
                q.append((h1,w1-1))
    if h1 < h - 1:
        if s[h1+1][w1] == '.':
            if dis[h1][w1] + 1 < dis[h1+1][w1]:
                dis[h1+1][w1] = dis[h1][w1] + 1
                q.append((h1+1,w1))
    if w1 < w - 1:
        if s[h1][w1+1] == '.':
            if dis[h1][w1] + 1 < dis[h1][w1+1]:
                dis[h1][w1+1] = dis[h1][w1] + 1
                q.append((h1,w1+1))

if dis[-1][-1] == 10 ** 10:
    print(-1)
    exit()

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

print(count - dis[-1][-1] - 1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
from collections import deque
INF=10**6
m=[[10**6]*W for _ in range(H)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs(y,x):
  q=deque()
  q.append((y,x))  
  
  while len(q)>0:
    y,x=q.popleft()
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if  0<=nx<W and 0<=ny<H and A[ny][nx]=="." and m[ny][nx]==INF:
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1

m[0][0]=0
bfs(0,0)
cnt=(m[-1][-1])
if cnt>2500:
  print(-1)
else:
  cntd=0
  for i in range(H):
    for j in range(W):
      if A[i][j]=='#':
        cntd+=1
  print(H*W-cnt-cntd-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
#0が進めるところ、1は無理
#lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]

road_count = 0
lis = [list('#'*(w+2))]
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '#' + li + '#'
    lis.append(list(li))
lis.append(list('#'*(w+2)))

#print(lis)
dp = [[0]*(w+2) for _ in range(h+2)]

#(開始x,開始y,移動回数)
step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)

    if x == h and y == w:
        print(road_count-dp[x][y]-1)
        exit()

    #探索済みのところは、#にする
    lis[x][y] = '#'


    if lis[x-1][y] != '#' and dp[x-1][y] == 0:
        step.append([x-1,y])
        dp[x-1][y] = dp[x][y]+1
    if lis[x+1][y] != '#' and dp[x+1][y] == 0:
        step.append([x+1,y])
        dp[x+1][y] = dp[x][y]+1
    if lis[x][y-1] != '#' and dp[x][y-1] == 0:
        step.append([x,y-1])
        dp[x][y-1] = dp[x][y]+1
    if lis[x][y+1] != '#' and dp[x][y+1] == 0:
        step.append([x,y+1])
        dp[x][y+1] = dp[x][y]+1
print(-1)

Submission status: Accepted

Solution code:
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)

Submission status: Accepted

Solution code:
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1

while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1


print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
m = []
m.append('#'*(W+2))
white = 0
for i in range(H):
  s = input()
  m.append(list('#' + s + '#'))
  white += s.count('.')
m.append('#'*(W+2))
 
op = set([(1, 1)])
dist = 0
while len(op) > 0:
  dist += 1
  next_op = set()
  for y, x in op:
    m[y][x] = dist
    if (y, x) == (H, W):
      print(white - dist)
      exit()
 
    for dx,dy in [0,1],[0,-1],[1,0],[-1,0]:
      if m[y-dy][x-dx] == '.':
        next_op.add((y-dy,x-dx))
  op = next_op
 
print('-1')

Submission status: Accepted

Solution code:
import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
while not q.empty():
    x, y, count = q.get()
    if checked[y][x]:
        continue
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque

def solve(x,y,gx,gy):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    start = [x, y]
    dist = [[10**3]*w for i in range(h)]
    dist[y][x] = 0
    Q = deque()
    Q.append(start)

    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**3:
                    Q.append([nx, ny])
                    dist[ny][nx] = dist[p[1]][p[0]] + 1
                    if nx==gx and ny==gy:
                        return dist[ny][nx]
    return -1

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

res=solve(0,0,w-1,h-1)

if res==-1:
    print(res)
else:
    print(cnt-solve(0,0,w-1,h-1)-1)

Submission status: Accepted

Solution code:
from collections import deque


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


H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
d = [[-1] * W for _ in range(H)]
b = 0

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

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            b += 1
l = bfs(0, 0, H - 1, W - 1)
if l < 0:
    print(l)
else:
    print(H*W - b-l-1)