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:





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


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

S=[input() for i in range(H)]
S_check = [[False]*W for _ in range(H)]

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

Q = []
Q.append(start)

step = 0
is_reached = False

while Q:
    current = Q.pop(0)
    step = current[2]
    
    for i in range(4):
        next_pos = (current[0]+dx[i], current[1]+dy[i])

        if next_pos[0] < 0 or next_pos[0] > H-1 or next_pos[1] < 0 or next_pos[1] > W-1:
            continue
        elif S_check[next_pos[0]][ next_pos[1]]:
            continue
        elif next_pos == goal:
            is_reached = True
            break
        elif S[next_pos[0]][ next_pos[1]] == "#":
            continue
        else:
            S_check[next_pos[0]][ next_pos[1]] = True
            Q.append((next_pos[0], next_pos[1], step+1))

    if is_reached:
        break

cnt = 0
for i in range(H):
    for j in range(W):
       if S[i][j] == "#":
           cnt += 1
ans = -1
if is_reached:
    ans = H * W - step -1 - cnt
print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        i, j = q.popleft()
        grid[i - 1][j - 1] = "*"
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if i + x < 1 or i + x > h or j + y < 1 or j + y > w or grid[i + x - 1][j + y - 1] != "." or v[i + x - 1][j + y - 1] > 0:
                continue
            v[i + x - 1][j + y -
                         1] = v[i - 1][j - 1] + 1
            q.append((i + x, j + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("#"))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

from collections import deque


def main():
    def input(): return sys.stdin.readline()[:-1]
    H, W = map(int, input().split())

    graph = [input() for _ in range(H)]

    dist = [[-1] * W for _ in range(H)]
    queue = deque()

    H -= 1
    W -= 1
    
    # initialize
    queue.append((0, 0))
    dist[0][0] = 0
    cnt = 0
    for g in graph:
        cnt += g.count(".")

    while queue:
        vx, vy = queue.popleft()

        if (vx, vy) == (W, H):
            break

        dxdy = [(1,0), (0, 1), (-1, 0), (0, -1)]
        for dx, dy in dxdy:
            if (vx + dx > W) or (vy + dy > H): continue
            elif (vx + dx < 0) or (vy + dy < 0): continue

            elif graph[vy + dy][vx + dx] == ".":
                if dist[vy + dy][vx + dx] == -1:
                    queue.append((vx + dx, vy + dy))
                    dist[vy + dy][vx + dx] = dist[vy][vx] + 1
                    

            elif graph[vy + dy][vx + dx] == "#": continue
            else: continue

    # can't goal
    if dist[H][W] == -1:
        print(-1)
    else:
        # the number of "." - min(dist) - "." of start
        print(cnt - dist[H][W] - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque

H,W=map(int,input().split())
dots=H*W
field=[]
for _ in range(H):
    tmp=input()
    dots-=tmp.count("#")
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
dist=[[-1]*W for _ in range(H)]
dist[0][0]=0
que=deque()
que.append([0,0])

while que:
    y,x=que.popleft()
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

score=-1
goal=dist[H-1][W-1]
if goal!=-1:
    score=dots-goal-1
print(score)

Submission status: Accepted

Solution code:
from collections import deque
import copy
H,W = map(int, input().split())
s=[list(input()) for i in range(H)]
#H,W=3,3
#s=[['.', '.', '#'], ['#', '.', '.'], ['.', '.', '.']]

ss=copy.deepcopy(s)
q=deque([[0,0]])#(H,W)
ss[0][0]=0
move=[[1,0],[0,1],[0,-1],[-1,0]]
num=0
t=False
while q:
    num+=1
    for i in range(len(q)):
        b=q.popleft()
        #print(b)
        if b==[H-1,W-1]:
            t=True
            num-=1
            break
        for m in move:
         #  print(m)
            if 0<=b[0]+m[0]<=H-1 and 0<=b[1]+m[1]<=W-1 and ss[b[0]+m[0]][b[1]+m[1]]=='.':
                ss[b[0]+m[0]][b[1]+m[1]]=num
                q.append([b[0]+m[0],b[1]+m[1]])
    else:
        continue
    break
if not t :
    print('-1')
else:
    x=num
    b=H-1,W-1
    ss[b[0]][b[1]]='#'
    while x!=0:
        for m in move:
            if 0<=b[0]+m[0]<=H-1 and 0<=b[1]+m[1]<=W-1 and ss[b[0]+m[0]][b[1]+m[1]]==x-1:
                x=x-1
                ss[b[0]+m[0]][b[1]+m[1]]='#'
                b=b[0]+m[0],b[1]+m[1]
                break
    ans=0
    for h in range(H):
        for w in range(W):
            if ss[h][w]!='#':
                ans+=1
    print(ans)

Submission status: Accepted

Solution code:
H,W = list(map(int,input().split()))
N=H*W

#壁のノード
wall=[]
for h in range(H):
    for w_idx,w in enumerate(list(input())):
        if w == '#':
            wall.append(W*h+w_idx+1)
#道のノード        
path=[_ for _ in range(1,N+1) if _ not in wall]

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N):
    n=n+1
    if n not in wall:
        up = n-W
        if up > 0 and up not in wall:
            ad[n].append(up)
            
        down = n+W
        if down <= N and down not in wall:
            ad[n].append(down)
            
        left = n-1
        if n % W != 1 and left not in wall and left > 0:
            ad[n].append(left)
        
        right = n+1
        if n % W != 0 and right not in wall:
            ad[n].append(right)   

from collections import deque
    
color = {}
for n in range(N):
    color[n+1] = -1

depth = {}
for n in range(N):
    depth[n+1] = -1
    
parent = {}
for n in range(N):
    parent[n+1] = -1
    
group = {}
    
group_= 0
for p in path:
    if color[p] != -1: 
        continue
    elif color[p] == -1: 
        start = p
        color[start] = 0
        que = deque([start])
        visit = deque([])
        group_+=1
        group[group_] = [start]

    depth[start] = 0
    while len(que) > 0:
        start = que[0]
        for v in ad[start]:
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1
                group[group_].append(v)
                parent[v] = start
                
        color[start] = 1
        visit.append(que.popleft())
        
ans_ = {}
for n in range(N):
    ans_[n+1]=1

for w in wall:
    ans_[w]=0

start = N
short_path=[]

while True:
    short_path.append(start)
    start = parent[start]
    if start == 1:
        short_path.append(start)
        for s in short_path:
            ans_[s] = 0
        print(sum(ans_.values()))
        break
        
    if start == -1:
        print(start)
        break

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
# maze = [list(map(int, input().split())) for i in range(H)]
maze = []
s_init_cnt = 0
for i in range(H):
    gyo = list(input())
    s_init_cnt += gyo.count('.')
    maze.append(gyo)

#print(maze)
#print(s_init_cnt)

direction = [(-1, 0), (0, -1), (1, 0), (0, 1)]
reached = [[-1] * W for i in range(H)]
reached[0][0] = 1
from collections import deque


def bfs():
    d = deque([[0, 0]])
    while len(d) > 0:
        px, py = d.popleft()
        for dx, dy in direction:
            tx = px + dx
            ty = py + dy
            if tx >= H or ty >= W or tx < 0 or ty < 0:
                continue
            if reached[tx][ty] != -1 or maze[tx][ty] == '#':
                continue
            else:
                reached[tx][ty] = reached[px][py] + 1
                d.append([tx, ty])
bfs()
ans = reached[H-1][W-1]
if ans == -1:
    print(ans)
else:
    ans = s_init_cnt - ans
    print(ans)

Submission status: Accepted

Solution code:
def main():
	H, W = [int(n) for n in input().split(" ")]
	iniBlack = 0
	S = []
	S.append(["X"] * (W + 2))
	for i in range(H):
		row = list(input())
		iniBlack += row.count("#")
		S.append(["X"] + row + ["X"])
	S.append(["X"] * (W + 2))

	to_visit = [{"row": 1, "col": 1, "step": 1}]
	checked = [[0] * (W + 2) for i in range(H + 2)]
	checked[1][1] = 1

	while len(to_visit) > 0:
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
			r = r0 + d[0]
			c = c0 + d[1]
			if S[r][c] == "." and checked[r][c] == 0:
				to_visit.append({"row": r, "col": c, "step": s0 + 1})
				checked[r][c] = s0 + 1

	if checked[H][W] == 0:
		print(-1)
		return 0
	print(H * W - iniBlack - checked[H][W])

main()

Submission status: Accepted

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

H,W = map(int,input().split())
sy, sx = 0,0
gy, gx = H-1,W-1
D = [list(input()) for i in range(H)]
Bs = 0
for i in range(H):
    Bs += D[i].count("#")

Q = deque()
Q.append((sy,sx))
dist = [[-1]*W for i in range(H)]
dist[sy][sx] = 0
dx = [1,0,-1,0]
dy = [0,-1,0,1]

while Q:
    x,y = Q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<=W-1 and 0<=ny<=H-1 and D[ny][nx]!="#" and dist[ny][nx] == -1:
            Q.append((nx,ny))
            dist[ny][nx] = dist[y][x]+1

print(H*W-Bs-1-dist[gy][gx] if dist[gy][gx]!=-1 else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(H, W, s):
    from heapq import heappop, heappush
    blacks = sum(sum(e == "#" for e in ss) for ss in s)
    hq = [(1, (0, 0))]
    visited = set()
    while hq:
        c, h_w = heappop(hq)
        h, w = h_w
        if h_w in visited:
            continue
        if h_w == (H-1, W-1):
            return H * W - blacks - c
        visited.add(h_w)
        for dh, dw in zip((0, 0, 1, -1), (1, -1, 0, 0)):
            nh, nw = nh_nw = h + dh, w + dw
            if not(0 <= nh < H and 0 <= nw < W):
                continue
            if nh_nw in visited:
                continue
            if s[nh][nw] == "#":
                continue
            heappush(hq, (c+1, nh_nw))
    return -1

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    print(solve(H, W, s))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
def cal():
    import queue
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[-1]*w for _ in range(h)]
    INF = float('inf')
    count, ans = 0, INF
    for i in range(h):
        for j in range(w):
            if s[i][j] != '#':
                cost[i][j] = INF
            else:
                count += 1        
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#' and cost[x][y] == INF:
                    cost[x][y] = c2+1
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

si,sj=0,0
gi,gj=h-1,w-1
INF=float('inf')
dist=[[INF for i in range(w)] for j in range(h)]
dist[si][sj]=1
Q=deque()
Q.append((si,sj))
while Q:
  pi,pj=Q.popleft()
  for di,dj in [[-1,0],[1,0],[0,-1],[0,1]]:
    ni,nj=pi+di,pj+dj
    if 0>ni or ni>h-1:
      continue
    if 0>nj or nj>w-1:
      continue
    if G[ni][nj]=='#':
      continue
    if dist[ni][nj]>dist[pi][pj]+1:
      dist[ni][nj]=dist[pi][pj]+1
      Q.append((ni,nj))
ans=0      
for i in range(h):
  for j in range(w):
    if G[i][j]=='.':
      ans+=1
ans-=dist[gi][gj]
if ans<0:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
inf = 101
s = [''] * H
cnt = 0
for i in range(H):
	s[i] = input()
	cnt += s[i].count('.')
d = [[inf] * W for i in range(H)]
from collections import deque
queue = deque([[0, 0]])
d[0][0] = 0

while queue:
	x, y = queue.popleft()
	if x+1 == H and y+1 == W:
		break
	dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
	for i in range(4):
		nx, ny = x + dx[i], y + dy[i]
		if 0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != '#' and d[nx][ny] == inf:
			queue.append([nx, ny])
			d[nx][ny] = d[x][y] + 1

if d[H-1][W-1] == inf:
	print(-1)
else:
	print(cnt-d[H-1][W-1]-1)

Submission status: Accepted

Solution code:
import collections
import math


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

c=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[0 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=='#':
            d[i][j]=-1
        else:
            d[i][j]=inf
            ans+=1


d[0][0]=0
queue=collections.deque([[0,0]])
gy,gx=H-1,W-1

moves=[[1,0],[-1,0],[0,1],[0,-1]]

flag=False
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        
        if 0<=ny and ny<H and 0<=nx and nx<W and c[ny][nx]=='.' and d[ny][nx]==inf:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])
            if ny==gy and nx==gx:
                print(ans-d[ny][nx]-1)
                exit()
print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    H, W = map(int, input().split())
    S = []
    num_path = 0
    for _ in range(H):
        s = input()
        num_path += s.count('.')
        S.append(s)

    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    distance = [[1] * W for _ in range(H)]
    queue = deque([(0, 0)])
    while queue:
        y, x = queue.popleft()
        if y == H - 1 and x == W - 1:
            break
        for dy, dx in move:
            ny = y + dy
            nx = x + dx
            if (1
                    and 0 <= ny < H
                    and 0 <= nx < W
                    and distance[ny][nx] == 1
                    and S[ny][nx] == '.'):
                queue.append((ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    if distance[H - 1][W - 1] == 1:
        print(-1)
    else:
        print(num_path - distance[H - 1][W - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Q = deque([[0,0]])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0

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

    for nh, nw in [[h+1,w],[h-1,w],[h,w-1],[h,w+1]]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] + 1
            Q.append([nh,nw])

if dist[H-1][W-1] == -1:
    print(-1)
else:
    ans = 0
    for s in S: ans += s.count(".")
    print(ans - dist[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
def abc088d_grid_repainting():
    import heapq
    h, w = map(int, input().split())
    maze = []
    cnt = h * w
    for _ in range(h):
        s = input()
        maze.append(s)
        cnt -= s.count('#')
    q = [(1, 0, 0)]
    heapq.heapify(q)
    check = [[False] * w for _ in range(h)]
    while len(q) != 0:
        dis, x, y = heapq.heappop(q)
        if (x, y) == (h - 1, w - 1):
            print(cnt - dis)
            return
        for dx, dy in zip([0, 0, 1, -1], [1, -1, 0, 0]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and not check[x + dx][y + dy]:
                check[x + dx][y + dy] = True
                heapq.heappush(q, (dis+1, x + dx, y + dy))
    print('-1')
abc088d_grid_repainting()

Submission status: Accepted

Solution code:
import queue
H , W = list(map(int, input().split()))
S = [input() for _ in range(H)]
Sum = 0
for i in range(H):
  for j in range(W):
    Sum += (S[i][j] == '#')
start = [1, 1, 1]
visited = [[0] * W for _ in range(H)]
visited[0][0] = 1
Q = queue.Queue()
Q.put(start)
now = start
while(now[:2] != [H, W] and not Q.empty()):
  now = Q.get()
  for i in range(2):
    for j in range(2):
      h = now[0] + ((-1) ** i + (-1) ** j) // 2
      w = now[1] + ((-1) ** i - (-1) ** j) // 2
      if(1 <= h and h <= H and 1 <= w and w <= W and visited[h - 1][w - 1] == 0 and S[h - 1][w - 1] == '.'):
        visited[h - 1][w - 1] = 1
        Q.put([h, w, now[2] + 1])
if(now[:2] == [H, W]):
  print(H * W - Sum - now[2])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
h,w=map(int,input().split())
ss=[list(input()) for i in range(h)]
num=0
for i in range(h):
    num+=ss[i].count('.')

visited=[[0 for i in range(w)] for j in range(h)]
queue=[]
queue.append([0,0])
ss[0][0]='fin'
dy=[1,0,-1,0]
dx=[0,1,0,-1]


while len(queue)>0:
    now=queue.pop(0)
    for i in range(4):
        x= now[1]+dx[i]
        y= now[0]+dy[i]
        if 0<=x<w and 0<=y<h :
            if ss[y][x]=='.' and visited[y][x]==0:
                visited[y][x]=visited[now[0]][now[1]]+1
                queue.append([y,x])
            if x==w-1 and y==h-1:
                print(num-visited[y][x]-1)
                sys.exit()
print(-1)

Submission status: Accepted

Solution code:
# 白だけ動いて(0,0)から(H-1, W-1)に行く
# その際にできるだけ黒を増やす
# 全体の白から最短距離を除いたものが答え

from collections import deque


H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .は白、#は黒
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

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

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

    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H-1 < moved_y or moved_x < 0 or W-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue

        visited[moved_y][moved_x] = visited[y][x] + 1
        q.append((moved_y, moved_x))

min_route = visited[H-1][W-1]

if min_route == -1:
    answer = -1
else:
    total_white = 0
    for row in grid:
        total_white += row.count('.')

    answer = total_white - min_route - 1

print(answer)

Submission status: Accepted

Solution code:
from queue import Queue
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

H, W = map(int, input().split())
S = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
que = Queue()

# 初期条件
dist[0][0] = 0
que.put((0, 0))

# 幅優先探索
while not que.empty():
    x, y = que.get()
    for dir in range(4):
        x2, y2 = x + dx[dir], y + dy[dir]
        if x2 < 0 or x2 >= H or y2 < 0 or y2 >= W or S[x2][y2] == '#':
            continue
        if dist[x2][y2] != -1:
            continue
        dist[x2][y2] = dist[x][y] + 1
        que.put((x2, y2))

# 白マス数
white = sum(sum(1 if S[x][y] == '.' else 0 for y in range(W)) for x in range(H))

# 答え
print(white - dist[H-1][W-1] - 1 if dist[H-1][W-1] != -1 else -1)

Submission status: Accepted

Solution code:
import copy
h,w =map(int,input().split())

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        now = copy.copy(steps[0])
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                now[1] += k[1]
                if s[now[0]][now[1]] == 10**5:
                    if not [now[0],now[1]] in steps:
                        steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    # if s[steps[0][0]][steps[0][1]] ==0:
    #     steps.pop(0)
    #     continue
    if s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                s[steps[0][0]][steps[0][1]]=min(s[steps[0][0]+l[0]][steps[0][1]+l[1]]+1,s[steps[0][0]][steps[0][1]])
    steps.pop(0)
if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**5:
    print(-1)
else:
    print(white-1 - s[h-1][w-1])

Submission status: Accepted

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

# In[47]:


from collections import deque


# In[50]:


H,W = map(int, input().split())
grid = [list("#"*(W+2))]
b_cnt = 0
for _ in range(H):
    tmp = list(input())
    grid.append(["#"]+tmp+["#"])
grid.append(list("#"*(W+2)))


# In[52]:


grid[1][1] = 1
q = deque([[1,1]])
move = [
    [1,0],[-1,0],[0,1],[0,-1]
]
while q:
    x,y = q.popleft()
    for dx,dy in move:
        if grid[x+dx][y+dy] == ".":
            grid[x+dx][y+dy] = grid[x][y]+1
            q.append([x+dx,y+dy])
if grid[H][W] == ".":
    print(-1)
else:
    print((H+2)*(W+2) - sum(g.count("#") for g in grid) - grid[H][W])


# In[ ]:

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

sq=[list(input()) for i in range(H)]

pos=[[0,0,0]]
g=True

while pos!=[]:
    y,x,depth=pos.pop(0)

    if y==H-1 and x==W-1:
        g=False
        break
    
    if x-1>=0:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
    if x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
    if y-1>=0:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    if y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])

if g==True:
    print(-1)
else:
    temp=0
    for k in range(H):
        for m in range(W):
            if sq[k][m]=="#":
                temp+=1


    print(H*W-temp-depth-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

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

d=deque([(0,0)])
distance=[[-1]*W for _ in range(H)]
distance[0][0]=0
goal_distance=0

while d:
  h,w=d.popleft()
  if h==H-1 and w==W-1:
    goal_distance=distance[h][w]
    break
  
  if h-1>=0 and S[h-1][w]=='.':
    d.append((h-1,w))
    distance[h-1][w]=distance[h][w]+1
    S[h-1][w]='#'
    
  if h+1<=H-1 and S[h+1][w]=='.':
    d.append((h+1,w))
    distance[h+1][w]=distance[h][w]+1
    S[h+1][w]='#'
    
  if w-1>=0 and S[h][w-1]=='.':
    d.append((h,w-1))
    distance[h][w-1]=distance[h][w]+1
    S[h][w-1]='#'
    
  if w+1<=W-1 and S[h][w+1]=='.':
    d.append((h,w+1))
    distance[h][w+1]=distance[h][w]+1
    S[h][w+1]='#'
else:
  if distance[H-1][W-1]==-1:
    print(-1)
    sys.exit()

print(count-(goal_distance+1))

Submission status: Accepted

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

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

dxdy = [[1,0],[0,1],[-1,0],[0,-1]]

queue = deque()
queue.append([0,0,1])
visited[0][0]=1

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and visited[nx][ny]==0 and mp[nx][ny]!="#":
            visited[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*visited[l]) for l in range(h)]
            #print("---------------")            

if visited[-1][-1]==0:
    print(-1)
    sys.exit()

cnt = 0
for i in range(h):
    for j in range(w):
        if mp[i][j]!="#":
            cnt += 1

print(cnt-visited[-1][-1])

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    h,w = LI()
    board = [["#" for _ in range(w+2)]]
    num = 0
    for _ in range(h):
        line = ["#"] + list(S()) + ["#"]
        num += line.count(".")
        board.append(line)
    board.append(["#" for _ in range(w+2)])
    
    queue = collections.deque([(1,1)])
    explored = {(1,1)}
    nbh = [[0,1],[0,-1],[1,0],[-1,0]]
    level = 0
    cnt = 0
    
    while len(queue)!=0 and (h,w) not in explored:
        if cnt==0:
            level+=1
            cnt=len(queue)
        nxt = queue.popleft()
        for dx,dy in nbh:
            ex = (nxt[0]+dx, nxt[1]+dy)
            if board[ex[0]][ex[1]] == ".":
                if ex not in explored:
                    explored.add(ex)
                    queue.append(ex)
        cnt -= 1
    ans = num-(level+1) if (h,w) in explored else -1
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
field = [input() for _ in range(h)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
white = 0
for i in range(h):
    white += field[i].count(".")
cnt = [[-1]*w for _ in range(h)]
cnt[0][0] = 0
q = deque([[0, 0]])

while q:
    y, x = q.pop()
    for dy, dx in d:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < h and 0 <= nx < w and field[ny][nx] == "." and cnt[ny][nx] < 0:
            cnt[ny][nx] = cnt[y][x] + 1
            q.appendleft([ny, nx])
        if ny == h-1 and nx == w-1:
            print(white - cnt[h-1][w-1] - 1)
            exit()

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

s = 0
for c in S:
    s += c.count('.')

que = deque()
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
st = (0, 0)
que.append(st)
dydx = [(1, 0), (0, 1), (-1, 0), (0, -1)]

while que:
    p, q = que.popleft()

    for dy, dx in dydx:
        if 0 <= p+dy and p+dy < H and 0 <= q+dx and q+dx < W:
            if dist[p+dy][q+dx] != -1 or S[p+dy][q+dx] != '.':
                continue

            dist[p+dy][q+dx] = dist[p][q] + 1
            que.append((p+dy, q+dx))

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

Submission status: Accepted

Solution code:
from collections import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+list(["#"]+list(input())+["#"] for h in range(H))+[(W+2)*["#"]]
S[1][1] = 1
Q = deque([[1,1]])
D = [[1,0],[-1,0],[0,1],[0,-1]]

while Q:
  x,y = Q.popleft()
  for dx,dy in D:
    if S[x+dx][y+dy]==".":
      S[x+dx][y+dy] = S[x][y]+1
      Q.append([x+dx,y+dy])

if S[H][W]==".":
  print(-1)
else:
  print((H+2)*(W+2)-sum(s.count("#") for s in S)-S[H][W])

Submission status: Accepted

Solution code:
from collections import *
H,W = map(int,input().split())
S = [input() for h in range(H)]
V = [W*[0] for h in range(H)]
V[0][0] = 1
Q = deque([(0,0)])
while Q:
  x,y = Q.popleft()
  for dx,dy in ((-1,0),(0,-1),(1,0),(0,1)):
    if 0<=x+dx<H and 0<=y+dy<W and V[x+dx][y+dy]==0 and S[x+dx][y+dy]==".":
      V[x+dx][y+dy] = V[x][y]+1
      Q.append((x+dx,y+dy))

if V[H-1][W-1]==0:
  print(-1)
else:
  print(H*W-sum(s.count("#") for s in S)-V[H-1][W-1])