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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



def main():
    h, w = LI()
    grid = SRL(h)
    cnt = 0
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.':
                cnt += 1
                grid[y][x] = INF



    que = deque([(0, 0)])
    grid[0][0] = 1
    while que:
        x, y = que.pop()
        cost = grid[y][x]
        for i, j in [(0,1),(1,0),(-1,0),(0,-1)]:
            nxt_x, nxt_y = x + i, y + j
            if not (0<=nxt_x<w and 0<=nxt_y<h):
                continue
            elif grid[nxt_y][nxt_x] != '#' and grid[nxt_y][nxt_x] > cost + 1:
                grid[nxt_y][nxt_x] = cost + 1
                que += [(nxt_x, nxt_y)]


    if grid[h-1][w-1] == INF:
        return -1


    return cnt - grid[h-1][w-1]







print(main())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
q = [(0, 0, 0)]
while q :
    cost, cx, cy = heappop(q)
    if cost >= dist[cy][cx] :
        continue
    dist[cy][cx] = cost
        
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
        if 0 <= cx + dx < W and 0 <= cy + dy < H and s[cy+dy][cx+dx] != '#' :
            heappush(q, (cost+1, cx+dx, cy+dy))
            
if dist[H-1][W-1] == float('inf') :
    print(-1)
else :
    ret = 0
    for s_ in s :
        ret += s_.count('#')
    print(H * W - ret - dist[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())

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

    cnt = 0
    for i in range(H):
        cnt += field[i].count('.')
    
    def bfs():
        d = [[float('inf')] * W for i in range(H)]

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

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

        while que:
            y,x = que.popleft()
            if y == H - 1 and x == W - 1:
                return d[y][x]

            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] != '#' and d[ny][nx] == float('inf'):
                    que.append((ny,nx))
                    d[ny][nx] = d[y][x] + 1

        return -1

    num = bfs()

    if num == -1:
        print(num)
    else:
        print(cnt - num)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

h, w = getList()
INF = 1000000000

dist = [[INF for i in range(w)] for j in range(h)]
grid = []
udlr = [(0, 1), (0, -1), (-1, 0), (1, 0)]

white = 0
for i in range(h):
    state = input().strip()
    grid.append(state)
    white += state.count(".")

dist[0][0] = 1
def bfs(grid, dist):
    q = deque([])
    q.append((0, 0))
    while(q):
        a, b = q.popleft()
        # print(a, b)
        cur = dist[a][b]
        for mv in udlr:
            c, d = mv
            e, f = a + c, b + d
            if e >= 0 and e < h and f >= 0 and f < w:
                if grid[e][f] == ".":
                    if dist[e][f] > cur + 1:
                        dist[e][f] = cur + 1
                        q.append((e, f))

bfs(grid, dist)

# for g in grid:
#     print(g)
# for d in dist:
#     print(d)
if dist[h-1][w-1] == INF:
    print(-1)

else:
    print(white - dist[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque

def dfs(stage , visited , start_x,start_y,goal_x,goal_y):
    queue = deque([[start_x,start_y]])
    visited[start_x][start_y] = 1
    while queue:
        x , y = queue.popleft()
        if [x , y] == [goal_x,goal_y]:
            return visited[x][y]

        for dx , dy in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x , new_y = x + dx , dy + y
            #print(new_x,new_y)
            if 0 <= new_x <= goal_x and 0 <= new_y <= goal_y  and stage[new_x][new_y] == "." and visited[new_x][new_y] == -1:
                #print(new_x , new_y)
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x,new_y])
    print("-1")
    exit(0)
if __name__ == "__main__":
    H , W = map(int , input().split())
    stage = []
    for _ in range(H):
        stage.append(list(input()))
    start_x,start_y ,goal_x,goal_y = 0,0,H-1,W-1
    visited = [[-1] * W for _ in range(H)]
    #print(visited)
    #print(stage)
    #print(visited[0][1])
    sum = 0
    for value in stage:
        sum += value.count('.')
    #print(sum)
    print(sum - dfs(stage,visited,start_x,start_y,goal_x,goal_y))

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
map = [list(input()) for _ in range(h)]
dis = [[float("inf")]*w for _ in range(h)]
dy = [1,0,-1,0]
dx = [0,1,0,-1]
que = deque([])
que.append((0,0))
dis[0][0]=1
count = 0
for i in range(h):
    for j in range(w):
        if map[i][j]=="#":
            count+=1

while que:
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
        break
    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if 0<=ny<h and 0<=nx<w and map[ny][nx]!="#" \
           and dis[ny][nx]==float("inf"):
            que.append((ny,nx))
            dis[ny][nx]=dis[p[0]][p[1]]+1

print(h*w-dis[h-1][w-1]-count if dis[h-1][w-1]!=float("inf") else -1)

Submission status: Accepted

Solution code:
from queue import Queue
import sys

def check(fl, y, x):
  mark = fl[y][x]
  if mark == '.': return True
  else: return False

def run():
  q = Queue()
  H, W = map(int, input().split())
  fl_list = [['#']*(W+2)]
  num_white = 0
  for h in range(H):
    fl = list('#'+input()+'#')
    num_white += fl.count('.')
    fl_list.append(fl)
  fl_list.append(['#']*(W+2))
  q.put([1,1,0])
  n_list = [0, 0, 1, -1]
  i_list = [1, -1, 0, 0]
  while True:
    if q.empty(): print(-1); sys.exit()
    y, x, t = q.get()
    if (y == H) and (x == W): break
    for n, i in zip(n_list, i_list):
      if check(fl_list, y+n, x+i):
        fl_list[y+n][x+i] = '#'
        q.put([y+n, x+i, t+1])
      
  print(num_white - (t+1))

run()

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain


class Solver:
    def __init__(self, m):
        self.m = m
        self.label = [[-1 for _ in range(len(m[0]))] for _ in range(len(m))]

    def bfs(self, s, g):
        queue = deque()
        start = [a - 1 for a in s]
        goal = [a - 1 for a in g]
        queue.append(start)
        self.label[start[0]][start[1]] = 0
        while len(queue) > 0:
            node = queue.popleft()
            y, x = node
            dist = self.label[y][x] + 1
            if y > 0:
                if self.m[y - 1][x] != "#" and self.label[y - 1][x] == -1:
                    if y-1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y - 1, x])
                        self.label[y - 1][x] = dist
            if y < len(self.m)-1:
                if self.m[y + 1][x] != "#" and self.label[y + 1][x] == -1:
                    if y+1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y + 1, x])
                        self.label[y + 1][x] = dist
            if x > 0:
                if self.m[y][x - 1] != "#" and self.label[y][x - 1] == -1:
                    if y == goal[0] and x-1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x-1])
                        self.label[y][x-1] = dist
            if x < len(self.m[0])-1:
                if self.m[y][x + 1] != "#" and self.label[y][x + 1] == -1:
                    if y == goal[0] and x+1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x+1])
                        self.label[y][x + 1] = dist
        return -1


def main():
    H, W = list(map(int, input().split()))
    m = [list(input()) for _ in range(H)]
    sum = list(chain.from_iterable(m)).count(".")

    solver = Solver(m)
    ans = solver.bfs([1, 1], [H, W])
    if ans == -1:
      print(-1)
      quit()
    print(sum - ans -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
r,c=map(int,input().split())
grid=[input() for _ in [0]*r]
ans=sum([grid[i].count(".") for i in range(r)])
visit=[[grid[i][j]=="#" for j in range(c)] for i in range(r)]
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0
q=[[0,0]]
flag=False
while q:
    qq=[]
    while q:
        i,j=q.pop()
        for dx,dy in d:
            if 0<=i+dx<r and 0<=j+dy<c:
                if i+dx==r-1 and j+dy==c-1:
                    flag=True
                if visit[i+dx][j+dy]==False:
                    visit[i+dx][j+dy]=True
                    qq.append([i+dx,j+dy])
    q=qq
    cnt+=1
    if flag==True:
        break
if flag==False:
    print(-1)
else:
    print(ans-cnt-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]
dflt_cnt=0
for i in range(H):
    dflt_cnt+=s[i].count(".")
que=deque([(0,0)])
step=[[-1]*W for _ in range(H)]
step[0][0]=0
move_h=[1,0,-1,0]
move_w=[0,1,0,-1]
cnt=1
while que:
    v=que.popleft()
    if v[0]==H-1 and v[1]==W-1:
        cnt+=step[H-1][W-1]
        break
    for i in range(4):
        next_h=v[0]+move_h[i]
        next_w=v[1]+move_w[i]
        if 0<=next_h<H and 0<=next_w<W and s[next_h][next_w]=="." and step[next_h][next_w]==-1:
            que.append((next_h,next_w))
            step[next_h][next_w]=step[v[0]][v[1]]+1
print(dflt_cnt-cnt if cnt!=1 else -1)

Submission status: Accepted

Solution code:
from collections import deque
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

que = deque() #座標と距離を保存
que.append((1,1,0)) #スタートの座標と距離を入力

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

while que:
    i,j,k = que.popleft() #先頭を取得
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
            distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
            que.append((i+di,j+dj,k+1)) #queの末尾に追加

#初期の道のカウント
road = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            road = road + 1

if distance[h-2][w-2] != float('inf'):
    minimum_distance = distance[h-2][w-2]
else:
    minimum_distance = road

print(road - minimum_distance - 1)

Submission status: Accepted

Solution code:
import sys
import copy
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def bfs():
    d = [[-1] * w for _ in range(h)]

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

    while que:
        x, y = que.popleft()
        if x == h - 1 and y == w - 1:
            break
        for dx, dy in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == -1:
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1

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

h, w = na()
maze = [list(input()) for _ in range(h)]
ct = 0
for i in range(h):
    ct += maze[i].count("#")
res = bfs()
if bfs() == -1:
    print(-1)
else:
    print(h * w - bfs() - 1 - ct)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
board = [0]*(H+2)
board[0] = [1]*(W+2)
total = 0
for i in range(1,H+1):
    board[i] = [1]+list(1 if c == '#'else 0 for c in input())+[1]
    total += sum(1 for c in board[i] if c == 0)
board[H+1] = [1]*(W+2)

D = [[10e10] * (W+2) for _ in range(H+2)]
D[1][1] = 0
from heapq import heappush, heappop

q = [(0, (1, 1))]

while q:
    d, (i, j) = heappop(q)
    alt = d + 1

    for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if board[x][y] == 0:
            if D[x][y] > alt:
                D[x][y] = alt
                heappush(q, (alt, (x, y)))

#for r in range(H+2): print(*[board[r][c] for c in range(W+2)])
#for r in range(H+2): print(*[D[r][c] for c in range(W+2)])
if D[H][W] == 10e10:
    print(-1)
else:
    print(total - D[H][W] - 1)

Submission status: Accepted

Solution code:
import sys
import copy

h, w = map(int, sys.stdin.readline().split())

maps = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

def calcdist(maps, start, end, h, w):
    nextlist = []
    nextlist.append(start)
    count = 1
    while True:
        nexnex = []
        for i in nextlist:
            if i[0] == end[0] and i[1] == end[1]:
                return count
            if i[0] > 0 and maps[i[0] -1][i[1]] == '.':
                maps[i[0] -1][i[1]] = '#'
                nexnex.append([i[0] -1, i[1]])
            if i[0] < h-1 and maps[i[0] +1][i[1]] == '.':
                maps[i[0] +1][i[1]] = '#'
                nexnex.append([i[0] +1, i[1]])
            if i[1] > 0 and maps[i[0]][i[1]-1] == '.':
                maps[i[0]][i[1]-1] = '#'
                nexnex.append([i[0], i[1]-1])
            if i[1] < w-1 and maps[i[0]][i[1]+1] == '.':
                maps[i[0]][i[1]+1] = '#'
                nexnex.append([i[0], i[1]+1])
        nextlist = nexnex
        count += 1
        if len(nexnex) == 0:
            return -1
    return count

kabe = 0

for i in range(h):
    for j in range(w):
        if maps[i][j] == '#':
            kabe += 1

total = 0
dist = calcdist(maps,[0, 0], [h-1, w-1], h, w)
if dist == -1:
    print(-1)
else:
    print(h*w - dist - kabe)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

tmp = 0
for i in range(H):
	tmp += S[i].count("#")

w_count = (H*W) - tmp

def bfs(field, dp, q):
	cp = q.pop(0)
	np = [[cp[0]+1,cp[1]], [cp[0]-1,cp[1]], [cp[0],cp[1]+1], [cp[0],cp[1]-1]]

	for n in np:
		if 0 <= n[0] <= H-1 and 0 <= n[1] <= W-1:
			if field[n[0]][n[1]] == "." and dp[n[0]][n[1]] == inf:
				q.append(n)
				dp[n[0]][n[1]] = dp[cp[0]][cp[1]] + 1
			if n == [H-1,W-1]:
				return dp[n[0]][n[1]]

	if len(q) == 0:
		return -1

	return bfs(field, dp, q)

inf = float("inf")
dp = [[inf for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
nes = bfs(S, dp, [[0,0]])
if nes == -1:
	print(-1)
else:
	print(w_count-nes-1)

Submission status: Accepted

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 1
 
queue = [(0, 0)]
counter = 0

while not queue == []:

    if counter >= 10000:
        print(-1)
        exit()

    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
if num_step[R-1][C-1] != INF:
    ans = R*C - black - num_step[R-1][C-1]
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:

adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [ int(v) for v in input().split() ]
total_block = 0
field = [ list(input()) for i in range(h) ]
for i in field:
    total_block += i.count("#")

start = (0,0)
def bfs(p,t):
    field[p[0]][p[1]] = t
    search_list = [p]
    while search_list != []:
        t += 1
        new_search_list = []
        for i in search_list:
            for j in adjust_list:
                if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                    if field[i[0]+j[0]][i[1]+j[1]] == ".":
                        field[i[0]+j[0]][i[1]+j[1]] = t
                        new_search_list.append((i[0]+j[0],i[1]+j[1]))
        search_list = new_search_list
    return

bfs(start,1)


if field[-1][-1] == ".":
    print(-1)
else:
    print(h*w - total_block - field[-1][-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid=[list(input()) for _ in range(h)]
dist=[[-1]*w for _ in range(h)]
dist[0][0]=0
Q=[(0,0)]
tile=h*w
cnt=0

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

while Q:
    Q_alt=[]
    for q in Q:
        if grid[q[1]][q[0]]!="#":
            if q[0]!=0:
                if grid[q[1]][q[0]-1]!="#" and dist[q[1]][q[0]-1]==-1:
                    dist[q[1]][q[0]-1]=cnt+1
                    Q_alt.append((q[0]-1,q[1]))
            if q[0]!=w-1:
                if grid[q[1]][q[0]+1]!="#" and dist[q[1]][q[0]+1]==-1:
                    dist[q[1]][q[0]+1]=cnt+1
                    Q_alt.append((q[0]+1,q[1]))
            if q[1]!=0:
                if grid[q[1]-1][q[0]]!="#" and dist[q[1]-1][q[0]]==-1:
                    dist[q[1]-1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]-1))
            if q[1]!=h-1:
                if grid[q[1]+1][q[0]]!="#" and dist[q[1]+1][q[0]]==-1:
                    dist[q[1]+1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]+1))
    cnt+=1
    Q=Q_alt

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

Submission status: Accepted

Solution code:

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

s = []

for i in range(H):

    S = list(input())
    s.append(S)

Q = [[0,0]]
shnum = 0

#print (s)

for i in range(H):

    for j in range(W):

        if s[i][j] == "#":

            shnum += 1


while len(Q) > 0:

    #print (Q)
    #print (s)

    now = Q.pop(0)

    if now[0] == 0 and now[1] == 0:
        s[0][0] = 1
        Q.append([0,1])
        Q.append([1,0])

    elif s[now[0]][now[1]] == "#":
        continue;

    else:

        if s[now[0]][now[1]] == ".":

            far = 10000

        else:

            far = s[now[0]][now[1]]

        flag = 0

        if now[0]-1 >= 0 and s[now[0]-1][now[1]] not in [-1,"#","."]:

            if far > s[now[0]-1][now[1]]+1:
                far = s[now[0]-1][now[1]]+1
                flag = 1

        if now[1]-1 >= 0 and s[now[0]][now[1]-1] not in [-1,"#","."]:

            if far > s[now[0]][now[1]-1]+1:
                far = s[now[0]][now[1]-1]+1
                flag = 2

        if now[0]+1 < H and s[now[0]+1][now[1]] not in [-1,"#","."]:

            if far > s[now[0]+1][now[1]]+1:
                far = s[now[0]+1][now[1]]+1
                flag = 3

        if now[1]+1 < W and s[now[0]][now[1]+1] not in [-1,"#","."]:

            if far > s[now[0]][now[1]+1]+1:
                far = s[now[0]][now[1]+1]+1
                flag = 4

        if flag != 0:
            
            s[now[0]][now[1]] = far

            if now[0]-1 >= 0 and flag != 1:

                Q.append([now[0]-1,now[1]])

            if now[1]-1 >= 0 and flag != 2:

                Q.append([now[0],now[1]-1])

            if now[0]+1 < H and flag != 3:

                Q.append([now[0]+1,now[1]])

            if now[1]+1 < W and flag != 4:

                Q.append([now[0],now[1]+1])


if s[-1][-1] == -1:
    print (-1)

else:

    if s[-1][-1] == ".":
        print (-1)
    else:
        print (H*W - s[-1][-1] - shnum)

Submission status: Accepted

Solution code:
H,W=map(int,input().split());S=[input() for _ in range(H)];G=[[-1]*W for _ in range(H)];G[0][0]=1;q=[(0,0)]
while q:
 i,j=q[0];q=q[1:]
 for x,y in[(1,0),(0,1),(-1,0),(0,-1)]:
  t,u=i+x,j+y
  if 0<=t<H and 0<=u<W and G[t][u]<0 and S[t][u]==".":
   G[t][u]=1+G[i][j];q+=[(t,u)]
print(-1*(G[-1][-1]<0)or sum(s.count(".")for s in S)-G[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque

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

S = []
white = 0
for _ in range(H):
    s = input()
    white += s.count(".")
    S.append(list(s))

S[0][0] = ""
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

S[0][0] = ""
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque

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

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] == ".":
            S[nh][nw] = "" # visited
            Q.append((nh, nw, count + 1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque

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

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

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

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
cnt[0][0] = 0

def bfs():
    q = deque([(0, 0)])
    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] != '#' and cnt[y+dy][x+dx] == float('inf'):
                q.append([y+dy, x+dx])
                cnt[y+dy][x+dx] = cnt[y][x] + 1
    
bfs()
if cnt[h-1][w-1] != float('inf'):
    short_path = cnt[h-1][w-1]
    ans = 0
    ans += short_path + 1
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                ans += 1

    ans = h*w - ans 
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, a = IR(2)
    n %= 500
    if a >= n:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    _ = II()
    a = LI()
    a.sort(reverse=True)
    op = 0
    ans = 0
    for ai in a:
        ans += -ai * op or ai
        op ^= 1
    print(ans)
    return

#C
def C():
    c = LIR(3)
    for x in range(c[0][0] + 1):
        b = (c[0][0] - x, c[0][1] - x, c[0][2] - x)
        if (c[1][0] - b[0]) == (c[1][1] - b[1]) == (c[1][2] - b[2]):
            if (c[2][0] - b[0]) == (c[2][1] - b[1]) == (c[2][2] - b[2]):
                print("Yes")
                return
    print("No")
    return
#D
def D():
    move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    h, w = LI()
    s = SR(h)
    q = deque([(0, 0, 1)])
    ans = h * w
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                ans -= 1
    check = [[True] * w for _ in range(h)]
    while q:
        x, y, tern = q.pop()
        for mx, my in move:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if s[my][mx] == "." and check[my][mx]:
                    check[my][mx] = False
                    if my == h - 1 and mx == w - 1:
                        print(ans - tern - 1)
                        return
                    q.appendleft((mx, my, tern + 1))
    print(-1)


    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()