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:
import collections
import time
def bfs(G,l):
    l.append([1,1])
    visited = [[0] * len(G[0]) for i in range(len(G))]
    chk = 0
    G[1][1] = 0
    while(len(l)):
        [n0,n1] = l.popleft()
        if visited[n0][n1] == 1:
            continue
        else:
            visited[n0][n1] = 1
        if [n0,n1] == [len(G)-2,len(G[0])-2]:
            chk = 1
            break
        if G[n0][n1+1] != "#" and visited[n0][n1+1] == 0:
            l.append([n0,n1+1])
            G[n0][n1+1] = min(G[n0][n1] + 1,G[n0][n1+1])

        if G[n0][n1-1] != "#" and visited[n0][n1-1] == 0:
            l.append([n0,n1-1])
            G[n0][n1-1] = min(G[n0][n1] + 1,G[n0][n1-1])

        if G[n0+1][n1] != "#" and visited[n0+1][n1] == 0:
            l.append([n0+1,n1])
            G[n0+1][n1] = min(G[n0][n1]+1,G[n0+1][n1])

        if G[n0-1][n1] != "#" and visited[n0-1][n1] == 0:
            l.append([n0-1,n1])
            G[n0-1][n1] = min(G[n0][n1]+1,G[n0-1][n1])
        #print(n0,n1)
    return chk

[h,w] = [int(i) for i in input().split()]
st = time.time()
s = [["#"] * (w+2)]
whites = 0
for i in range(h):
    ls = ["#"]
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            ls.append(200)
        else:
            ls.append(tmp[j])
    ls.append("#")
    whites += tmp.count(".")
    s.append(ls)
s.append(["#"] * (w+2))
l = collections.deque()
#print(time.time() - st)
if bfs(s,l):
    print(whites - s[h][w]-1)

else:
    print(-1)
#print(time.time() - st)

Submission status: Accepted

Solution code:
import queue

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

visited = set()
q = queue.Queue()

# y, x, depth (start = 1)
q.put((0, 0, 1))
visited.add((0, 0))

while not q.empty():
    y, x, depth = q.get()
    if y == h - 1 and x == w - 1:
        print(total - num_b - depth)
        exit()
    if x < w - 1:
        if (y, x+1) not in visited and s[y][x+1] == '.':
            visited.add((y, x+1))
            q.put((y, x+1, depth+1))
    if x > 0:
        if (y, x-1) not in visited and s[y][x-1] == '.':
            visited.add((y, x-1))
            q.put((y, x-1, depth+1))
    if y < h - 1:
        if (y+1, x) not in visited and s[y+1][x] == '.':
            visited.add((y+1, x))
            q.put((y+1, x, depth+1))
    if y > 0:
        if (y-1, x) not in visited and s[y-1][x] == '.':
            visited.add((y-1, x))
            q.put((y-1, x, depth+1))

print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque

def main():
    h, w = map(int, input().split())
    maze = [[] for _ in range(h+2)]
    maze[0] = ['#' for _ in range(w+2)]
    maze[h+1] = ['#' for _ in range(w+2)]
    score = h * w
    for i in range(1, h+1):
        maze[i] = list('#' + input() + '#')
        for j in range(1, w+1):
            if maze[i][j] == '#':
                score -= 1

    direct = [(-1,0), (0,-1), (1,0), (0,1)]
    que1 = deque([(1, 1)])
    que2 = deque([])
    score -= 1
    maze[1][1] = '#'
    while que1:
        x, y = que1.popleft()
        if (x, y) == (h, w):
            print(score)
            break
        for d in direct:
            dx, dy = d
            if maze[x+dx][y+dy] == '.':
                maze[x+dx][y+dy] = '#'
                que2.append((x+dx, y+dy))
        if len(que1) == 0:
            score -= 1
            que1.extend(que2)
            que2.clear()
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sx, sy, gx, gy):
  dist = [[0]*w for i in range(h)] #全頂点を未訪問
  que = deque([(sy,sx)])   #初期条件
  dist[sy][sx] = 1 #start訪問済み
  directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  while que:
    y,x = que.popleft()
    for dirs in directions:
      ny = y + dirs[0] 
      nx = x + dirs[1]
      if not(0<=ny<h and 0<=nx<w):
        continue
      if G[ny][nx] == "#":
        continue
      if dist[ny][nx] == 0:
        dist[ny][nx] = dist[y][x] + 1
        que.append((ny, nx))
      if nx == w-1 and ny == h-1:
        return dist[gy][gx]   
  return -1

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

cnt = 0
for i in range(h):
    cnt += G[i].count('#')
    
ans = bfs(0,0,w-1,h-1)
if ans == -1:
  print(-1)
else:
  score = h * w - cnt - ans
  print(score)

Submission status: Accepted

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

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

black = 0

for i in grid :
    black += i.count('#')
                     
queue = deque([[0,0]])

while queue:
    x,y = queue.popleft()
    if x == h -1  and y == w - 1:
        break
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
        nx,ny = x+i,y+j
        if nx < 0 or ny <0 or nx >= h or ny >= w:
            continue
        if grid[nx][ny] == '.' and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx,ny])
            
ans = h*w - visited[h-1][w-1] - black if visited[h-1][w-1] != -1 else -1


print(ans)

Submission status: Accepted

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

s = list([list(input()) for i in range(H)])
dist = list([[-1 for j in range(W)] for i in range(H)])

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

while q.empty() != True:
  x, y = map(int, q.get())
  for i in range(-1,2):
    for j in range(-1,2):
      if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and s[nx][ny] == '.' and dist[nx][ny] == -1:
          dist[nx][ny] = dist[x][y] + 1
          s[nx][ny] = str(dist[x][y] + 1)
          q.put([nx,ny])

dCount = set()
wallCount = 0
notShortest = 0
goal = dist[H-1][W-1]
for i in s:
  for j in range(len(i)):
    if i[j] =='#':
      wallCount += 1
    elif i[j] == '.':
      pass
    elif goal < int(i[j]):
      pass
    else:
      dCount.add(i[j])

if dist[H-1][W-1] != -1:
  print( H*W - wallCount - goal - 1)
else:
  print(-1)
# for i in s:
  # print("".join(i))

Submission status: Accepted

Solution code:
from collections import deque, namedtuple

P = namedtuple('p', 'y x')
# moves are up, right, down or left
moves = [P(-1, 0), P(0, 1), P(1, 0), P(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
s = P(0, 0)
g = P(h - 1, w - 1)
S[s.y][s.x] = 0
d = deque()
d.append(s)
reach_goal = False
while len(d) != 0:
    cur = d.popleft()
    if cur == g:
        reach_goal = True
        break
    for move in moves:
        nxt = P(cur.y + move.y, cur.x + move.x)
        can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and S[nxt.y][nxt.x] == '.'
        if can_move:
            S[nxt.y][nxt.x] = S[cur.y][cur.x] + 1
            d.append(nxt)
if reach_goal:
    sharp_cnt = 0
    for S_ in S:
        for S__ in S_:
            if S__ == '#':
                sharp_cnt += 1
    ans = h * w - (sharp_cnt + S[g.y][g.x] + 1)
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
'''


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False


## input
h,w = map(int, input().split())

M = [list(input().rstrip()) for _ in range(h)]

## ステータス管理2次元配列
# 訪問状態をWHITE, GRAY, BLACKのいずれかで表す
M_color = [['WHITE']*w for _ in range(h)]

## 距離
# 初期値は-1（到達不能）を入れ、到達できたら実際の距離を代入する
M_distance = [[-1]*w for _ in range(h)]

route_str = '.'
# start, goal設定
sy=0
sx=0
gy=h-1
gx=w-1

def breadth_first_search():
    """

    """
    # 開始頂点sのステータスを探索中へ変更、距離は0を代入
    M_color[sy][sx] = 'GRAY'
    M_distance[sy][sx] = 0
    # キューを初期化し、開始頂点をキューへ代入
    q = deque()
    q.append([sy,sx])

    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]

    # qが空になるまでwhileループ処理
    while len(q) > 0:
        # 探索する頂点を取り出し
        y, x = q.popleft()

        # ゴールに辿り着いたら距離をreturn
        if x == gx and y == gy:
            return M_distance[y][x]

        ## uに隣接する全ての頂点について、未探索の場合は探索
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # r,cの範囲に収まっていなければスキップ
            if after_x < 0 or after_x > w-1 or after_y < 0 or after_y > h-1:
                continue
            
            # 移動先が陸かつ未探索なら
            if M[after_y][after_x] == route_str and M_color[after_y][after_x] == 'WHITE':
                M_color[after_y][after_x] = 'GRAY'
                # 距離は、現在キューにある頂点u + 1となる（隣接しているので）
                M_distance[after_y][after_x] = M_distance[y][x] + 1
                # キューに追加
                q.append([after_y,after_x]) # キューに追加
                            
            M_color[y][x] = 'BLACK'
    
    # goalへたどり着けない場合
    return -1


def main():
    '''メイン処理'''
    g_distance = breadth_first_search()
    # 塗りつぶせる'.'の数 = 全ての'.'の数 - ゴールまでの距離 - 1(スタート地点の.)
    if is_debug:
        print(g_distance)
    
    if g_distance == -1:
        print(-1)
    else:
        # 2次元配列Mの中の、.の数をカウント
        all_dot = len([s for s in list(itertools.chain.from_iterable(M)) if '.' in s])
        ans = all_dot - g_distance -1
        print(ans)
    
    
if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
maze = [[] for i in range(H)]
con = 0
inf = 10 ** 6
distance = [[inf] * W for i in range(H)]

for i in range(H):
  m = list(input())
  maze[i] = m
  con += m.count("#")

def bfs(maze, distance, sh, sw):
  queue = deque([[sh, sw]])
  distance[sh][sw] = 0
  while queue:
    h,w = queue.popleft()
    if h == H - 1 and w == W - 1:
      return distance[H - 1][W - 1]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_h, new_w = h + j, w + k
      if new_h < 0 or new_h >= H or \
        new_w < 0 or new_w >= W:
          continue
      elif maze[new_h][new_w] != "#" and \
        distance[new_h][new_w] > distance[h][w] + 1:
        distance[new_h][new_w] = distance[h][w] + 1

        queue.append([new_h, new_w])
  
minpath = bfs(maze,distance,0,0)

if minpath == None:
  print(-1)
else:
  print(H * W - minpath - con - 1)

Submission status: Accepted

Solution code:
from collections import deque

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


def move(h, w):
    if (0 <= h and h <= H - 1) and (0 <= w and w <= W - 1):
        if s[h][w] == '.':
            return True

    return False


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

dist = l = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
q = deque()
q.append(start)

flag = False

while q:
    now = q.popleft()
    h, w = now

    next_h, next_w = h, w - 1
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h, w + 1
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h - 1, w
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h + 1, w
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

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

ans = white - 2 - (dist[H - 1][W - 1] - 1)

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

# print(dist)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int,input().split())
field = [list(input()) for i in range(h)]
seen = [[False]*w for i in range(h)]
dis = [[0]*w for i in range(h)]

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

que = deque([[sx, sy]])

while len(que) != 0:
    x, y = que.popleft()
    for i, j in ([1,0], [0,1], [-1,0], [0,-1]):
        px, py = x+i, y+j
        
        if px < 0 or px > h-1 or py < 0 or py > w-1:
            continue
        
        if field[px][py] == '#':
            continue
        
        if seen[px][py]:
            continue
        
        else:
            dis[px][py] = dis[x][y] + 1
            seen[px][py] = True
            que.append([px, py])

if dis[gx][gy] == 0:
    print(-1)
    exit()

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

print(c_dot-dis[gx][gy]-1)

Submission status: Accepted

Solution code:

from collections import deque

def bfs(sx, sy, gx, gy):
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = deque([(sx, sy)])
    dist = [[0] * W for _ in range(H)]
    dist[sy][sx] = 1
    while queue:
        x, y = queue.popleft()
        for dirs in directions:
            nx = x + dirs[0]
            ny = y + dirs[1]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if maze[ny][nx] == '#':
                continue

            if dist[ny][nx] == 0:
                dist[ny][nx] = dist[y][x] + 1
                queue.append((nx, ny))
            if nx == gx and ny == gy:
                return dist[gy][gx]
    return -1

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt = 0
for i in range(H):
    cnt += maze[i].count('#')
ans = bfs(0, 0, W-1, H-1)
if ans == -1:
    print(ans)
else:
    score = H * W - cnt - ans
    print(score)

Submission status: Accepted

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

def bfs():
    visited = [[-1]*w for _ in range(h)]
    queue = deque([[sx, sy]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [h-1,w-1]:
            return visited[y][x]
        
        for dy, dx in ([0,1], [1,0], [0, -1], [-1, 0]):
            ny, nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
                    
black_num = 0
for i in maze:
    black_num += i.count("#")
bfs = bfs()
if bfs is None:
    print(-1)
else:
    print(h*w - bfs -1 -black_num)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dist = [[-1 for i in range(w)] for j in range(h)]
dist[0][0] = 0
queue = deque([[0, 0]])
while len(queue) != 0:
    now = queue.popleft()
    if now[1] != w-1:
        if dist[now[0]][now[1]+1] == -1 and s[now[0]][now[1]+1] == ".":
            dist[now[0]][now[1]+1] = dist[now[0]][now[1]] + 1
            queue.append([now[0],now[1] + 1])
    if now[0] != h-1:
        if dist[now[0] + 1][now[1]] == -1 and s[now[0]+1][now[1]] == ".":
            dist[now[0]+1][now[1]] = dist[now[0]][now[1]] + 1
            queue.append([now[0] + 1,now[1]])
    if now[1] != 0:
        if dist[now[0]][now[1]-1] == -1 and s[now[0]][now[1]-1] == ".":
            dist[now[0]][now[1]-1] = dist[now[0]][now[1]] + 1
            queue.append([now[0],now[1] - 1])
    if now[0] != 0:
        if dist[now[0]-1][now[1]] == -1 and s[now[0]-1][now[1]] == ".":
            dist[now[0]-1][now[1]] = dist[now[0]][now[1]] + 1
            queue.append([now[0] -1 ,now[1]])


if dist[h-1][w-1] == -1:
    print(-1)
else:
    length = dist[h-1][w-1] + 1
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans += 1
    ans -= length
    print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
H_list = [list(input()) for i in range(H)]
import numpy as np

H_list = np.array(H_list)

w_cnt = 0
b_cnt = 0
for i in H_list:
    for j in i:
        if j == '.':
            w_cnt += 1
        if j == '#':
            b_cnt += 1
    
dis_mat = np.zeros((H, W))
dis_mat[0, 0] = 1
queue = []
queue.append([0,0])

while queue != []:
    v = queue.pop(0)

    v_new = [[v[0], v[1]+1],
             [v[0], v[1]-1],
             [v[0]+1, v[1]],
             [v[0]-1, v[1]]]

    for i in v_new:
        if 0 <= i[0] < H and 0 <= i[1] < W:
            if dis_mat[i[0], i[1]] == 0 and H_list[i[0], i[1]] == '.':
                dis_mat[i[0], i[1]] = dis_mat[v[0], v[1]] + 1
                queue.append(i)
        
dis = dis_mat[H-1][W-1]
if dis == 0:
    print(-1)
else:
    print(int(w_cnt - dis))

Submission status: Accepted

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

H, W = map(int, input().split())
field = ["#"*(W+2) for _ in range(H+2)] #indexed from 1
for i in range(1, H+1):
    field[i] = "#" + input() + "#"
    
idxs = []
dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
for row in range(1, H+1):
    for col in range(1, W+1):
        if field[row][col] == ".":
            idxs.append((row, col))
graph = {idx: deque() for idx in idxs}
for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx, dy in dxdy:
        if field[x+dx][y+dy] == ".":
            graph[idx].append((x+dx, y+dy))

dist = [[-1] * (W+1) for _ in range(H+1)] #indexed from 1
seen = [[0] * (W+1) for _ in range(H+1)] #indexed from 1
queue = deque()
def bfs(u,v):
    seen[u][v] = 1
    dist[u][v] = 0
    queue.append((u,v))
    while queue:
        p, q = queue[0]
        if not graph[(p,q)]:
            queue.popleft()
            continue
        g,h = graph[(p,q)].popleft()
        if seen[g][h]:
            continue
        seen[g][h] = 1
        dist[g][h] = dist[p][q] + 1
        queue.append((g,h))

bfs(1, 1)
total_pattern = 0
goal = dist[H][W]
if goal == -1:
    print(-1)
else:
    empty_count = 0
    for row in range(1, H+1):
        empty_count += field[row].count(".")
    total_pattern = empty_count - goal - 1
    print(total_pattern)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque

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


def S():
    return input().rstrip()


def I():
    return int(input())


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


inf = float("inf")
mod = 10 ** 9 + 7

h, w = MI()

white = 0
s = [["#"] * (w + 2)]
for i in range(h):
    line = S()
    white += line.count(".")
    s.append(["#"] + list(line) + ["#"])
s.append(["#"] * (w + 2))
s[1][1] = "#"


dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

step = 1
q = [(1, 1)]
while q:
    qq = []
    for x, y in q:
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == "#":
                continue
            if nx == h and ny == w:
                print(white - (step + 1))
                exit()
            qq.append((nx, ny))
            s[nx][ny] = "#"
    q = qq
    step += 1

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
sy, sx, gy, gx = 0, 0, H-1, W-1

q = deque([[sy, sx]])
visited = [[-1]*W for _ in range(H)]
visited[sy][sx] = 0

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

flag = False
while q:
  y, x = q.popleft()
  if [y, x] == [gy, gx]:
    flag = True
    break
  for dy, dx in d:
    ny, nx = y+dy, x+dx
    if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
      continue
    if maze[ny][nx] == "." and visited[ny][nx] == -1:
      visited[ny][nx] = visited[y][x] + 1
      q.append([ny, nx])

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

if flag:
  print(H*W - black - visited[gy][gx] - 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
total_block = h * w
h += 2
w += 2
area = []
explored = []

wall_num = 0

for i in range(h):
    if i == 0 or i == h-1:
        a = '#' * w
    else:
        a = input()
        for j in a:
            if j == '#':
                wall_num += 1
        a = '#' + a + '#'
    area.append(a)

distance = [[float('inf') for _ in range(w)] for _ in range(h)]
distance[1][1] = 0

q = deque()
if area[1][2] == '.':
    q.append([1, 2])
    distance[1][2] = 1
    explored.append([1, 2])
if area[2][1] == '.':
    q.append([2, 1])
    distance[2][1] = 1
    explored.append([2, 1])

explored.append([1, 1])

while len(q) != 0:
    now = q.popleft()
    a = now[0]
    b = now[1]
    d = distance[a][b]
    l = [[a+1, b], [a-1, b], [a, b+1], [a, b-1]]
    for x, y in l:
        if area[x][y] == '.' and [x, y] not in explored:
            q.append([x, y])
            distance[x][y] = d + 1
            explored.append([x, y])

if distance[h-2][w-2] == float('inf'):
    print(-1)
else:
    print(total_block - wall_num - distance[h-2][w-2] - 1)

Submission status: Accepted

Solution code:
from collections import deque

def n_bfs(S,W,H):
    dx=(-1,0,1,0)
    dy=(0,1,0,-1)
    queue=deque([[0,0]])
    d=[[0]*W for _ in range(H)]
    d[0][0]=1
    while queue:
        x,y=queue.popleft()
        for n in range(4):
            nx,ny=x+dx[n],y+dy[n]
            if 0<=nx<=W-1 and 0<=ny<=H-1 and S[ny][nx]=="." and d[ny][nx]==0:
                queue.append([nx,ny])
                d[ny][nx]=d[y][x]+1
    return d[-1][-1]

def n_main():
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    ans=n_bfs(S,W,H)
    num_dot=sum(s.count(".") for s in S)
    
    return num_dot-ans if ans!=0 else -1

if __name__=="__main__":
    print(n_main())

Submission status: Accepted

Solution code:
from collections import deque

def bfs(S,W,H):
    dx=(-1,0,1,0)
    dy=(0,1,0,-1)
    queue=deque([[0,0]])
    visited=[]
    goal=False
    cnt=deque([0])
    while queue and goal==False:
        exe=queue.popleft()
        C=cnt.popleft()
        for i in range(len(dx)):
            x=exe[0]+dx[i]
            y=exe[1]+dy[i]
            if [x,y]==[W-1,H-1]:
                goal=True
            elif 0<=x<=W-1 and 0<=y<=H-1 and S[y][x]==".":
                if [x,y] not in visited:
                    queue.append([x,y])
                    visited.append([x,y])
                    cnt.append(C+1) 
    return goal,C+1

def main():
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    # number of dot
    num_sharp=0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                num_sharp+=1
    goal,num=bfs(S,W,H)
    if goal:
        return W*H-num_sharp-(num+1)
    else:
        return -1

if __name__=="__main__":
    print(main())

Submission status: Accepted

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

_S = [input() for _ in range(H)]
S = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        S[i][j] = _S[i][j]

from collections import deque
queue = deque()

cost = [[-1] * W for _ in range(H)]

def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    queue.append([0, 0])
    cost[0][0] = 0

    while len(queue) > 0:
        x, y = queue.popleft()
        if x == W - 1 and y == H - 1:
            return cost[y][x]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if S[ny][nx] == "#":
                continue
            if cost[ny][nx] != -1:
                continue
            cost[ny][nx] = cost[y][x] + 1
            queue.append([nx, ny])
    return -1

min_cost = bfs()

import numpy as np
num_white = (np.array(S) == ".").sum(axis=1).sum() - 2

print(-1 if min_cost == -1 else num_white - (min_cost - 1))

Submission status: Accepted

Solution code:
import collections
import sys
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
sx,sy,gx,gy = 0,0,h-1,w-1

def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #スタート地点をキューにいれ、頂点を０にする
    que = collections.deque([])
    que.append((sy,sx))
    d[sy][sx] = 0
    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d[-1][-1]
a = bfs(0,0)-1
if a + 1 == INF:
    print(-1)
    sys.exit()
maxgrid = h*w
cnt = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            cnt+=1
ans = maxgrid - cnt - a -2
print(ans)

Submission status: Accepted

Solution code:
import sys
import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

h, w= list(map(int,input().split()))

s=[list(input().strip()) for i in range(h)]

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

total_point=0
for i in range(h):
    for u in range(w):
        if s[i][u]==".":
            total_point+=1

def bfs(y, x):
    q = deque([])
    q.append((y, x, -1))
    while len(q):
        
        y, x, d = q.popleft()
        if visited[y][x]==0:
            dis[y][x] = d+1
            visited[y][x] = 1
            if y==h-1 and x==w-1:
                break
            
            dx = [0, -1 ,0 ,1]
            dy = [-1 ,0 ,1 ,0]
            for i in range(4):
                
                nx = x + dx[i]
                ny = y + dy[i]
                if nx<0 or ny<0 or nx>=w or ny>=h or visited[ny][nx]==1 or s[ny][nx]=="#":
                    continue
                q.append((ny, nx, dis[y][x]))
bfs(0,0)
if visited[h-1][w-1]==0:
    print(-1)
else:
    print(total_point-dis[h-1][w-1]-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = []
count = 0
for _ in range(h):
    x = input()
    count += x.count(".")
    grid.append(x)
from collections import deque
que = deque([])
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 0

delta = [(-1,0),(0,-1),(0,1),(1,0)]
que.append((0,0))
while len(que) > 0:
    vy,vx = que.popleft()
    for dy,dx in delta:
        y = vy + dy
        x = vx + dx
        if not (0<=y<h and 0<=x<w):
            continue
        if dist[y][x] != -1:
            continue
        if grid[y][x] == "#":
            continue
        dist[y][x] = dist[vy][vx] + 1
        que.append((y,x))
ans = dist[h-1][w-1] 
if ans == -1:
    print(-1)
else:
    print(count - ans - 1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
maze = []
for _ in range(H):
    l = list(input())
    maze.append(l)
import collections as col
q = col.deque()
q.append((0,0))
maze[0][0] = 0
def bfs(maze):
    while True:
        if len(q) == 0:
            print("-1")
            quit()
        else: nowx,nowy = q.popleft()
        if nowx == (H - 1) and nowy == (W - 1): return
        for x in [1,-1]: 
            if nowx + x == H or nowy == W or \
             maze[nowx + x][nowy] != '.' : continue
            if 0 <= nowx + x and nowx + x <= H - 1:
                q.append((nowx+x,nowy))
                maze[nowx + x][nowy] = maze[nowx][nowy] + 1
        for y in [1,-1]: 
            if nowx == H or nowy + y== W or \
             maze[nowx][nowy + y] != '.' : continue
            if 0 <= nowy + y and nowy + y <= W - 1:
                q.append((nowx,nowy+y))
                maze[nowx][nowy + y] = maze[nowx][nowy] + 1
bfs(maze)
cnt = 0
for x in maze:
    for y in x:
        if y == '#':
            cnt += 1
print(H*W - maze[H-1][W-1] - cnt - 1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
maze = []
for _ in range(H):
    l = list(input())
    maze.append(l)
import collections as col
q = col.deque()
q.append((0,0))
maze[0][0] = 0
def bfs(maze):
    while True:
        try: nowx,nowy = q.popleft()
        except IndexError:
            print("-1")
            quit()
        if nowx == (H - 1) and nowy == (W - 1): return
        for x in [1,-1]: 
            if nowx + x == H or nowy == W: continue
            if maze[nowx + x][nowy] != '.' : continue
            if 0 <= nowx + x and nowx + x <= H - 1:
                q.append((nowx+x,nowy))
                maze[nowx + x][nowy] = maze[nowx][nowy] + 1
        for y in [1,-1]: 
            if nowx == H or nowy + y== W: continue
            if maze[nowx][nowy + y] != '.' : continue
            if 0 <= nowy + y and nowy + y <= W - 1:
                q.append((nowx,nowy+y))
                maze[nowx][nowy + y] = maze[nowx][nowy] + 1
bfs(maze)
cnt = 0
for x in maze:
    for y in x:
        if y == '#':
            cnt += 1
print(H*W - maze[H-1][W-1] - cnt - 1)