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:
#%%
H, W = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1
            
#%%
import copy, collections

maze_copy = copy.deepcopy(maze)
color = [["W"] * W for _ in range(H)]


X, Y = 0, 0
vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
color[Y][X] = "G"
que = collections.deque()
maze_copy[Y][X] = 1
que.append([Y, X])

while len(que) != 0:
    u = que.popleft()
    for y, x in vec:
        temp_x = u[1] + x
        temp_y = u[0] + y
        if (0 <= temp_x < W and 0 <= temp_y < H
                and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
            color[temp_y][temp_x] = "G"
            maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
            que.append([temp_y, temp_x])
    
if maze_copy[-1][-1] == ".":
    print(-1)
else:
    print(W * H - num_black - maze_copy[-1][-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc088/tasks/abc088_d


import sys
input = sys.stdin.readline
from collections import deque

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def bfs(grid, visit, start, goal=(None,None)):
    visit[start[0]][start[1]] = 1               # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == wall:         # 壁があったら進まない
                continue
            if visit[q[0]][q[1]] == 1:           # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(start, goal, q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit[q[0]][q[1]] = 1               # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0
for h in range(H):
    grid.append(input().rstrip())                # 文字列を読み込むと改行が入るため、rstrip()で消す
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)

visit = [[0]*W for _ in range(H)]
res = bfs(grid, visit, start, goal)           #  visitを初期化せずに何度も呼び出すと、visit が変わって返り値も変わるので注意
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

Submission status: Accepted

Solution code:
import heapq as hp
import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)])
s = np.pad(s, 1, 'constant')
visited = np.zeros_like(s, dtype=np.bool)

judge = np.inf

q = []
hp.heappush(q, (0, 1, 1))

while q:
    cnt, y, x = hp.heappop(q)
    if y == h and x == w:
        judge = cnt
        break
    for dy, dx in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
        ny, nx = y + dy, x + dx
        if s[ny, nx] == '.' and not visited[ny, nx]:
            visited[ny, nx] = True
            hp.heappush(q, (cnt + 1, ny, nx))

if judge == np.inf:
    print(-1)
else:
    print((s == '.').sum() - judge - 1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

queue = deque([[0, 0]])
visited = [[1] * w for _ in range(h)]
visited[0][0] = 0

def bfs():
    while len(queue) > 0:
        h1, w1 = queue.popleft()
        if h1 == h - 1 and w1 == w - 1:
            return visited[h1][w1]
        for k, l in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_h, n_w = h1 + k, w1 + l
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if visited[n_h][n_w] == 1 and s[n_h][n_w] == '.':
                queue.append([n_h, n_w])
                visited[n_h][n_w] += visited[h1][w1]
    return -1
    
bfs = bfs()
ans = 0
if bfs == -1:
    ans = -1
else:
    ans = cnt - bfs - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
def bfs(G,visited,sy,sx):
    queue=deque([[sy,sx]])
    visited[sy][sx]=0
    while queue:
        y,x=queue.popleft()
        if (y,x)== (H-1,W-1):
            return visited[y][x]
        for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
            tmp_y,tmp_x = y+j,x+k
            if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and  G[tmp_y][tmp_x]!='#':
                if visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
    return -1
if __name__  =="__main__":
    H,W =map(int,input().split())
    G=[list(input()) for _ in range(H)]
    sy,sx =0,0
    dist=0
    visited=[[-1]*W for _ in range(H)]
    dist=bfs(G,visited,sy,sx)
    if dist==-1:
        print(-1)
    else:
        print(list(itertools.chain.from_iterable(G)).count('.')-dist-1)

Submission status: Accepted

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None), visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "#":         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
res = search(start,goal)
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

Submission status: Accepted

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
visit = set()                                 # 訪れたかどうかをメモ ([]をつけないとtupleが展開されて各要素をsetに入れる操作になってしまう)
next_set = deque()                            # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None)):      #
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "#":         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
res = search(start,goal)
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    maze = [[f_inf] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        h, w = que.popleft()
        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W or grid[next_h][next_w] == "#":
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])

    if maze[H - 1][W - 1] == f_inf:
        print(-1)
        exit()

    mi = maze[H - 1][W - 1] + 1

    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                cnt += 1
    res = H * W - cnt - mi
    print(res)


if __name__ == '__main__':
    resolve()

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), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*(W) for _ in range(H)]
    dist[sy][sx] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '.' and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1
                q += [[ny, nx]]

    return dist

d = bfs(0, 0)

if d[-1][-1] == float('inf'):
    print(-1)
    exit()

ans = H*W 
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            ans -= 1

ans -= d[-1][-1] + 1
print(ans)

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  white = 0
  black = 0
  for i in range(H):
    for j in range(W):
      if M[i][j] == '.':
        white += 1
      elif M[i][j] == '#':
        black += 1

  start = (0, 0)
  q = deque()
  q.append(start)
  is_visited = [[0]*W for _ in range(H)]
  d = [[float('inf')]*W for _ in range(H)]
  d[0][0] = 0

  while len(q):

    ur, uc = q.popleft()

    for vr, vc in [(ur, uc+1), (ur, uc-1), (ur-1, uc), (ur+1, uc)]:
      if 0 <= vr < H and \
         0 <= vc < W and \
         not(is_visited[vr][vc]) and not(M[vr][vc] == '#'):

        q.append((vr, vc))
        is_visited[vr][vc] = True
        d[vr][vc] = d[ur][uc] + 1

  if d[H-1][W-1] == float('inf'):
    print(-1)
  else:
    print(white - (d[H-1][W-1] + 1))


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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in  range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            cnt += 1
dist = [[-1]*W for _ in range(H)]
dist[0][0] = 0
que = deque([[0,0]])
while que:
    h,w = que.pop()
    for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
        nh,nw = h+dh,w+dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w]+1
            que.appendleft([nh,nw])
if dist[H-1][W-1] == -1:
    print(-1)
    exit()
print(H*W-cnt-dist[H-1][W-1]-1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = 10, 37
ARR = [
    ".....................................",
    "...#...####...####..###...###...###..",
    "..#.#..#...#.##....#...#.#...#.#...#.",
    "..#.#..#...#.#.....#...#.#...#.#...#.",
    ".#...#.#..##.#.....#...#.#.###.#.###.",
    ".#####.####..#.....#...#..##....##...",
    ".#...#.#...#.#.....#...#.#...#.#...#.",
    ".#...#.#...#.##....#...#.#...#.#...#.",
    ".#...#.####...####..###...###...###..",
    ".....................................",
]

H, W = map(int, input().split())
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, arr):
    q = deque()

    q.append((0, 0))

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

    distance = [[0 for i in range(w)] for j in range(h)]
    distance[0][0] = 1
    while q.__len__() > 0:
        y, x = q.popleft()
        for i in range(4):
            my = y + dy[i]
            mx = x + dx[i]
            if (my >= 0) and (mx >= 0) and (my <= (h - 1)) and (mx <= (w - 1)) and (distance[my][mx] == 0) and (
                    arr[my][mx] == "."):
                distance[my][mx] = distance[y][x] + 1
                q.append((my, mx))

    mmk = 0
    for j in range(h):
        mmk += arr[j].count("#")

    if distance[h - 1][w - 1] == 0:
        print(-1)
    else:
        print(h * w - distance[h - 1][w - 1] - mmk)


calculate(H, W, ARR)

Submission status: Accepted

Solution code:
from collections import deque
import collections
import math

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

def bfs():
    res=0
    for y in range(h):
        for x in range(w):
            if c[y][x]=='.':
                c[y][x]=math.inf
                res += 1
    c[0][0]=0
    que=deque([[0,0]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if h > ny >= 0 and w > nx >= 0:
                dist=c[ny][nx]
                if dist!='#':
                    if dist>c[y][x]+1:
                        c[ny][nx]=c[y][x]+1
                        que.append([ny,nx])
            else:
                pass
    if c[h-1][w-1] ==math.inf:
        return (-1)
    else:
        return res - c[h-1][w-1] -1

print (bfs())

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


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

white_cnt = 0
grid = [[] for i in range(H+2)]
check = [[0] * (W+2) for i in range(H+2)]
grid[0] = ['#']*(W+2)
for i in range(1, H+1):
    w = list(input())
    white_cnt += w.count('.')
    grid[i] = ['#'] + w + ['#']
grid[-1] = ['#']*(W+2)

mv_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que_hwc = deque([(1, 1, 1)])
check[1][1] = 1
while que_hwc:
    hwc = que_hwc.popleft()
    h = hwc[0]
    w = hwc[1]
    cnt = hwc[2]
    if h == H and w == W:
        print(white_cnt-cnt)
        exit(0)

    for mv in mv_list:
        mv_h = h + mv[0]
        mv_w = w + mv[1]
        if grid[mv_h][mv_w] == '.' and check[mv_h][mv_w] != 1:
            check[mv_h][mv_w] = 1
            que_hwc.append((mv_h, mv_w, cnt+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

s = [[] for _ in range(h)]
dis = [[-1] * w for _ in range(h)]

for i in range(h):
    s[i] = input()

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

q = deque()
q.append([0, 0, 1])  # x,y,d
dis[0][0] = 1

while len(q) > 0:
    x, y, d = q.popleft()
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "#":
            continue
        q.append([nx, ny, d + 1])
        dis[ny][nx] = d + 1

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
field = [list(input()) for i in range(H)]
sx, sy, gx, gy = 0, 0, H-1, W-1
x = [1, 0, -1, 0]
y = [0, 1, 0, -1]
def bfs():
    d = [[float("inf")] * W for _ in range(H)]
    d[sx][sy] = 0
    Q = deque([])
    Q.append((sx, sy))
    while Q:
        px, py = Q.popleft()
        if px==gx and py==gy:
            break
        for dx, dy in zip(x, y):
            nx = px+dx
            ny = py+dy
            if 0<=nx<H and 0<=ny<W and field[nx][ny]=='.' and d[nx][ny]==float('inf'):
                d[nx][ny]=d[px][py]+1
                Q.append((nx, ny))
    return d[gx][gy]

count = 0
for i in field:
    count += i.count('.')
res = bfs()
if 0 < res < float("inf"):
    print(count-res-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
l = [str(input()) for _ in range(H)]
white_count = 0
for s in l:
  white_count += s.count('.')
sy = 0
sx = 0
gy = H-1
gx = W-1
visited = [[-1]*W for _ in range(H)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()
  if [y,x] == [gy,gx]:
    print(white_count - visited[y][x] - 1)
    exit()
  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    if 0 <= x+j < W and 0 <= y+i < H and visited[y+i][x+j] == -1 and l[y+i][x+j] == '.':
      visited[y+i][x+j] = visited[y][x]+1
      Q.append([y+i,x+j])
    else:
      continue
print(-1)

Submission status: Accepted

Solution code:
from collections import deque


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((sx, sy))
  d[sx][sy] = 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 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == float('inf'):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
        
  return d[gx][gy]
  
  
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

white = 0
for i in range(h):
  for j in range(w):
    if maze[i][j] == '.':
      white += 1
      
res = bfs()
if 0 < res < float('inf'):
  print(white - res - 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    R,C= map(int,input().split())

    S = [0,0]

    mv = [[1,0],[-1,0],[0,-1],[0,1]]
    MAP = []
    flg = 0
    block = 0
    for _ in range(R):
        t = list(input())
        block += t.count('#')
        MAP.append(t)
    stack = deque([S])
    MAP_c = [[None]*C for _ in range(R)]
    MAP_c[0][0] = 1
    while stack:
        v = stack.popleft()
        for m in mv:
            u = [v[0]+m[0],v[1]+m[1]]
            if u[0] >=0 and u[0] < R and u[1] >= 0 and u[1] < C and MAP[u[0]][u[1]] == '.':
                MAP[u[0]][u[1]] = '#'
                MAP_c[u[0]][u[1]] = MAP_c[v[0]][v[1]] + 1
                stack.append(u)
                if u == [R-1,C-1]:
                    flg = 1

        if flg == 1:
            break

    if flg == 1:
        a = MAP_c[R-1][C-1]
        print(R*C - a - block)
    else:
        print(-1)


main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int,input().split())
S = [input() for _ in range(h)]
s = deque([(0,0)])  # サーチstack. 初期条件を設定
e = [[-1] * w for _ in range(h)]  # 探索済みノード集（総数Nを入れる）
e[0][0] = 0

def main():
    while len(s) > 0:  # len(s) > 0 でループ
        t = s.popleft()
        if is_end(t):  # 終了条件を満たすなら脱出
            break
        for i in get_children(t):  # t の子ノードを列挙
            if is_legal(i):  # i が探索対象として適切なら(この判定はget_children内でも可)
                if e[i[0]][i[1]] != -1:  # iが探索済みなら次へ(この判定はget_children内でも可)
                    continue
                s.append(i)
                e[i[0]][i[1]] = e[t[0]][t[1]] + 1 # 探索済としつつ距離を入れる
    cnt = 0
    for x in S:
        cnt += x.count(".")
    end = e[h-1][w-1]
    #printing()
    if end == -1:
        print(-1)
    else:
        print((cnt-2)-(end-1))
    
def printing():
    for i in range(len(e)):
        for j in range(len(e[i])):
            if e[i][j] == -1:
                print(S[i][j], end="")
            else:
                print(e[i][j], end="")
        print("")
    
def is_end(t):
    return t[0] == h-1 and t[1] == w-1

def get_children(t):
    return ((t[0]-1,t[1]),(t[0]+1,t[1]),(t[0],t[1]-1),(t[0],t[1]+1))

def is_legal(i):
    return -1 < i[0] < h and -1 < i[1] < w and S[i[0]][i[1]] == "."

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
map = [list(input()) for i in range(h)]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    sx = 0
    sy = 0
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    d[sx][sy] = 0
    que = deque([])
    que.append((sx, sy))
    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and map[nx][ny] != "#"\
            and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[h-1][w-1]
count = 0
for i in range(h):
    for j in range(w):
        if map[i][j] == '#':
            count += 1
short = bfs()
if short == float("inf"):
    ans = -1
else:
    ans = h * w - count - short - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

G = []
black = 0
for i in range(H):
    line = list(input())
    G.append(line)
    black += line.count("#")
    
ls = deque([[0, 0, 0]])
D = [[float("inf")] * W for i in range(H)]
direction = [[1,0], [-1,0], [0,1], [0,-1]]
find = False
while len(ls) > 0:
    h, w, depth = ls.popleft()
    
    if h == H-1 and w == W-1:
        route = depth + 1
        find = True
        break
        
    for dh, dw in direction:
        if h + dh < 0 or H-1 < h + dh: continue
        if w + dw < 0 or W-1 < w + dw: continue
        if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
            ls.append([h+dh, w+dw, depth+1])
            D[h+dh][w+dw] = depth + 1
            
if find:
    ans = (H * W) - black - route
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())#H行　　W列
L=[]
kuro=0
siro=0

for i in range(H):
    a=list(input())
    L.append(a)
    for i in a:
        if i=='#':
            kuro+=1
        else:
            siro+=1
#print(kuro,siro)
#print(L)
q=deque([[1,1]])
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=0
s=False
while q:
    #print(q)
    for i in range(len(q)):
        b=q.popleft()
        #print(b)
        if b==[H,W]:
            s=True
        #    print(num)
            print(H*W-kuro-num-1)
            break
        for m in move:
         #  print(m)
            if 1<=b[0]+m[0]<=H and 1<=b[1]+m[1]<=W and L[b[0]+m[0]-1][b[1]+m[1]-1]=='.':
                L[b[0]+m[0]-1][b[1]-1+m[1]]='#'
                q.append([b[0]+m[0],b[1]+m[1]])
        #print(L)
    num+=1
#print(L)
#print(num)
if not s:
    print('-1')

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
area = [['#']*(W+2)]
space = 0
for i in range(H):
    temp = ['#']+list(input())+['#']
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['#']*(W+2))
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
    
dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 1
    
while dq:
    nowx, nowy = dq.popleft()
    if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='#': continue
        dist[nxty][nxtx] = dist[nowy][nowx]+1
        dq.append((nxtx, nxty))
if dist[H][W]==-1: print(-1)
else: print(space-dist[H][W])

Submission status: Accepted

Solution code:
from collections import deque
import sys


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

M = []
w_count = 0
for i in range(H):
    s = input()
    w_count += s.count('.')
    M.append(s)

visited = [[False for _ in range(W)] for _ in range(H)]

q = deque([[0, 0, 1]])
while len(q) != 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    count = p[2]
    if x == W - 1 and y == H - 1:
        print(w_count - count)
        sys.exit(0)
    cands = []
    if x - 1 >= 0:
        cands.append([x-1, y])
    if x + 1 < W:
        cands.append([x+1, y])
    if y - 1 >= 0:
        cands.append([x, y-1])
    if y + 1 < H:
        cands.append([x, y+1])
    for cx, cy in cands:
        if M[cy][cx] == '.' and not visited[cy][cx]:
            q.append([cx, cy, count+1])
            visited[cy][cx] = True
print(-1)

Submission status: Accepted

Solution code:
import queue
INF=10**8
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
maze=[input() for _ in range(r)]
d=[[INF for i in range(r)] for _ in range(c)]
sx,sy=1,1
gx,gy=r,c
cnt=0
for i in range(r):
  for j in range(c):
    if maze[i][j]=='.':
      cnt+=1

sx-=1
sy-=1
gx-=1
gy-=1
q=queue.Queue()
dx=[-1,0,1,0]
dy=[0,-1,0,1]
q.put((sx,sy))
d[sy][sx]=0

while not q.empty():
  x,y=q.get()
  if (x,y)==(gx,gy):break
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<c and 0<=ny<r:
      if maze[ny][nx]=='.' and d[nx][ny]==INF:
        q.put((nx,ny))
        d[nx][ny]=d[x][y]+1
if d[gy][gx]==INF:
  print(-1)
else:print(cnt-d[gy][gx]-1)