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:
# coding: utf-8
# Your code here!
h,w=map(int,input().split())

maze=[]
m=[]
wn=0
INF = 10**5

for i in range(h):
    row=list(input())
    maze.append(row)
    m.append([INF for i in range(w)])
    for j in range(w):
        if row[j]==".":
            wn+=1


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

queue=[]
queue.append([0,0])
maze[0][0]="#"

while len(queue)>0:

    y,x=queue.pop(0)
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]==".":
                queue.append([ny,nx])
                maze[ny][nx]="#"
                m[ny][nx]=min(m[ny][nx],m[y][x]+1)


if m[-1][-1]==INF:
    print(-1)
else:
    print(wn-2-(m[-1][-1]-1))

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((0, 1), (1, 0), (0, -1), (-1, 0))
path = [[float('inf')]*w for _ in range(h)]
path[0][0] = 0
def bfs():
    q = deque([[0, 0]])
    while q:
        y, x = q.popleft()
        if y == h and x == w:
            return 
        for dy, dx in moves:
            ny = y + dy 
            nx = x + dx 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.' and path[ny][nx] == float('inf'):
                path[ny][nx] = min(path[ny][nx], path[y][x]+1)
                q.append([ny, nx])

bfs()

black = 0

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

if path[h-1][w-1] != float('inf'):
    print(h*w - black - path[h-1][w-1] - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import copy
import queue
import numpy as np

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







#import queue
def bfs(array,start,goal,height,width):
    v=[[-1]*width for _ in range(height)]

    q=queue.Queue()
    q.put([start[0],start[1]])
    move=[[0,1],[0,-1],[1,0],[-1,0]]
    v[start[0]][start[1]]=0
    while not q.empty():
        pos=q.get()
        if pos[0]==goal[0] and pos[1]==goal[1]:          
            break
        
        for m in move:
            y=pos[0]+m[0]
            x=pos[1]+m[1]
            if y>=0 and y<height and x>=0 and x<width and array[y][x]=="." and v[y][x]==-1 :
                v[y][x]=v[pos[0]][pos[1]]+1
                q.put([y,x])
    return v[goal[0]][goal[1]]


cnt=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            cnt+=1

d=bfs(c,[0,0],[H-1,W-1],H,W)
if d==-1:
    print(-1)
else:
    print(H*W-1-d-cnt)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    #class ctmp():
    #    def __init__(self,ij,dis):
    #        self.ij=ij
    #        self.dis=dis
    H,W=map(int,input().split())
    ls=["#"*(W+2)]#
    for i in range(H):
        ls.append("#"+input()+"#")
    ls.append("#"*(W+2))#
    q=deque([])
    #qd=deque([])
    #tmp=ctmp((1,1),0)
    q.append((1,1))
    #qd.append(0)
    #df={}
    lf=[[float("inf") for _ in range(W+2)] for _ in range(H+2)]#
    #これでfとdの両方の役割をこなす
    lf[1][1]=0
    while q:
        tmpij=q.popleft()
        #tmpd=qd.popleft()
        #df[tmpij]=1
        if tmpij==(H,W):
            break
        lind=[(-1,0),(1,0),(0,-1),(0,1)]#
        for i in range(4):
            #ntmpij=(tmpij[0]+(i<2)*(2*i-1),tmpij[1]+(i>1)*(2*i-5))
            ntmpij=(tmpij[0]+lind[i][0],tmpij[1]+lind[i][1])
            #print(ntmpij)
            #if ntmpij not in df and ls[ntmpij[0]][ntmpij[1]]==".":
            if lf[ntmpij[0]][ntmpij[1]]==float("inf") and ls[ntmpij[0]][ntmpij[1]]==".":
                #c_tmp=ctmp(ntmpij,tmp.dis+1)
                #q.append(c_tmp)
                q.append(ntmpij)
                #qd.append(tmpd+1)
                lf[ntmpij[0]][ntmpij[1]]=lf[tmpij[0]][tmpij[1]]+1
                #dは訪れる前に書き込んでしまう
    if tmpij==(H,W):
        nw=0
        for i in range(1,H+1):
            #for j in range(1,W+1):
             #   if ls[i][j]==".":
              #      nw+=1
            nw+=ls[i].count(".")
        #print(nw-tmpd-1)
        print(nw-lf[H][W]-1)
    else:
        print(-1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
c = []
for _ in range(H):
  c.append(list(input()))
Q = dq([])
Q.append((0, 0))
dist = [[float("inf")] * W for _ in range(H)]
d = [-1, 0, 1, 0]
dist[0][0] = 1
while len(Q):
  p = Q.popleft()
  for i in range(4):
    y = p[0] + d[i]
    x = p[1] + d[-1 - i]
    if (0 <= y < H) and (0 <= x < W):
      if c[y][x] == "." and (dist[y][x] > dist[p[0]][p[1]] + 1):
        Q.append((y, x))
        dist[y][x] = dist[p[0]][p[1]] + 1
if dist[H - 1][W - 1] == float("inf"):
  print(-1)
  exit(0)
black = 0
for i in range(H):
  black += c[i].count("#")
print(H * W - dist[H - 1][W - 1] - black)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sx, sy, gx, gy):
    d = [[float('inf')] * W for _ in range(H)]

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]                
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] != '#' and d[ny][nx] == float('inf'):
                d[ny][nx] = d[p[1]][p[0]] + 1
                que.append((nx, ny))
    return d[gy][gx]


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

a = bfs(0, 0, W-1, H-1)
white = 0
for x in grid:
    white += x.count('.')

if a == float('inf'):
    answer = -1
else:
    answer = white - (a + 1)
print(answer)

Submission status: Accepted

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

white = 0

for i in range(H):
    white += s[i].count(".")

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

g = [[10**9]*W for i in range(H)]
g[0][0] = 0
for i in range(H*W):
    if len(q) == 0:
        break
    x, y = q.popleft()
    if (x, y) == (H-1, W-1):
        break
    else:
        if x < H-1 and s[x+1][y] == ".":
            if g[x+1][y] == 10**9:
                q.append((x+1, y))
            g[x+1][y] = min(g[x+1][y], g[x][y]+1)
        if y < W-1 and s[x][y+1] == ".":
            if g[x][y+1] == 10**9:
                q.append((x, y+1))
            g[x][y+1] = min(g[x][y+1], g[x][y]+1)
        if x > 0 and s[x-1][y] == ".":
            if g[x-1][y] == 10**9:
                q.append((x-1, y))
            g[x-1][y] = min(g[x-1][y], g[x][y]+1)
        if y > 0 and s[x][y-1] == ".":
            if g[x][y-1] == 10**9:
                q.append((x, y-1))
            g[x][y-1] = min(g[x][y-1], g[x][y]+1)
if g[H-1][W-1] == 10**9:
    print(-1)
else:
    print(white - (g[H-1][W-1]+1))

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:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    bl = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                bl += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mc = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mc = min(mc, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and s[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(h * w - mc - 1 - bl if mc != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    h, w = map(int, input().split())
    t = [[(c == "#") * 1 for c in input()] for _ in range(h)]
    b0 = sum(sum(tk) for tk in t)
    # print(b0)
    hp = []
    # p2D(t)
    heappush(hp, (1, 0, 0))
    while hp:
        d, i, j = heappop(hp)
        if (i, j) == (h - 1, w - 1):
            print(h * w - d - b0)
            exit()
        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if t[ni][nj]: continue
            t[ni][nj] = 1
            heappush(hp, (d + 1, ni, nj))
    print(-1)

main()

Submission status: Accepted

Solution code:
import numpy as np


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

    ps = np.zeros([H, W])
    for i in range(H):
        ps[i, :] = list(map(lambda x: -1 if x == "#" else 0, input()))
    hashnum = np.sum(ps)

    costs = np.zeros([H, W])
    s = (0, 0)
    g = (H-1, W-1)
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = [s]
    costs[s] = 1
    ps[s] = 1
    moves = 1
    dame = 1

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if ps[nx, ny] == 0:
                        costs[nx, ny] = moves
                        ps[nx, ny] = 1
                        qn.append((nx, ny))

        q = qn
        if g in q:
            dame = 0
            break

    if dame == 0:
        print(int(H * W + hashnum - np.max(costs)))
    else:
        print(-1)


main()

Submission status: Accepted

Solution code:
def BFS(x,y): # 配列dの幅優先探索
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[]
    que.append([x,y])
    d[x][y]=0
    while len(que)!=0:
        [qx,qy]=que[0]
        que.pop(0)
        for i in range(4):
            nx=qx+dx[i]
            ny=qy+dy[i]
            if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                d[nx][ny]=d[qx][qy]+1
                que.append([nx,ny])
    return d[h-1][w-1]

def main():
    global h,w,maze,d
    h,w = map(int,input().split())
    d=[[-1 for _ in range(w)] for _ in range(h)]
    maze=[]
    for _ in range(h):
        maze.append(list(input()))
    n=BFS(0,0)
    if n==-1:
        print(-1)
    else:
        cnt=0
        for i in range(h):
            for j in range(w):
                if maze[i][j]==".":
                    cnt+=1
        print(cnt-n-1)

        
    





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)

H,W = map(int,input().split(' '))
sx,sy = 0,0
move_list = [ list(input()) for _ in range(H) ]
possible_list = [ [-1 for _ in range(W) ] for _ in range(H) ]
possible_list[sx][sy] = 0

x_start_list = [sx]
y_start_list = [sy]

def bfs(target_list,possible_list,x_queue,y_queue,cnt=0):
    x_list = [1,-1,0,0,]
    y_list = [0,0,1,-1]
    cnt += 1
    next_x_queue = []
    next_y_queue = []

    for i in range(4):
        for j in range(len(x_queue)):
            dx = x_queue[j] + x_list[i]
            dy = y_queue[j] + y_list[i]
            if dx < 0 or H <= dx or dy < 0 or W <= dy:
                continue
            if target_list[dx][dy] == '#':
                continue
            if possible_list[dx][dy] != -1:
                continue
            possible_list[dx][dy] = cnt
            next_x_queue.append(dx)
            next_y_queue.append(dy)
    if len(next_x_queue) > 0:
        bfs(target_list,possible_list,next_x_queue,next_y_queue,cnt)
    else:
        return

bfs(move_list,possible_list,x_start_list,y_start_list)

cnt_all_panel = 0
for row in move_list:
    for val in row:
        if val == '.':
            cnt_all_panel += 1
if possible_list[H-1][W-1] == -1:
    print(-1)
else:
    print(cnt_all_panel - possible_list[H-1][W-1] -1)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]


count = 0

# for i in range(H):
#     for j in range(W):
#         if field[i][j] == start:
#             sy, sx = i, j
#         elif field[i][j] == goal:
#             gy, gx = i, j
sy,sx = 0,0
gy,gx = H-1,W-1
seen = [[0 for i in range(W)] for j in range(H)]
queue = [[sy,sx]]
flag = False
while queue != []:
    h,w = queue.pop(0)
    before = seen[h][w]
    for i in range(4):
        nh = h + dy[i]
        nw = w + dx[i]
        if (nh == gy) and (nw == gx):
            count = before+1
            flag = True
        if (0<=nh<H) and (0<=nw<W):
            if field[nh][nw] != '#':
                if seen[nh][nw] == 0:
                    seen[nh][nw] = before+1
                    queue.append([nh,nw])
    if flag:
        break
whites = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            whites += 1
if count != 0 :
    print(whites - count-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import copy

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

#(っ•₃•c)♡(っ•₃•c)♡(っ•₃•c)♡(っ•₃•c)♡(っ•₃•c)♡

visited = []
for _ in range(h):
    visited.append([-1 for __ in range(w)])

visited[0][0] = 0
here = [[0,0]]
count = 0

#(っ०ω०c)(っ०ω०c)(っ०ω०c)(っ०ω०c)(っ०ω०c)(っ०ω०c)

def udlr(line):
    ans = []
    for cell in line:
        if cell[0]-1 >= 0:
            ans.append([cell[0]-1, cell[1]])
        if cell[0]+1 < h:
            ans.append([cell[0]+1, cell[1]])
        if cell[1]-1 >= 0:
            ans.append([cell[0], cell[1]-1])
        if cell[1]+1 < w:
            ans.append([cell[0], cell[1]+1])
    return ans

flag = 0

#ｏ(｡・‧̫・｡)ｏｏ(｡・‧̫・｡)ｏｏ(｡・‧̫・｡)ｏｏ(｡・‧̫・｡)ｏｏ(｡・‧̫・｡)ｏ

while True:
    count += 1
    line = []
    for cell in udlr(here):
        a = cell[0]
        b = cell[1]
        if s[a][b] == "." and visited[a][b] == -1:
            visited[a][b] = count
            line.append([a, b])
            if a == h-1 and b == w-1:
                flag = 1
    here = copy.deepcopy(line)
    if flag:
        break
    if here == []:
        break

#(੭ु ›ω‹ )੭ु⁾⁾♡(੭ु ›ω‹ )੭ु⁾⁾♡(੭ु ›ω‹ )੭ु⁾⁾♡(੭ु ›ω‹ )੭ु⁾⁾♡

if visited[h-1][w-1] == -1:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                cnt += 1
    print(h*w - 1 - visited[h-1][w-1] - cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

p = [[0 for j in range(W)] for i in range(H)]
p[0][0] = 1
visited = [[False for j in range(W)] for i in range(H)]
Q = deque()
Q.append((0, 0))
while len(Q) > 0:
    i, j = Q.popleft()
    neighbors = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
    for ni, nj in neighbors:
        if 0 <= ni < H and 0 <= nj < W and s[ni][nj] != '#' and p[ni][nj] == 0 and not visited[ni][nj]:
            p[ni][nj] = p[i][j] + 1
            Q.append((ni, nj))
    visited[i][j] = True

n_black = sum([row.count('#') for row in s])
print(H * W - n_black - p[H - 1][W - 1] if p[H - 1][W - 1] != 0 else - 1)

Submission status: Accepted

Solution code:
def debug_print(maze):
    for xx in maze:
        print(xx)
#        for yy in xx:
#            print(yy)

def clear_maze(h,w,sx, sy, gx, gy, maze):
#    debug_print(maze)
    INF = 100000000
    distance = [[INF for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        queue.insert(0, (sy, sx))
        distance[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance[gy][gx]
    return bfs()
###########################################

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

H, W = LI()
cur = int(0)
S = [list(str(input().rstrip('\n'))) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            cur +=1
#print (clear_maze(H,W,0,0,W-1,H-1,S))
ans = H*W - (clear_maze(H,W,0,0,W-1,H-1,S) + 1 + cur)
if ans<0:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mt = min(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and s[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    if mt == 10 ** 10:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            cnt += s[i].count("#")
        print(h * w - cnt - (mt + 1))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

d = deque()
d.append([0, 0])
while(d):
    y,x = d.popleft()
    difflist = [[1,0], [0,1], [-1, 0], [0, -1]]
    for dy, dx in difflist:
        y2 = y + dy
        x2 = x + dx
        if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] != '#' and dist[y2][x2] == INF:
            d.append([y2, x2])
            dist[y2][x2] = dist[y][x] + 1

distribution = [0]*(h*w)
ans = 0
for i in range(h):
    for j in range(w):
        if dist[i][j] != INF:
            distribution[dist[i][j]] += 1
        elif maze[i][j] == '.':
            ans += 1

if dist[h-1][w-1] != INF:
    distend = dist[h-1][w-1]
    ans += sum(distribution) - distend -1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

r, c = map(int, input().split())
s_y, s_x = 1, 1
g_y, g_x = r, c
s_y -= 1
s_x -= 1
g_y -= 1
g_x -= 1

maze = [list(input()) for i in range(r)]
dot_num = 0
for i in maze:
    dot_num += i.count('.')
reached = [[0] * c for i in range(r)]

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

queue = deque([[s_y, s_x, 0]])
reached[s_y][s_x] = 1

while queue:
    now = queue.popleft()
    depth = now[2] + 1
    for d in directions:
        next_y = now[0] + d[0]
        next_x = now[1] + d[1]
        if 0 <= next_y < r and 0 <= next_x < c:
            if maze[next_y][next_x] == '.':
                if reached[next_y][next_x] == 0:
                    queue.append([next_y, next_x, depth])
                    reached[next_y][next_x] = 1

                    if next_y == g_y and next_x == g_x:
                        print(dot_num - depth - 1)
                        exit()
print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

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


def bfs(h,w,num):
    if h==H-1 and w==W-1:
        print(ku-num-1)
        exit() 
    else:
        pass

    if h!=0: 
        if S[h-1][w]!="#": 
            temp.append([h-1,w])
            S[h-1][w]="#"

    if w!=0: 
        if S[h][w-1]!="#": 
            temp.append([h,w-1]) 
            S[h][w-1]="#"

    if h!=H-1: 
        if S[h+1][w]!="#": 
            temp.append([h+1,w]) 
            S[h+1][w]="#"

    if w!=W-1: 
        if S[h][w+1]!="#": 
            temp.append([h,w+1]) 
            S[h][w+1]="#"
        
q=[[0,0]] 
count=-1
while True: 
    count+=1
    #print(q)
    temp=[]
    while q:
        l=q.pop(0)
        bfs(l[0],l[1],count)
        
    q=temp[:]
    if len(q)==0:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
F = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == '.':
            cnt += 1


que = [[0, 0, 0]]
flag = True

while len(que) > 0 and flag:
    sp = que.pop(0)
    y, x, c = sp[0], sp[1], sp[2]
    for dy, dx in [[1,0], [-1,0], [0,1], [0,-1]]:
        if 0 <= y+dy < H and 0 <= x+dx < W and F[y+dy][x+dx] == ".":
            F[y+dy][x+dx] = c+1
            que.append([y+dy, x+dx, c+1])
            if y+dy == H-1 and x+dx == W-1:
                flag = False

if flag:
    print(-1)
else:
    print(cnt-F[H-1][W-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

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

A = [[-1 for _ in range(W)] for _ in range(H)]
A[0][0] = 1

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

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

    if S[x][y] == "#":
        continue

    for dx,dy in dxdy:
        if 0 <= x+dx < H  and  0 <= y+dy < W:
            if S[x+dx][y+dy] == "." and A[x+dx][y+dy] == -1:
                A[x+dx][y+dy] = A[x][y] + 1
                queue.append((x+dx,y+dy))

cnt_white = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            cnt_white += 1

if A[H-1][W-1] == -1:
    print(-1)
else:
    print(cnt_white - A[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
l=[["#" for i in range(w+2)]]
for i in range(h):
  l1=list(input())
  l1=["#"]+l1+["#"]
  l.append(l1)
l2=["#" for i in range(w+2)]
l.append(l2)
q=deque([[1,1]])
inf=1000000000
d=[[inf for i in range(w+2)] for j in range(h+2)]
d[1][1]=0
move=[[1,0],[-1,0],[0,1],[0,-1]]
while q:
  a=q.popleft()
  n1=a[0]
  n2=a[1]
  for i in move:
    m1=i[0]
    m2=i[1]
    if l[n1+m1][n2+m2]!="#":
      if d[n1+m1][n2+m2]>d[n1][n2]+1:
        d[n1+m1][n2+m2]=d[n1][n2]+1
        q.append([n1+m1,n2+m2])
dis=d[h][w]
count=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=="#":
      count+=1
if dis==inf:
  print(-1)
else:
  print(h*w-dis-1-count)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [list(input()) for i in range(h)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    dist = [[-1 for j in range(w)] for i in range(h)]
    que = deque()
    px = [[-1 for j in range(w)] for i in range(h)]
    py = [[-1 for j in range(w)] for i in range(h)]
    dist[0][0] = 0
    que.append((0, 0))
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if (ny < 0) or (h <= ny) or (nx < 0) or (w <= nx):
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                py[ny][nx], px[ny][nx] = y, x
                que.append((ny, nx))

    if dist[h-1][w-1] == -1:
        print(dist[h-1][w-1])
    else:
        y, x = h - 1, w - 1
        while y != -1 and x != -1:
            G[y][x] = "o"
            y, x = py[y][x], px[y][x]
        ans = 0
        for i in G:
            for j in i:
                if j == ".":
                    ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
g = [['#'] * (w+2) for i in range(h+2)]
c = 0
for i in range(h):
  g[i+1][1:-1] = list(input())
  c += g[i+1][1:-1].count('#')
d = {}
d[0] = [(1,1)]
vi = set()
vi.add((1,1))
i = 0
while d[i]:
  l = d[i]
  d[i+1] = []
  for cur in l:
    for a,b in [[1,0],[0,1],[-1,0],[0,-1]]:
      to = (cur[0]+a,cur[1]+b)
      if to == (h,w):
        print(h*w-c-i-2)
        exit()
      if g[to[0]][to[1]] == '.' and to not in vi:
        vi.add(to)
        d[i+1].append(to)
  i += 1
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(grid, sy, sx, target, wall):
    grid[sy][sx] = wall
    queue = deque([])
    queue.append([sy, sx, 1])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if [y_, x_] == target:
                return cnt+1
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_,cnt+1])
            grid[y_][x_] = wall
    return 0

H,W = map(int, input().split())
wall = '#'
edges = [wall] * (W+2)
grid = [edges]
b_cnt = 0
for i in range(H):
    s = input()
    grid.append([wall] + list(s) + [wall])
    b_cnt += s.count(wall)
grid.append(edges)
cost = bfs(grid, 1,1, [H,W], wall)
print(H*W - b_cnt - cost if cost else -1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
total_white_square = 0
for i in range(h):
    row = list(input())
    total_white_square += row.count('.')
    maze.append(row)
visited = [[False for i in range(w)] for j in range(h)]
queue = deque()
start = (0, 0)
end = (h - 1, w - 1)
queue.append((start, 1))
visited[0][0] = True
num_white_row = 0
while len(queue) > 0:
    curr, time = queue.popleft()
    if curr == end:
        num_white_row = time
        break
    x, y = curr
    if x - 1 >= 0 and not visited[x - 1][y] and maze[x - 1][y] == '.':
        visited[x - 1][y] = True
        queue.append(((x - 1, y), time + 1))
    if x + 1 <= h - 1 and not visited[x + 1][y] and maze[x + 1][y] == '.':
        visited[x + 1][y] = True
        queue.append(((x + 1, y), time + 1))
    if y - 1 >= 0 and not visited[x][y - 1] and maze[x][y - 1] == '.':
        visited[x][y - 1] = True
        queue.append(((x, y - 1), time + 1))
    if y + 1 <= w - 1 and not visited[x][y + 1] and maze[x][y + 1] == '.':
        visited[x][y + 1] = True
        queue.append(((x, y + 1), time + 1))
if num_white_row != 0:
    print(total_white_square - num_white_row)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(lambda x: int(x), input().split())
s=[[] for _ in range(h)]
black=0
for i in range(h):
    s[i]=input()
    black+=s[i].count('#')

dist=[[-1 for _ in range(w)] for _ in range(h)]
que = deque([(0, 0)])
dist[0][0]=0
while que:
    y, x=que.popleft()
    for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
        if y1<0 or y1>h-1 or x1<0 or x1>w-1:
            continue
        if s[y1][x1]=='#':
            continue
        if dist[y1][x1]!=-1:
            continue
        dist[y1][x1]=dist[y][x]+1
        que.append((y1,x1))

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

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = []
    b_cnt = 0
    for i in range(h):
        st = list(str(input().rstrip('\n')))
        s.append(st)
        b_cnt += st.count("#")

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[0, 0] = 1
    m_cost = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            if x == h - 1 and y == w - 1:
                m_cost = min(m_cost, cost)
            for x, y in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= x < h and 0 <= y < w:
                    if (x, y) not in fq and s[x][y] == ".":
                        ql.append([cost+1, x, y])
                        fq[x, y] += 1
        else:
            break
    if m_cost == 10 ** 10:
        print(-1)
    else:
        print(h * w - b_cnt - m_cost - 1)


if __name__ == '__main__':
    solve()