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 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    white = 0
    for s in S:
        white += s.count(".")
    q = []
    q.append((0, 0))
    memo = [[-1 for _ in range(W)] for _ in range(H)]
    memo[0][0] = 0
    while q != []:
        cur = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            next = (cur[0] + DIR[i][0], cur[1] + DIR[i][1])
            if not 0 <= next[1] < H:
                continue
            if not 0 <= next[0] < W:
                continue
            if S[next[1]][next[0]] == "#":
                continue
            if memo[next[1]][next[0]] != -1:
                continue
            memo[next[1]][next[0]] = memo[cur[1]][cur[0]] + 1
            q.append(next)
    if memo[H-1][W-1] == -1:
        print("-1")
    else:
        print(white - memo[H-1][W-1] - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.append("")
    _s.insert(0, "")
    s.append(_s)
s.append([""]*(w+2))

blacks = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == "#":
            blacks += 1

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

visited = [[float("inf")]*(w+2) for _ in range(h+2)]
visited[1][1] = 1

q = collections.deque([[1, 1]])
while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy
        if s[y][x] == "." and visited[y][x] == float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

if visited[h][w] == float("inf"):
    print(-1)
else:
    print(h*w - visited[h][w] - blacks)

Submission status: Accepted

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

while Q:
    x,y,d = Q.popleft()
    s[x][y] = "#"
    if x == H and y == W:
        route = d
        break
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        if s[x+dx][y+dy] == ".":
            Q.append((x+dx,y+dy,d+1))
            s[x+dx][y+dy] = "#"
else:
    print(-1)
    exit()

print(cnt-route)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
 
def min_route():
    global h,w
    stack = MyStack()
    stack.push(1,1)
    route[0][0] = 0
    while len(stack.stack) >= 1:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] += route_num
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] += route_num
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] += route_num
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] += route_num
        if route[h-1][w-1]  != 0:
            return route[h-1][w-1]
    print(-1)
    exit()
 
ans = white - min_route() - 1
 
if ans < 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
 
def min_route():
    global h,w
    stack = MyStack()
    stack.push(1,1)
    route[0][0] = 0
    n = 0
    while len(stack.stack) >= 1:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] += route_num
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] += route_num
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] += route_num
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] += route_num
        if route[h-1][w-1]  != 0:
            return route[h-1][w-1]
        n += 1
    print(-1)
    exit()
 
ans = white - min_route() - 1
 
if ans < 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

queue = deque()
queue.append((0, 0, 0))
count = None
while queue:
    ny, nx, steps = queue.popleft()
    if not (0 <= ny < H and 0 <= nx < W):
        continue
    if grid[ny][nx] == "#":
        continue
    grid[ny][nx] = "#"
    if ny == H - 1 and nx == W - 1:
        count = steps
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        queue.append((ny+dy, nx+dx, steps+1))

if count is None:
    ans = -1
else:
    ans = 0
    for line in raw_grid:
        ans += line.count(".")
    ans -= 2
    ans -= (count - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import *
h, w = map(int, input().split())
s = [input() for _ in range(h)]
p = [[-1] * w for _ in range(h)]
p[0][0] = 1
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
white = sum(row.count('.') for row in s)
queue = deque([(0, 0)])
clearable = False
while queue:
  x, y = queue.popleft()
  if x == w-1 and y == h-1:
    clearable = True
    break
  for dx, dy in d:
    nx, ny = x + dx, y + dy
    if not (0 <= nx < w and 0 <= ny < h):
      continue
    if s[ny][nx] == '#' or p[ny][nx] > 0 :
      continue
    p[ny][nx] = p[y][x] + 1
    queue.append((nx, ny) )
if clearable:
  print(white - p[h-1][w-1])
else:
  print(-1)

Submission status: Accepted

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

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = None
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if (not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '#' or (ni, nj) in used:
            continue
        used.add((ni, nj))
        que.append((ni, nj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

Submission status: Accepted

Solution code:
height, width = map(int, input().split(" "))
target = []
white_num = 0
for h in range(height):
    temp = [n for n in input()]
    white_num += temp.count(".")
    target.append(temp)
queue = [[0, 0]]
goal = -1
turn = 1
visited = [[0 for n in range(width)] for m in range(height)]
visited[0][0] = 1
all_move = [[0, 1], [0, -1], [1, 0], [-1, 0]]

while queue:
    next_queue = []
    for q in queue:
        here_x, here_y = q
        if here_x == width - 1 and here_y == height - 1:
            goal = turn
        for move in all_move:
            next_x, next_y = move[0] + here_x, move[1] + here_y
            if 0 <= next_x < width and 0 <= next_y < height:
                if not visited[next_y][next_x] and target[next_y][next_x] == ".":
                    visited[next_y][next_x] = 1
                    next_queue.append([next_x, next_y])
    queue = next_queue
    turn += 1
# print(visited, turn, white_num)
if goal >= 0:
    print(white_num - goal)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# 単純にスタートとゴールが固定（1,1) (h,w)のBFSで
# 最短経路を求めたら、h*w - cnt - 最初の黒マスの数　を返す
# inputで黒マスを数える
h,w = map(int,input().split())
board = [["#"]*(w+2) for _ in range(h+2)]
num_black = 0
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
        if s[j] == "#":
            num_black += 1
path = 0 # 最短経路のパス数
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
visit = deque()
start_pos = (1,1)
visit.append(start_pos)
cnt = [[-1]*(w+2) for _ in range(h+2)] # -1埋め
cnt[1][1] = 0 #スタート地点は0
while visit:
    point = visit.popleft()
    #print(point[0], point[1])
    for k in mv:
        pos = (point[0]+k[0],point[1]+k[1])
        #print(pos)
        if board[pos[0]][pos[1]] == ".":
            if cnt[pos[0]][pos[1]] == -1: #unvisited
                #print(i,j,"yes")
                cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                visit.append((pos[0],pos[1]))
                if pos[0] == h and pos[1] == w:
                    path = cnt[pos[0]][pos[1]]
                    break
if path == 0: print(-1)
else: print(h*w - path - num_black -1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
w = 0
for i in range(H):
    w += maze[i].count(".")
inf = 10**9
d = np.array([[inf]*W for _ in range(H)])
d[0][0] = 0
q = deque([])
q.append([0, 0])
nx, ny = 0, 0
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while len(q) > 0:
    p = q.popleft()
    if p[0] == H and p[1] == W:
        break
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H and d[ny][nx] == inf and maze[ny][nx]==".":
            q.append([ny, nx])
            d[ny][nx] = d[p[0]][p[1]] + 1
if d[H-1][W-1] == inf:
	print(-1)
else:
	print(w-(d[H-1][W-1]+1))

Submission status: Accepted

Solution code:
import collections

H,W = list(map(int,input().split()))
field = [["#"]*(W+2)]

white = 0
for i in range(H):
    field.append(list(input()))
    counter = collections.Counter(field[-1])
    white += counter["."]
    field[-1].insert(0,"#")
    field[-1].append("#")
field.append(["#"]*(W+2))

queue = collections.deque()
queue.append((1,1))

distances = [[-1]*(W+2) for i in range(H+2)]
distances[1][1] = 0

while queue:
    y,x = queue.popleft()
    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        newx,newy = x+i,y+j
        if field[newy][newx] == "." and distances[newy][newx] == -1:
            distances[newy][newx] = distances[y][x]+1
            if (newy,newx) == (H,W):
                break
            else:
                queue.append((newy,newx))

if distances[H][W] == -1:
    print(-1)
else:
    print(white-distances[H][W]-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
aw=0
for i in range(h):
  aw+=maze[i].count('.')
def bfs(maze,visited):
  q=deque([[0,0]])
  visited[0][0]=1
  while q:
    x,y=q.popleft()
    if [x,y]==[h-1,w-1]:
      return True,visited[x][y]
    for i,j in [[0,1],[1,0],[0,-1],[-1,0]]:
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==-1:
          visited[newx][newy]=visited[x][y]+1
          q.append([newx,newy])
  return False,-1
ok,path=bfs(maze,visited)
if ok:
  print(aw-path)
else:
  print(path)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(i.count('.') for i in S)

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = []
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        xi = s + di; yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
            continue
        used.add((xi, yj))
        que.append((xi, yj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
black = 0
v = [""] * h
for i in range(h):
    v[i] = input()
    for c in v[i]:
        black += c == '#'

d = [[(10 ** 18)]*w for j in range(h)]
d[0][0] = 0

q = deque()
q.append((0, 0))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while len(q):
    y, x = q.popleft()
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if not (0 <= ny and ny < h and 0 <= nx and nx < w):
            continue
        if v[ny][nx] == '#':
            continue
        if d[ny][nx] < (10 ** 18):
            continue
        d[ny][nx] = d[y][x] + 1
        q.append((ny, nx))

if d[h - 1][w - 1] == 10 ** 18:
    print(-1)
    exit()
print(h*w-black-d[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

si, sj = 0, 0
gi, gj = H-1, W-1

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


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

dis = [[INF]*W for _ in range(H)]
dis[si][sj] = 0

dq = deque([])
dq.append([si,sj])

while dq:
    p = dq.popleft()
    if p[0] == gi and p[1] == gj:
        break
    for i in range(4):
        ni = p[0] + di[i]
        nj = p[1] + dj[i]
        if 0 <= ni < H and 0 <= nj < W and field[ni][nj] != '#' and dis[ni][nj] == INF:
            dq.append([ni,nj])
            dis[ni][nj] = dis[p[0]][p[1]]+1

path_length = dis[gi][gj]
shiro = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            shiro += 1

if path_length != INF:
    ans = shiro - path_length - 1
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import collections

def bfs(si, sj, ei, ej):
    q = collections.deque()
    q.append([si, sj, 0])
    used = set()
    used.add((si, sj))
    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi + 1, prvj], [prvi - 1, prvj], [prvi, prvj + 1], [prvi, prvj - 1]]:
            if i < 0 or j < 0 or W <= i or H <= j or (i, j) in used:
                continue
            elif grids[j][i] == '.':
                if [i, j] == [ei, ej]:
                    return cost
                else:
                    q.append([i, j, cost + 1])
                    used.add((i, j))
    return -1


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

res = bfs(0, 0, W - 1, H - 1)
if res != -1:
    black_num = sum([row.count('#') for row in grids])
    print( H * W - black_num - 2 - res)
else:
    print(res)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
H-=1
W-=1
maze=[]
for i in range(H+1):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze[0][0]="S"

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

que=deque([[0,0]])
steps=[[-1]*(W+1) for i in range(H+1)]
steps[0][0]=0
flag=True

def bfs():
      global flag
      if len(que)>=1:
         now=que.popleft()
         now_step=steps[now[0]][now[1]]
         for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
               ny=now[0]+dy
               nx=now[1]+dx
               if 0<=ny<=H and 0<=nx<=W:
                     if ny==H and nx==W:
                           print((H+1)*(W+1)-(now_step+1+1)-(count))
                           flag=False
                           break
                     elif maze[ny][nx]==".":
                           maze[ny][nx]="A"
                           que.append([ny,nx])
                           steps[ny][nx]=now_step+1
                     else:
                           pass
      else:
         print(-1)
         flag=False

while(flag):
      bfs()

Submission status: Accepted

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

def bfs():
  dist = [[False]*W for _ in range(H)]
  D = ((1,0), (0,1), (-1,0), (0,-1))
  
  que = deque([])
  que.append((0,0))
  dist[0][0] = 0
  
  while que:
    p = que.popleft()
    for d in D:
      nx = p[0] + d[0]
      ny = p[1] + d[1]
      if H > nx >= 0 and W > ny >= 0 and C[nx][ny] != '#' and dist[nx][ny] is False:
        que.append((nx,ny))
        dist[nx][ny] = dist[p[0]][p[1]]+1
  return dist[H-1][W-1]

cnt = 0
for c in C:
  cnt += c.count('.')
  
ans = bfs()
if ans is False:
  print(-1)
else:
  print(cnt - 1 - ans)

Submission status: Accepted

Solution code:
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = [(sy,sx)]
    d = 1

    while q:
        qq = []
        for y,x in q:
            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                yy,xx = y+dy, x+dx
                if not (0 <= yy < gridy and 0 <= xx < gridx):
                    continue
                if grid[yy][xx] == '#':
                    continue
                if dist[yy][xx] != INF:
                    continue
                dist[yy][xx] = d
                qq.append((yy,xx))
        q = qq
        d += 1

    return dist

H,W = map(int,input().split())
grid = [input() for i in range(H)]
d = gridbfs(grid,0,0)
b = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            b += 1

print(max(H*W-b-d[H-1][W-1]-1,-1))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
numdot = sum([line.count('.') for line in m])

q = deque([[0, 0, 1]])
m[0][0] = '#'
goal = False
while q:
    i, j, score = q.popleft()
    if i == H-1 and j == W-1:
        goal = True
        break

    for movei, movej in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj or m[ni][nj] == '#':
            continue
        m[ni][nj] = '#'
        q.append([ni, nj, score+1])

if goal:
    print(numdot - score)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
white = sum(s.count(".") for s in S)
visited = [[-1] * W for _ in range(H)]
deq = deque([(0,0)])
visited[0][0] = 1
dia = [1, 0, -1, 0, 1]
while deq:
    i, j = deq.popleft()
    if i == H - 1 and j == W - 1:
        break
    d = visited[i][j]
    for x, y in zip(dia, dia[1:]):
        ii, jj = i + x, j + y
        if 0 <= ii < H and 0 <= jj < W and S[ii][jj] == "." and visited[ii][jj] < 0:
            visited[ii][jj] = d + 1
            deq.append((ii, jj))
print(white - visited[H-1][W-1] if visited[H-1][W-1] > 0 else -1)

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

from collections import deque

h, w = na()
s = [ns() for _ in range(h)]
m = [[s[i][j] for j in range(w)] for i in range(h)]
inf = 1 << 60
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    q = deque()
    q.append((0, 0))
    d = [[inf] * w for _ in range(h)]
    d[0][0] = 0
    while len(q):
        p = q.popleft()
        if p[0] == w-1 and p[1] == h-1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] != '#' and d[ny][nx] == inf:
                q.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
    return d[h-1][w-1]

b = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '#':
            b += 1

k = bfs()
if k == inf:
    res = -1
else:
    res = (h * w) - b - (k + 1)
print(res)

Submission status: Accepted

Solution code:
H,W=[int(x) for x in input().split()]
import heapq
A=[]
temp=0
for i in range(H):
	s=input()
	A.append(s)
	for j in range(W):
		if s[j]==".":
			temp+=1


B=[[1000000000000000 for i in range(W)] for j in range(H)]

#print(A)

queue=[]
heapq.heapify(queue)
heapq.heappush(queue,[1,0,0])
#print(queue)
ans=100000000000000000000
B[0][0]=1
while queue:
	#print(queue)
	count,x,y=heapq.heappop(queue)
	#print(count,x,y)
	if x==H-1 and y==W-1:
		ans=min(ans,count)
	else:
		if (x+1<=H-1 and A[x+1][y]==".") and B[x+1][y]>count+1:
			heapq.heappush(queue,[count+1,x+1,y])
			B[x+1][y]=count+1
		if (0<=x-1 and A[x-1][y]==".") and B[x-1][y]>count+1:
			heapq.heappush(queue,[count+1,x-1,y])
			B[x-1][y]=count+1
		if (y+1<=W-1 and A[x][y+1]==".") and B[x][y+1]>count+1:
			heapq.heappush(queue,[count+1,x,y+1])
			B[x][y+1]=count+1
		if (0<=y-1 and A[x][y-1]==".") and B[x][y-1]>count+1:
			heapq.heappush(queue,[count+1,x,y-1])
			B[x][y-1]=count+1
if ans==100000000000000000000:
	print(-1)
else:
	print(temp-ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = []
b = 0
for h in range(H):
    tmp = list(input())
    maze.append(tmp)
    for x in tmp:
        if x == ".":
            b += 1
sx, sy = 0, 0
gx, gy = W-1, H-1
dist = [[-1 for y in range(W)] for x in range(H)]
dist[sy][sx] = 0
que = deque([[sy, sx]])
while len(que) > 0:
    y, x = que.popleft()
    if y == gy and x == gx:
        break
    for n in range(4):
        ny, nx = y+[0,0,-1,1][n], x+[1,-1,0,0][n]
        if nx >= 0 and nx < W and ny >= 0 and ny < H and dist[ny][nx] == -1:
            if maze[ny][nx] == ".":
                dist[ny][nx] = dist[y][x] + 1
                que.append([ny, nx])
if dist[gy][gx] == -1:
    print(-1)
else:
    print(b-1-dist[gy][gx])

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    dist = [[f_inf] * w for _ in range(h)]
    
    D = ((1,0), (0,1), (-1,0), (0, -1))

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

    while que:
        p = que.popleft()
        for d in D:
            nx = p[0] + d[0]
            ny = p[1] + d[1]

            if h > nx >= 0 and w > ny >= 0 and \
               C[nx][ny] != '#' and \
               dist[nx][ny] == f_inf:
                que.append((nx, ny))
                dist[nx][ny] = dist[p[0]][p[1]]+1
    return dist[h-1][w-1]

h, w = map(int, input().split())
C =[input() for _ in range(h)]
f_inf = float('inf')

cnt = 0
for c in C:
    cnt += c.count('.')

if bfs() == f_inf:
    print(-1)
else:
    print(cnt - 1 - bfs())

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    dist = [[f_inf] * w for _ in range(h)]

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

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

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if h > nx >= 0 and w > ny >= 0 and \
               C[nx][ny] != '#' and \
               dist[nx][ny] == f_inf:
                que.append((nx, ny))
                dist[nx][ny] = dist[p[0]][p[1]]+1
    return dist[h-1][w-1]

h, w = map(int, input().split())
C =[input() for _ in range(h)]
f_inf = float('inf')

cnt = 0
for c in C:
    cnt += c.count('.')

if bfs() == f_inf:
    print(-1)
else:
    print(cnt - 1 - bfs())

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
 
def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                maze[new_y][new_x] == "." and   \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
 
    return -1
 
 
def main():
    sharp = 0
 
    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]
 
    for k in range(H):
        sharp += maze[k].count('#')
 
    print(bfs(H, W, maze, visited, sharp))
 
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
m = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]

cnt = 0
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if m[hi][wi]==".":
            cnt += 1

inf = 10**9
d = [[inf]*(w+2) for _ in range(h+2)]
q = deque([(1,1,1)])
d[1][1] = 1
while len(q):
    ch,cw,r = q.popleft()

    for hi,wi in [[ch+1,cw],[ch,cw+1],[ch-1,cw],[ch,cw-1]]:
        if m[hi][wi]=="." and d[hi][wi]>r+1:
            d[hi][wi]=r+1
            q.append((hi,wi,r+1))

if d[h][w]==inf:
    print(-1)
else:
    print(cnt-d[h][w])

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
meiro=[list('#'+input()+'#') for i in range(h)]
h+=2
w+=2
top=list('#'*w)
bot=list('#'*w)
meiro.insert(0,top)
meiro.append(bot)

def bfs(a,b):
    dist=[[-1]*w for i in range(h)]
    dist[b][a]=0
    q=deque([(a,b)])
    ans=-1
    flag=0
    while q:
        x,y=q.popleft()
        kyori=dist[y][x]
        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==w-2 and ny==h-2 and meiro[ny][nx]=='.':
                return kyori +1
            if dist[ny][nx]==-1 and meiro[ny][nx]=='.':
                dist[ny][nx]=kyori+1
                ans=max(ans,kyori+1)
                q.append((nx,ny))
    return -1
saitan = bfs(1,1)
if saitan==-1:
    print(-1)
else:
    cnt=0
    for i in range(h):
        cnt+=str(meiro[i]).count('.')
    ans=cnt-saitan-1
    print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
  ans += Gd[i].count('.')
INF = -1
direc = [[1,0,-1,0],[0,1,0,-1]]
Dis = [[INF]*W for _ in range(H)]
from collections import deque
def dfs(start,goal):
  q = deque([])# スタック
  Dis[start[0]][start[1]]=1
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（先頭）
    for i in range(4):
      hs = h+direc[0][i]
      ws = w+direc[1][i]
      if 0<=hs<H and 0<=ws<W and Dis[hs][ws]==INF:
        if Gd[hs][ws]=='.':
          q.append([hs,ws])
          Dis[hs][ws]=Dis[h][w]+1
  return Dis[goal[0]][goal[1]]
minpath = dfs([0,0],[H-1,W-1])
if minpath == INF:
  ans = INF
else:
  ans = ans - minpath
print(ans)