Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque

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

# 最短距離を幅優先探索で求める
# 最短経路以外の.を全て黒く塗りつぶせば最高得点

n_blank = [flatten for inner in s for flatten in inner].count(".")

distance = [[-1]*W for _ in range(H)]
current_position = [0,0]
distance[0][0] = 0
next_positions = deque()
next_positions.append(current_position) # このようにしないとデック内部が2重リストにならない

# ある地点を渡すと、その地点から到達可能かつ距離未計算の地点のリストを返す
def not_investigated_positions(current_position):
    output = []
    for udrl in [[0,1],[0,-1],[1,0],[-1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            if s[y][x] == "." and distance[y][x] == -1:
                output.append([y,x])
    return output

while len(next_positions)>0 and current_position!=[H-1,W-1]:
    current_position = next_positions.popleft()
    for q in not_investigated_positions(current_position):
        distance[q[0]][q[1]] = distance[current_position[0]][current_position[1]] + 1
        next_positions.append(q)

if current_position == [H-1,W-1]:
    print(n_blank - (distance[H-1][W-1]+1))
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
b=[["#"]*(w+2)]
a=0
for i in range(h):
  c=["#"]
  for j in input():
    a+=j=="#"
    c.append(j)
  b.append(c+["#"])
b+=[["#"]*(w+2)]
b[h][w]=0
Q=[(1,1)]
x=0
y=-1
while Q:
	x+=1
	p=[]
	for i,j in Q:
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if b[i+dx][j+dy]==".":
				p+=[(i+dx,j+dy)]
				b[i+dx][j+dy]="#"
			elif b[i+dx][j+dy]==0:
				y=x
	if y>0:break
	Q=p
if y>0:print((h*w)-a-y-1)
else:print(-1)

Submission status: Accepted

Solution code:
from collections import deque
r, c = map(int, input().split())

MAX = (r+2) * (c + 2)

sy = 0
sx = 0
gx = c-1
gy = r-1

maze = [[val for val in list(input())] for _ in range(r)]
checked_maze = [[None for _ in range(c)] for _ in range(r)]
goal = [False]

def wfs(queue):
    while len(queue) > 0:
        a = queue.popleft()
        y = a[0]
        x = a[1]
        count = a[2]
        if x < 0 or x > c-1 or y < 0 or y > r-1:
            continue
        if checked_maze[y][x]:
            continue

        if a[0] == gy and a[1] == gx:
            goal[0] = count
            break

        checked_maze[y][x] = True
        if not maze[y][x] == "#":
            count += 1
            queue.append((a[0]+1, a[1], count))
            queue.append((a[0]-1, a[1], count))
            queue.append((a[0], a[1]+1, count))
            queue.append((a[0], a[1]-1, count))


if __name__ == "__main__":
    que = deque()
    checked_maze[sy][sx] = 0
    que.append((sy, sx, 0))
    wfs(que)
    if not goal[0]:
        print(-1)
    else:
        masu = r * c
        blocks = 0
        for r_index in range(r):
            for c_index in range(c):
                if maze[r_index][c_index] == "#":
                    blocks += 1
        print(masu-goal[0]-1 -blocks)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(h, w, visited, ss):
    visited[0][0] = 0
    queue = deque([])
    queue.append([0, 0])
    while queue:
        y, x = queue.popleft()
        if y == h-1 and x == w-1:
            return visited[y][x]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            xn, yn = x+i, y+j
            if xn < 0 or yn < 0 or xn >= w or yn >= h:
                continue
            if visited[yn][xn] == -1 and ss[yn][xn] != "#":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])
    return -1


def main():
    h, w = map(int, input().split())
    ss = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    c = 0
    for s in ss:
        c += s.count("#")

    min_route = bfs(h, w, visited, ss)
    if min_route == -1:
        print(min_route)
    else:
        print(h*w - c - min_route - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(input())
    
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            ans += 1
            
Path = [[10**3 for j in range(W)] for i in range(H)]
Path[0][0] = 1
visited = [[0, 0]]

while len(visited) > 0:
    H = len(Path)
    W = len(Path[0])
    i = visited[0][0]
    j = visited[0][1]
    if i != 0:
        if Path[i-1][j] > Path[i][j]+1 and maze[i-1][j] == ".":
            Path[i-1][j] = Path[i][j]+1
            visited.append([i-1, j])
    if i != H-1:
        if Path[i+1][j] > Path[i][j]+1 and maze[i+1][j] == ".":
            Path[i+1][j] = Path[i][j]+1
            visited.append([i+1, j])
    if j != 0:
        if Path[i][j-1] > Path[i][j]+1 and maze[i][j-1] == ".":
            Path[i][j-1] = Path[i][j]+1
            visited.append([i, j-1])
    if j != W-1:
        if Path[i][j+1] > Path[i][j]+1 and maze[i][j+1] == ".":
            Path[i][j+1] = Path[i][j]+1
            visited.append([i, j+1])
    visited.pop(0)
            
if Path[-1][-1] >= 1000:
    ans = -1
else:
    ans -= Path[-1][-1]
    
print(ans)

Submission status: Accepted

Solution code:
INFTY = 1000
H,W = map(int,input().split())
S = [["#" for _ in range(W+2)]]
for i in range(H):
    row = list(input())
    row.insert(0,"#")
    row.append("#")
    S.append(row)
S.append(["#" for _ in range(W+2)])
G = {(i,j):[] for i in range(1,H+1) for j in range(1,W+1)}
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]==".":
            if S[i][j+1]==".":
                G[(i,j)].append((i,j+1))
            if S[i-1][j]==".":
                G[(i,j)].append((i-1,j))
            if S[i][j-1]==".":
                G[(i,j)].append((i,j-1))
            if S[i+1][j]==".":
                G[(i,j)].append((i+1,j))
tot = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]==".":
            tot += 1
dist = [[INFTY for j in range(W+2)] for i in range(H+2)]
d = [[0 for j in range(W+2)] for i in range(H+2)]
cur = (1,1)
dist[cur[0]][cur[1]] = 0
d[cur[0]][cur[1]] = 1
while True:
    for x in G[cur]:
        if d[x[0]][x[1]]==0:
            if dist[x[0]][x[1]]>dist[cur[0]][cur[1]]+1:
                dist[x[0]][x[1]] = dist[cur[0]][cur[1]]+1
    dmin = INFTY
    for i in range(1,H+1):
        for j in range(1,W+1):
            if d[i][j]==0:
                if dist[i][j]<dmin:
                    cur = (i,j)
                    dmin = dist[i][j]
    if dmin==INFTY:
        break
    else:
        d[cur[0]][cur[1]]=1
if dist[H][W]==INFTY:
    print(-1)
else:
    print(tot-2-dist[H][W]+1)

Submission status: Accepted

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def solve():
    def find_path(p0, p1):
        queue = deque()
        footsteps = dict()

        queue.append((p0, 0))

        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            if p == p1:
                return s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= pp[0] < width and 0 <= pp[1] < height and field[pp[1]][pp[0]] == '.' and pp not in footsteps:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

        return -1

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]

    s = find_path((0, 0), (width - 1, height - 1))

    if s < 0:
        return -1
    else:
        return "".join(field).count(".") - (s + 1)


def main():
    print(solve())


main()

Submission status: Accepted

Solution code:
import sys

H, W = [int(_) for _ in input().split()]
s = ["" for _ in range(H)]
for i in range(H):
    s[i] = input()
A = [[0, 0]]
d = [[] for _ in range(H)]
for i in range(0, H):
    for j in range(0, W):
        d[i].append(float('inf'))
d[0][0] = 0
while [H-1,W-1] not in A:
    
    if len(A) == 0:
        print(-1)
        sys.exit()


    res = float('inf')
    t_i = 0
    t_j = 0
    for i in range(len(A)):
        if d[A[i][0]][A[i][1]] < res:
            res = d[A[i][0]][A[i][1]]
            t_i = A[i][0]
            t_j = A[i][1]
    


    A.remove([t_i,t_j])

    if t_i - 1 >= 0 and s[t_i-1][t_j] == '.':
        if d[t_i-1][t_j] == float('inf'):
            A.append([t_i-1,t_j])
            d[t_i-1][t_j] = res + 1
        elif d[t_i-1][t_j] > res + 1:
            d[t_i-1][t_j] = res + 1



    if t_i + 1 <= H-1 and s[t_i+1][t_j] == '.':
        if d[t_i+1][t_j] == float('inf'):
            A.append([t_i+1,t_j])
            d[t_i+1][t_j] = res + 1
        elif d[t_i+1][t_j] > res + 1:
            d[t_i+1][t_j] = res + 1

   

    if t_j - 1 >= 0 and s[t_i][t_j-1] == '.':
        if d[t_i][t_j-1] == float('inf'):
            A.append([t_i,t_j-1])
            d[t_i][t_j-1] = res + 1
        elif d[t_i][t_j-1] > res + 1:
            d[t_i][t_j-1] = res + 1



    if t_j + 1 <= W-1 and s[t_i][t_j+1] == '.':
        if d[t_i][t_j+1] == float('inf'):
            A.append([t_i,t_j+1])
            d[t_i][t_j+1] = res + 1
        elif d[t_i][t_j+1] > res + 1:
            d[t_i][t_j+1] = res + 1

ans = d[H-1][W-1]

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

print(c-ans-1)

Submission status: Accepted

Solution code:
from queue import Queue
h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

memo=[[-1]*w for _ in range(h)]
def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

q=Queue()
q.put([0,0,0])
while not q.empty():
  bfs(q)
if memo[h-1][w-1]==-1:
  print(-1)
  exit()
cnt=0
for i in range(h):
  cnt+=S[i].count('.')
print(cnt-memo[h-1][w-1]-1)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
H, W = map(int, input().split())
L = []

for i in range(H):
  S = input()  
  L.append(list(1 if s == "." else 0 for s in S))
L = np.array(L)
S = np.zeros((H,W))
Q = deque(())
Q.append((0,0))

while Q:
  i, j = Q.popleft()
  for ti, tj in ((i+1, j), (i, j+1), (i-1, j), (i, j-1)):
    if 0 <= ti < H and 0 <= tj < W:
      if L[ti][tj] and S[ti][tj] == 0:
        S[ti][tj] = S[i][j] + 1
        Q.append((ti, tj))
print (int(np.sum(L) - S[-1][-1] - 1) if S[-1][-1] != 0 else -1)

Submission status: Accepted

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

white = 0
for i in range(H):
  white += S[i].count('.')

q = [(0,0)]
S[0][0] = 0
while q:
  qq = []
  for xy in q:
    x,y = xy
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
      if not(0 <= x+dx < W) or not(0 <= y+dy < H):
        continue
      elif S[y+dy][x+dx] != '.':
        continue
      S[y+dy][x+dx] = S[y][x] + 1
      qq.append((x+dx,y+dy))
  q = qq

print(white - S[-1][-1] -1 if S[-1][-1] != '.' else -1)

Submission status: Accepted

Solution code:
from collections import deque

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

cnt=0
for i in s:
    cnt+=i.count('.')

sy,sx=0,0
gy,gx=h-1,w-1

dist=[[-1]*w for i in range(h)]
dist[sy][sx]=0

que=deque()
que.append((sy,sx))

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

    if y==gy and x==gx:
        print(cnt-(dist[y][x]+1))
        exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<=h-1 and 0<=nx<=w-1 and s[ny][nx]=='.' and dist[ny][nx]==-1:
            que.append((ny,nx))
            dist[ny][nx]=dist[y][x]+1

print(-1)

Submission status: Accepted

Solution code:
#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

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

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(0)
    #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1 and s[i[0]][i[1]] == '.':
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] = 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if check[0][0] =='#':
    flag = False

if flag:
    print(h*w - sharp - key)
else:
    print(-1)

Submission status: Accepted

Solution code:
#Grid Repainting
from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
white=0
for i in range(h):
    for j in range(w):
        if field[i][j]==".":
            white+=1
start=[0,0]
goal=[h-1,w-1]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
count=0
que=deque([[[0,0]]])
field[0][0]="#"
while que:
    q=que.popleft()
    count+=1
    k=[]
    while q:
        p=q.pop()
        x=p[0]
        y=p[1]
        if x==h-1 and y==w-1:
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w:
                if field[nx][ny]!="#":
                    k.append([nx,ny])
                    field[nx][ny]="#"
    else:
        if k:
            que.append(k)
        continue
    break
else:
    print(-1)
    sys.exit()
print(white-count)

Submission status: Accepted

Solution code:
import collections

H,W=map(int,input().split())
S=[[10**10 for j in range(W)] for i in range(H)]

Q=collections.deque([])
S[0][0]=1

s=[]
cnt=0
for i in range(H):
  s=input()
  for j in range(W):
    if s[j]=="#":
      S[i][j]=-1
      cnt+=1
#print(S)

def bfs(i,j):
  if 0<=i+1<H and S[i][j]+1<S[i+1][j] and S[i+1][j]!=-1:
    Q.append([i+1,j])
    S[i+1][j]=S[i][j]+1
  if 0<=i-1<H and S[i][j]+1<S[i-1][j] and S[i-1][j]!=-1:
    Q.append([i-1,j])
    S[i-1][j]=S[i][j]+1
  if 0<=j+1<W and S[i][j]+1<S[i][j+1] and S[i][j+1]!=-1:
    Q.append([i,j+1])
    S[i][j+1]=S[i][j]+1
  if 0<=j-1<W and S[i][j]+1<S[i][j-1] and S[i][j-1]!=-1:
    Q.append([i,j-1])
    S[i][j-1]=S[i][j]+1

Q.append([0,0])
while len(Q):
  q=Q.popleft()
  bfs(q[0],q[1])
  #for i in range(H):
  #  print(S[i])
  #print("")
print(H*W-S[-1][-1]-cnt if S[-1][-1]!=10**10 else -1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
# 周りを#dで囲う
ss = ['#' + input() + '#' for i in range(H)]
ss = ['#' * (W + 2)] + ss + ['#' * (W + 2)]

# 初期の白の数を数える
numWhite = sum(map(lambda s: s.count('.'), ss))

# 上下左右
dij = [(0, -1), (0, 1), (-1, 0), (1, 0)]

# 各点への距離の初期値をINFに設定
dist = [[float('inf')] * (W + 2) for i in range(H + 2)]
# スタート地点の距離は1
dist[1][1] = 1

# O(1)で配列操作をする為にdequeを採用
# 操作未完了リストをqueueに追加していく
#  (x,y)で記入
Q = deque()
# start地点を追加
Q.append((1, 1))

# 操作未完了リストが空になるまで行う
while Q:
  # Qの左から取り出し
  i, j = Q.popleft()
  # 上下左右で同じ操作を行う
  for di, dj in dij:
    # 白でまだ距離が確定していなかったら操作を行う
    if (ss[i + di][j + dj] == '.') & (dist[i + di][j + dj] == float('inf')):
      # 距離を移動元から一つ増やす
      dist[i + di][j + dj] = dist[i][j] + 1
      # 操作未完了リストに追加
      Q.append((i + di, j + dj))

#　ゴールがINFなら到着できなかったので、-1を返す
if dist[H][W] == float('inf'):
    print(-1)
# ゴールできた場合、最初の白の数から最短距離を引く
else:
    print(numWhite - dist[H][W])

Submission status: Accepted

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

field=[[float('inf') for i in range(w)]for j in range(h)]

q=deque()
q.append((0,0))
field[0][0]=0

n=0
while q:
    y,x=q.popleft()
    n=max(n,field[y][x])
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf') and s[ny][nx]!='#':
            q.append((ny,nx))
            field[ny][nx]=field[y][x]+1

ans=0
check=field[h-1][w-1]

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

            
if field[h-1][w-1]!=float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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


def main():
    from collections import deque

    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    dist = [[float('inf') for _ in range(w)] for _ in range(h)]
    is_visited = [[False for _ in range(w)] for _ in range(h)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    white_count = 0

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

    # スコアの最大化：全ての白マス－最短距離で(H, W)まで移動するのに必要なマスの数
    # BFS
    # Initialize
    d = deque()
    d.append(tuple((0, 0)))
    dist[0][0] = 1
    is_visited[0][0] = True

    while d:
        di = d.popleft()

        for dy, dx in dxy:
            nx = dx + di[1]
            ny = dy + di[0]

            if (nx < 0 or w <= nx or ny < 0 or h <= ny):
                continue
            elif s[ny][nx] == '#':
                continue
            elif is_visited[ny][nx]:
                continue
            else:
                dist[ny][nx] = dist[di[0]][di[1]] + 1
                is_visited[ny][nx] = True
                d.append((ny, nx))

    if dist[h - 1][w - 1] == float('inf'):
        print(-1)
    else:
        print(white_count - dist[h - 1][w - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

H,W = II()
s = [list(map(str, input())) for _ in range(H)]

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


v = (0,0)
check_visited = [[False]*W for _ in range(H)]
check_visited[v[0]][v[1]] = True
S = [v]
flag = False
c = 1
while S:
    S1 = []
    for v1 in S:
        if v1[0]==H-1 and v1[1]==W-1:
            flag = True
            break
        if v1[0]-1>=0:
            if check_visited[v1[0]-1][v1[1]] == False and s[v1[0]-1][v1[1]] == '.':
                check_visited[v1[0]-1][v1[1]] = True
                S1.append((v1[0]-1,v1[1]))
        if v1[0]+1<=H-1:
            if check_visited[v1[0]+1][v1[1]] == False and s[v1[0]+1][v1[1]] == '.':
                check_visited[v1[0]+1][v1[1]] = True
                S1.append((v1[0]+1,v1[1]))
        if v1[1]-1>=0:
            if check_visited[v1[0]][v1[1]-1] == False and s[v1[0]][v1[1]-1] == '.':
                check_visited[v1[0]][v1[1]-1] = True
                S1.append((v1[0],v1[1]-1))
        if v1[1]+1<=W-1:
            if check_visited[v1[0]][v1[1]+1] == False and s[v1[0]][v1[1]+1] == '.':
                check_visited[v1[0]][v1[1]+1] = True
                S1.append((v1[0],v1[1]+1))
    else:
        S = S1
        c += 1
        continue
    break

if flag:
    print(w_count-c)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
wnum=0
field=[input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]=='.':
            wnum+=1
# スタートからゴールまでの最短経路をBFSで求め、wnumからその分を引けば、最大スコアが得られる。
dist=[[-1]*W for _ in range(H)]
dist[0][0]=0
que=deque()
que.append([0,0])
while que:
    s_h,s_w=que.popleft()
    for dh,dw in [[-1,0],[1,0],[0,-1],[0,1]]:
        nh=s_h+dh
        nw=s_w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:continue
        if field[nh][nw]=='#':continue
        if dist[nh][nw]!=-1:continue
        dist[nh][nw]=dist[s_h][s_w]+1
        que.append([nh,nw])
    
if dist[H-1][W-1]==-1:
    print(-1)
else:
    print(wnum-dist[H-1][W-1]-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
wnum=0
field=[input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]=='.':
            wnum+=1
# スタートからゴールまでの最短経路をBFSで求め、wnumからその分を引けば、最大スコアが得られる。
dist=[[-1]*W for _ in range(H)]
dist[0][0]=0
que=deque()
que.append([0,0])
while (len(que)!=0):
    s_h,s_w=que.popleft()
    for dh,dw in [[-1,0],[1,0],[0,-1],[0,1]]:
        nh=s_h+dh
        nw=s_w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:continue
        if field[nh][nw]=='#':continue
        if dist[nh][nw]!=-1:continue
        dist[nh][nw]=dist[s_h][s_w]+1
        que.append([nh,nw])
if dist[H-1][W-1]==-1:
    print(-1)
else:
    print(wnum-(dist[H-1][W-1]+1))

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque([[0,0]])
visited = [[-1 for i in range(w)]for j in range(h)]
visited[0][0] = 1
while queue:
    x,y = queue.popleft()
    if x!=0:
        if S[x-1][y] == '.' and visited[x-1][y] == -1:
            queue.append([x-1,y])
            visited[x-1][y] = visited[x][y] + 1
    if x!=h-1:
        if S[x+1][y] == '.' and visited[x+1][y] == -1:
            queue.append([x+1,y])
            visited[x+1][y] = visited[x][y] + 1
    if y!=0:
        if S[x][y-1] == '.' and visited[x][y-1] == -1:
            queue.append([x,y-1])
            visited[x][y-1] = visited[x][y] + 1
    if y!=w-1:
        if S[x][y+1] == '.' and visited[x][y+1] == -1:
            queue.append([x,y+1])
            visited[x][y+1] = visited[x][y] + 1

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

if visited[h-1][w-1] != -1:
    print(dots-visited[h-1][w-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w= map(int,input().split())
dist = [[-1 for _ in range(w)]for _ in range(h)]
y = [1,-1, 0, 0]
x = [0, 0, 1,-1]
graph = []
q = deque([(0,0)])
count = -2
for i in range(h):
    j = input()
    count += j.count(".")
    graph.append(j)
while q:
    v = q.popleft()
    for j in range(4):
        nh,nw = v[0]+y[j],v[1]+x[j]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "#" or dist[nh][nw] != -1:continue
        if nh == h-1 and nw == w-1:
            dist[nh][nw] = dist[v[0]][v[1]]+1
            break
        else:
            q.append((nh,nw))
            dist[nh][nw] = dist[v[0]][v[1]]+1
    else:continue
    break
else:print(-1);exit()
print(count-dist[h-1][w-1])

Submission status: Accepted

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

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

maze = [] # マス目
for _ in range(H):
    maze.append(input().strip())
move = {(1,0), (0,1), (-1,0), (0,-1)} # 動きのパターン

Inf = 10**9
def bfs():
    d = [[Inf]*W for _ in range(H)] # スタートからの最短経路の距離
    d[0][0] = 0

    q = collections.deque()
    q.append((0,0))
    while q:
        p = q.popleft() # 幅優先
        if p == (H-1, W-1):
            break # 幅優先なので、見つかった時点で最短経路
        for dh, dw in move:
            nh, nw = p[0] + dh, p[1] + dw # 次のマス
            if 0 <= nw and nw < W and 0 <= nh and nh < H: # 迷路の中か
                if maze[nh][nw] == "." and d[nh][nw] == Inf: # 移動可能で、かつ未訪問か
                    d[nh][nw] = d[p[0]][p[1]] + 1 # 幅優先なので確定して良い
                    q.append((nh, nw)) # 次のキューに入れる
    return d[H-1][W-1]

def main():
    d = bfs()
    if d == Inf:
        print(-1)
    else:
        x = 0
        for s in maze:
            x += s.count("#")
        print(W*H - x - (d+1))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
field=[[float('inf') for i in range(w)] for j in range(h)]

q=deque()
q.append((0,0))
field[0][0]=0

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

while q:
    y,x=q.popleft()
    
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<w and 0<=ny<h and field[ny][nx]==float('inf') and s[ny][nx]!='#':
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))
check=field[h-1][w-1]

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

print(ans if check!=float('inf') else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
field=[[float('inf') for i in range(w)] for j in range(h)]

q=deque()
q.append((0,0))
field[0][0]=0

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

while q:
    y,x=q.popleft()
    
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<w and 0<=ny<h and field[ny][nx]==float('inf') and s[ny][nx]!='#':
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))
check=field[h-1][w-1]

dic=defaultdict(int)
for i in range(h):
    for j in range(w):
        dic[field[i][j]]+=1
ans=0

for key,value in dic.items():
    if key!=float('inf') and key <=check:
        ans+=value-1
    elif key!=float('inf') and key >check:
        ans+=value
    

for i in range(h):
    for j in range(w):
        if field[i][j]==float('inf') and s[i][j]=='.':
            ans+=1
print(ans if check!=float('inf') else -1)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
S = tuple(input().rstrip() for _ in range(H))
a=0
d=[(1,0),(-1,0),(0,1),(0,-1)]
lity=[[0 for i in range(W)] for j in range(H)]
lity[0][0]=1
def roop()->None:
  p=[(0,0)]
  while p:
    x,y=p.pop(0)
    for dx,dy in d:
      if 0<=x+dx<H and 0<=y+dy<W and S[x+dx][y+dy]=='.' and lity[x+dx][y+dy]==0:
        p.append((x+dx,y+dy))
        lity[x+dx][y+dy]=lity[x][y]+1
roop()
white=sum(t.count(".") for t in S)
x=lity[-1][-1]
ans = white - x
if 0<x:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

a = [[False]*(w+2)]
for y in _in[1:]:
    a.append([False] + [x!='#' for x in y.strip()] + [False])
a.append([False]*(w+2))

ans = 0
for x in a:
    ans += sum(x)

s = deque()
s.append((1,1))

while s:
    ns = deque()
    for i, j in s:
        if i==h and j==w:
            ns = deque()
            break
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans -= 1

if i==h and j==w:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
S = tuple(input().rstrip() for _ in range(H))
a=0
d=[(1,0),(-1,0),(0,1),(0,-1)]
lity=[[0 for i in range(W)] for j in range(H)]
lity[0][0]=1
def roop()->None:
  p=[(0,0)]
  while p:
    x,y=p.pop(0)
    for dx,dy in d:
      if 0<=x+dx<H and 0<=y+dy<W and S[x+dx][y+dy]=='.' and lity[x+dx][y+dy]==0:
        p.append((x+dx,y+dy))
        lity[x+dx][y+dy]=lity[x][y]+1
roop()
white=sum(t.count(".") for t in S)
x=lity[-1][-1]
ans = white - x if x else -1
print(ans)

Submission status: Accepted

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

from collections import deque
q = deque([(0, 0)])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l[0][0] = 0

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

try:
    g = l[H-1][W-1]
    total = 0
    for _l in l:
        for i in _l:
            if i != '#':
                total += 1
    print(total - g - 1)
except:
    print(-1)