Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque
def MI(): return map(int, input().split())
def bfs():
  dist=[[INF] * (W+1) for _ in range(H+1)]
  dist[sx][sy]=0
  que=deque([])
  que.append((sx,sy))
  di=(-1,0,1,0)
  dj=(0,-1,0,1)
  while que:
    (x,y)=que.popleft()
    if x==gx and y==gy:
      break
    for k in range(4):
      ni=x+di[k]
      nj=y+dj[k]
      if 0<=ni<H and 0<=nj<W:
        if Map[ni][nj]!='#':
          if dist[ni][nj]==INF:
            dist[ni][nj]=dist[x][y]+1
            que.append((ni,nj))
  return dist[gx][gy]
H,W=MI()
Map=[list(input()) for _ in range(H)]
#Map2=[[input()] for _ in range(H)]
INF=float('inf')
(sx,sy)=(0,0)
(gx,gy)=(H-1,W-1)
res=bfs()
white=0
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
if 0<res<INF:
  ans=white-res-1
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
s = [list('#'+input()+'#') for i in range(h)]
s = [['#']*(w+2)]+s+[['#']*(w+2)]
z=0
for i in s:
  z += i.count('.')
ans = [[-1]*(w+2) for i in range(h+2)]
m = [[0,1],[0,-1],[1,0],[-1,0]]
ans[1][1] = 1
d = deque([[1,1]])
while len(d):
  x,y = d.popleft()
  for i,j in m:
    a,b = x+i,y+j
    if s[a][b] == '.' and ans[a][b] == -1:
      d.append([a,b])
      ans[a][b] = ans[x][y]+1
if ans[h][w] == -1:
  print(-1)
else:
  print(z-ans[h][w])

Submission status: Accepted

Solution code:
import queue
h,w=map(int,input().split())
INF=10**9
s=[[-1]* w for _ in range(h)]
b=0
for i in range(h):
	x=input()
	for j in range(w):
		if x[j]==".":
			s[i][j] = INF
		else:
			b+=1

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

def test(x,y,t):
	if 0<=x<h and 0<=y<w:
		u=s[x][y]
		if t<u:
			s[x][y]=t
			q.put((x,y))

while not q.empty():
	x,y=q.get()
	t=s[x][y]
	test(x+1,y,t+1)
	test(x-1,y,t+1)
	test(x,y+1,t+1)
	test(x,y-1,t+1)

x=s[h-1][w-1]
print(-1 if x==INF else h*w-b-x-1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
white = 0
maze = []
for _ in range(n):
  row = list(input())
  white += row.count(".")
  maze.append(row)
steps = [ [-1]*m for _ in range(n) ]
steps[0][0] = 0

q = deque([(0,0)])
while q:
  r,c = q.popleft()

  for x,y in [(1,0), (0,1), (-1,0), (0,-1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=n or nc>=m: continue
    if maze[nr][nc] == "#": continue
    if steps[nr][nc] != -1: continue
    steps[nr][nc] = steps[r][c] + 1
    if nr==n-1 and nc==m-1:
      break
    else:
      q.append((nr,nc))

if steps[n-1][m-1] == -1:
  print(-1)
else:
  print( white - steps[n-1][m-1] - 1)

Submission status: Accepted

Solution code:
import collections
 
H,W = list(map(int,input().split()))
S = [list(input()) for _ in range(H)]
copyS = [S[i][:] for i in range(H)]
que = collections.deque()
que.append([0,0])
 
d = [[float('inf') for _ in range(W)] for _ in range(H)]
d[0][0] = 0
S[0][0] = '#'
 
while len(que) != 0:
    y,x = que.popleft()
    if y == H-1 and x == W-1:
        break
    for direct in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0 <= y+direct[0] <= H-1 and 0 <= x+direct[1] <= W-1:
            if S[y+direct[0]][x+direct[1]] != '#':
                d[y+direct[0]][x+direct[1]] = d[y][x]+1
                S[y+direct[0]][x+direct[1]] = '#'
                que.append([y+direct[0], x+direct[1]])

if y != H-1 or x != W-1:
    print(-1)
    exit()

count = 0
for i in range(H):
    for j in range(W):
        if copyS[i][j] == '.':
            count += 1
print(count - (d[y][x]+1))

Submission status: Accepted

Solution code:
from collections import deque

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

cnt_white = 0
for row in s:
    cnt_white += row.count('.')

d = deque([[0, 0]])
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
goal_flag = False
while d:
    x, y = d.popleft()
    if x == h - 1 and y == w - 1:
        goal_flag = True
        break
    for i in range(4):
        pos_x, pos_y = x + dx[i], y + dy[i]
        if 0 <= pos_x < h and 0 <= pos_y < w and s[pos_x][pos_y] == '.' and dist[pos_x][pos_y] == -1:
            d.append([pos_x, pos_y])
            dist[pos_x][pos_y] = dist[x][y] + 1

if goal_flag:
    print(cnt_white - dist[h-1][w-1] - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
#<33>
#(0)初期設定
from collections import deque
H, W = map(int,input().split())
S = []
count = 0
for h in range(H):
    A = list(input())#文字列のままリストの入れてやる
    for a in A:
        if a == ".":
            count += 1#白マスの数
    S.append(A)

#(1)DFS
mas = deque([(0, 0, 0)])
while mas: #キューが空になるまで続く
    y, x, n = mas.popleft()
    if (0 <= y <= H -1) and (0 <= x <= W -1):#範囲内か
        if S[y][x] == ".":
            S[y][x] = n
            mas.append((y + 1, x, n + 1))
            mas.append((y, x + 1, n + 1))
            mas.append((y - 1, x, n + 1))
            mas.append((y, x - 1, n + 1))

#(2)出力環境
short = S[H -1][W -1]
if short == ".": #キューが空になったのにゴールが書き換えられていない時
    print("-1")
else:
    print(count - (short + 1))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
queue=[]
ans = 0
cn = 0
for i in maze:
     cn += i.count("#")
queue.append([0,0,0])
while len(queue)>0:
    x,y,cnt=queue.pop(0)
    ans=cnt
    if x == h - 1 and y == w - 1:
        print(h*w-ans-cn-1)
        exit()
    for i in range(4):
        X=x+dx[i]
        Y = y + dy[i]
        if not (0 <= X < h and 0 <= Y < w):
             continue
        if maze[X][Y]=="#":
            continue
        if maze[X][Y]==".":
            queue.append([X,Y,cnt+1])
            maze[X][Y]="#"
print(-1)

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
s=[list(input()) for i in range(h)]

blackCnt=0
for i in s:
  for j in i:
    if j=="#":
      blackCnt+=1


#スタートをキューに格納
q=[[0,0]]
route=[[1,0],[0,1],[-1,0],[0,-1]]
visited = [[0 for i in range(w)] for j in range(h)]
visited[0][0]=1
cnt=0
while q:
  
  for _ in range(len(q)):
    x,y = q.pop(0)
    
    for i in range(4):
      nx, ny = x+route[i][0], y+route[i][1]
      #条件に合致すれば追加
      if 0<=nx<h and 0<=ny<w and visited[nx][ny] == 0 and s[nx][ny] != '#':
        q.append([nx,ny])
        visited[nx][ny]=1
  cnt+=1
  if visited[h-1][w-1]==1:
    print(w*h-cnt-1-blackCnt)
    exit()
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
dist=[[-1]*(w+2) for _ in range(h+2)]
dist[1][1]=1
maze=[]
maze.append(['#' for _ in range(w+2)])
for i in range(h):
    maze.append(['#']+list(input())+['#'])
maze.append(['#' for _ in range(w+2)])
cnt=0
for i in range(h+2):
    for j in range(w+2):
        if maze[i][j]=='#':
            cnt+=1

d=[[-1,0],[1,0],[0,-1],[0,1]]
q=deque()
q.append([1,1])
while q:
    x,y=q.popleft()
    for dx,dy in d:
        if (0<=x+dx<=h+1) and (0<y+dy<w+1):
            if maze[x+dx][y+dy]==".":
                if dist[x+dx][y+dy]==-1 or dist[x+dx][y+dy]>dist[x][y]+1:
                    q.append([x+dx,y+dy])
                    dist[x+dx][y+dy]=dist[x][y]+1
if dist[h][w]==-1:
    print(-1)
else:
    print((h+2)*(w+2)-cnt-dist[h][w])

Submission status: Accepted

Solution code:
#create date: 2020-07-03 14:46

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    h, w = na()
    g = [[1] * (w+2)]
    white = 0
    for i in range(h):
        r = ns()
        white += r.count(".")
        g.append([1] + [1 if s=="#" else 0 for s in r] + [1])
    g.append([1] * (w+2))
    q = deque([[1,1]])
    move = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while q:
        x, y = q.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if g[nx][ny] > 0:
                continue
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))
    if g[h][w] == 0:
        print(-1)
    else:
        print(white - g[h][w] - 1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
chiz = [[] for _ in range(w)]
cnt = 0
for _ in range(h):
    tmp_list = input()
    for i in range(w):
        if tmp_list[i]=='.':
            cnt += 1
        chiz[i].append(tmp_list[i])
dq = deque([(0,0)])
chiz[0][0] = 0
while dq:
    i,j = dq.popleft()
    for e in [(1,0),(-1,0),(0,-1),(0,1)]:
        if i+e[0]>=0 and i+e[0]<w and j+e[1]>=0 and j+e[1]<h:
            if chiz[i+e[0]][j+e[1]] == '.':
                chiz[i+e[0]][j+e[1]] = chiz[i][j] + 1
                dq.append((i+e[0],j+e[1]))
try:
    print(cnt-chiz[w-1][h-1]-1)
except:
    print(-1)

Submission status: Accepted

Solution code:
from queue import Queue
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
white = 0
for g in G:
    white += g.count('.')
been = [[-1] * W for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = Queue()
que.put((0, 0))
been[0][0] = True
while not que.empty():
    h, w = que.get()
    for dx, dy in d:
        nh = h + dx
        nw = w + dy
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if been[nh][nw] != -1:
            continue
        if G[nh][nw] == '#':
            continue
        been[nh][nw] = been[h][w] + 1
        que.put((nh, nw))
if been[H-1][W-1] == -1:
    print(-1)
else:
    print(white - been[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque,Counter
import itertools
h,w=map(int,input().split())
s=[]
for i in range(h):
    si=list(input())
    s.append(si)
bfs_res=0;
que=deque()
visited=[[-1]*w for i in range(h)]

visited[0][0]=0
que.append((0,0,0))
while que:
    y,x,d=que.popleft()
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
        newy,newx=y+i,x+j
        if newy<0 or newx<0 or newy>=h or newx>=w:continue
        if s[newy][newx]=="." and visited[newy][newx]==-1:
            visited[newy][newx]=d+1
            que.append((newy,newx,d+1))
            
s=list(itertools.chain.from_iterable(s))
print(-1 if visited[-1][-1]==-1 else Counter(s)['.']-visited[-1][-1]-1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(sy, sx, gy, gx):
    # yが下方向，xが右方向
    d = [[float("inf")] * w for _ in range(h)]

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

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

    while que:

        p = que.popleft()

        if p[0] == gy and p[1] == gx:
            break

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

            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    if d[gy][gx] == float("inf"):
        return -1
    else:
        return d[gy][gx]


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

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

dis = bfs(0, 0, h - 1, w - 1)

if dis == -1:
    print(-1)
else:
    print(h * w - res - dis - 1)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W = map(int, input().split())
H += 2
W += 2
B = [0] * H
block = 0
for i in range(H):
    if i == 0 or i == H - 1:
        B[i] = '#' * W
    else:
        B[i] = '#' + input() + '#'
        block += B[i].count("#") - 2

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

from collections import deque
def bfs(start, goal):
    dist = [[-1] * W for _ in range(H)]
    q = deque([])
    sy, sx = start
    dist[sy][sx] = 1
    q.append(start)

    ys = [0, 1, 0, -1]
    xs = [1, 0, -1, 0]

    while len(q) > 0:
        y, x = q.popleft()
        if (y, x) == goal:
            return dist[y][x]

        for dy, dx in zip(ys, xs):
            ny, nx = y + dy, x + dx
            if B[ny][nx] == '#':
                continue
            if dist[ny][nx] != -1:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))
    return -1

res = bfs(start, goal)
if res == -1:
    print(res)
else:
    print((H - 2) * (W - 2) - block - res)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W = map(int, input().split())
H += 2
W += 2
B = [0] * H
block = 0
for i in range(H):
    if i == 0 or i == H - 1:
        B[i] = '#' * W
    else:
        B[i] = '#' + input() + '#'
        block += B[i].count("#") - 2

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

import queue
def bfs(start, goal):
    dist = [[-1] * W for _ in range(H)]
    q = queue.Queue()
    sy, sx = start
    dist[sy][sx] = 1
    q.put(start)

    ys = [0, 1, 0, -1]
    xs = [1, 0, -1, 0]

    while not q.empty():
        y, x = q.get()
        if (y, x) == goal:
            return dist[y][x]

        for dy, dx in zip(ys, xs):
            ny, nx = y + dy, x + dx
            if B[ny][nx] == '#':
                continue
            if dist[ny][nx] != -1:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.put((ny, nx))
    return -1

res = bfs(start, goal)
if res == -1:
    print(res)
else:
    print((H - 2) * (W - 2) - block - res)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[]
count=0
for _ in range (H):
    A=list(input())
    for a in A:
        if a=='.':
            count+=1
    S.append(A)

mas=deque([(0,0,0)])
while mas:
    y,x,n=mas.popleft()
    if 0<=y<=H-1 and 0<=x<=W-1:
        if S[y][x]=='.':
            S[y][x]=n
            mas.append((y+1,x,n+1))
            mas.append((y,x+1,n+1))
            mas.append((y-1,x,n+1))
            mas.append((y,x-1,n+1))
short=S[H-1][W-1]
if short=='.':
    print(-1)
else:
    print(count-(short+1))

Submission status: Accepted

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

gidx = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '.':
            grid[i][j] = gidx
            gidx += 1
node_cnt = gidx
g = [[] for _ in range(node_cnt)]
for i in range(h):
    for j in range(w):
        if grid[i][j] != '#':
            gidx = grid[i][j]
            #上下左右
            if i > 0 and grid[i-1][j] != '#':
                g[gidx].append(grid[i-1][j])
            if i < h-1 and grid[i+1][j] != '#':
                g[gidx].append(grid[i+1][j])
            if j > 0 and grid[i][j-1] != '#':
                g[gidx].append(grid[i][j-1])
            if j < w-1 and grid[i][j+1] != '#':
                g[gidx].append(grid[i][j+1])

num_white = sum(s.count('.') for s in g)
d = [-1] * node_cnt
seen = [False] * node_cnt

q = deque()
def bfs():
    q.append(0)
    d[0] = 0
    seen[0] = True
    while len(q) > 0:
        now_v = q.popleft()
        for new_v in g[now_v]:
            if seen[new_v]:
                continue
            seen[new_v] = True
            q.append(new_v)
            d[new_v] = d[now_v] + 1

bfs()
ok = True
if grid[0][0] == '#' or grid[h-1][w-1] == '#' or d[node_cnt - 1] == -1:
    ok = False

print(node_cnt - d[node_cnt - 1] - 1 if ok else -1)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
from queue import Queue

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

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


def solve():
    q = Queue()
    q.put((0, 0, 1))
    A[0][0] = "#"

    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    while not q.empty():
        cx, cy, cnt = q.get()

        if cx == W - 1 and cy == H -1:
            return cnt

        for xx, yy in zip(dx, dy):
            nx, ny = cx + xx, cy + yy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if A[ny][nx] == "#":
                continue
            A[ny][nx] = "#"
            q.put((nx, ny, cnt + 1))
        pass

    return -1

sh = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            sh += 1

d = solve()
print(H * W - d - sh if d >= 0 else -1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
h,w = map(int,input().split())
s = []
bcnt = 0
for i in range(h):
    ss = list(input())
    bcnt += ss.count("#")
    s.append(ss)
def next(x,y,h,w):
    global s
    ret = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    ans = []
    for i in ret:
        if i[0] >= 0 and i[0] < w and i[1] >= 0 and i[1] < h:
            if s[i[1]][i[0]] == ".":
                ans.append(i)
    return ans

queue = deque([(0,next(0,0,h,w))])
#print(queue)
visited = {(0,0):0}
while queue != deque([]):
    label = queue.popleft()
    #print(label)
    for i in label[1]:
        if not i in visited:
            visited[i] = label[0]+1
            queue.append((label[0]+1,next(i[0],i[1],h,w)))
if (w-1,h-1) in visited:
    print(h*w-bcnt-visited[(w-1,h-1)]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
#m = int(input())
h, w = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

black = 0
l = []
l.append(["#"] * (w+2))
for i in range(h):
    z = list(input())
    
    for j in range(len(z)):
        if z[j] == "#":
            black += 1
            
    z.append("#")
    z.insert(0, "#")
    l.append(z)
    
l.append(["#"] * (w+2))

q = deque([])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
f = [[float("INF") for i in range(w+2)] for j in range(h+2)]

q.append((1, 1, 0))
f[1][1] = 0
while q:
    y, x, cnt = q.popleft()
    if y == h and x == w:
        print(h * w - black - cnt - 1)
        sys.exit()
    
    for i in range(4):
        if l[y+dy[i]][x+dx[i]] == "." and f[y+dy[i]][x+dx[i]] != 0:
            q.append((y+dy[i], x+dx[i], cnt+1))
            f[y+dy[i]][x+dx[i]] = 0

print(-1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S =[]
for _ in range(H):
    a = input()
    S.append(a)
count =0
for i in range(H):
    for j in range(W):
        if S[i][j] =='.':
            count += 1
from collections import deque

seen = [[False]*(W) for _ in range(H)]
seen[0][0] = True
dq = deque([(0,0,1)])
d = [(1,0),(0,1),(0,-1),(-1,0)]
while dq:
    x,y,cnt = dq.popleft()
    if x ==H-1 and y ==W-1:
        print(count-cnt);exit()
    for dx,dy in d:
        if 0<=x+dx<H and 0<=y+dy<W and seen[x+dx][y+dy] ==False and S[x+dx][y+dy]=='.':
            seen[x+dx][y+dy] = True
            dq.append((x+dx,y+dy,cnt+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  que = deque([])
  que.append((sx,sy))
  d[sx][sy] = 0
  
  while que:
    lead = que.popleft()
    #lead == queを入れるところ
    if lead[0] == gx and lead[1] == gy:
      break
    for i in range(4):
      nx = lead[0] + dx[i]
      ny = lead[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[lead[0]][lead[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

w_squares = 0
#最初の白マスの総数をw_squaresへ
for i in range(h):
  for j in range(w):
    if maze[i][j] == ".":
      w_squares += 1 
      
score = bfs() #幅優先探索で最短で通る白マス総数を出力
if 0 < score < float("inf"):
  #ゴールの分も引く
  change_squares = w_squares - score - 1
  print(change_squares)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def resolve():
    H, W = map(int, input().split())
    maze = []
    cnt = 0
    for i in range(H):
        maze.append(list(input()))
        cnt += maze[-1].count('#')
    
    d = [[float('inf')] * W for _ in range(H)]
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    q = deque([(0, 0)])
    d[0][0] = 0
    goal = 0

    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (1
                    and 0 <= ny < H
                    and 0 <= nx < W
                    and maze[ny][nx] != '#'
                    and d[ny][nx] == float('inf')):
                q.append((ny, nx))
                d[ny][nx] = d[y][x] + 1
        if d[H - 1][W - 1] != float('inf'):
            goal = d[H - 1][W - 1] + 1
            break
    if goal:
        print(H * W - goal - cnt)
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import collections

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

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

dx = [1,0,-1,0]
dy = [0,1,0,-1]
field[0][0] = 0
q = collections.deque([])
q.append((0,0))
while q:
    s = q.popleft()
    y,x = s[0],s[1]
    c = field[y][x]
    if y == h-1 and x == w-1:
        print(white-c-1)
        exit()
    else:
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<= newy < h and 0<= newx < w and field[newy][newx] == ".":
                field[newy][newx] = c+1
                q.append((newy,newx))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
startx=0
starty=0
goalx=M-1
goaly=N-1

S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx

point=0

for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
        if S[i][j]==".":
            point+=1
        
        
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合

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

def dfs(y,x):

    todox=deque()
    todoy=deque()
    seen[y][x]=1
    todox.append(x)
    todoy.append(y)
    
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]+1
                    #print(seen)
                    return seen[ny][nx]
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
                
    return -1

ret=dfs(starty,startx)
if ret==-1:
    print(-1)
else:
    print(point-ret)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

INF = -1
dist = [[INF for i in range(W)] for j in range(H)]

q = deque([(0, 0)])
dist[0][0] = 0

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

while q:
    y, x = q.popleft()
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]

        if (ny < 0 or ny >= H or nx < 0 or nx >= W): continue
        if grid[ny][nx] == "#": continue
        if dist[ny][nx] != INF: continue

        dist[ny][nx] = dist[y][x] + 1
        q.append((ny, nx))

block = 0
for h in range(H):
    block += grid[h].count("#")



if dist[H-1][W-1] == INF:
    print(-1)
    exit()
else:
    ans = (H * W) - block - (dist[H-1][W-1] + 1)
    print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

H, W = MAP()
s = [input() for _ in range(H)]

cnt_black = sum([s[i].count("#") for i in range(H)])

check = [[-1]*W for _ in range(H)]
check[0][0] = 1
q = deque([(0, 0)])
dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while q:
	y, x = q.popleft()
	for i in range(4):
		ny = y + dy[i]
		nx = x + dx[i]
		if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == "." and check[ny][nx] == -1:
			check[ny][nx] = check[y][x] + 1
			q.append((ny, nx))


if check[H-1][W-1] == -1:
	print(-1)
	exit()
else:
	print(H*W - check[H-1][W-1] - cnt_black)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 17:46 -> 

from collections import deque

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

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

grid = []
num_shiro = 0
for i in range(H):
    grid.append(list(input()))
    num_shiro += sum([dot == '.' for dot in grid[i]])

# 最も近道させ、残りに黒マスを塗るのがよき.
# 幅優先探索
grid_queue = deque()
grid_queue.append((0,0))
grid[0][0] = 1

while len(grid_queue) != 0:
    x, y = grid_queue.popleft()
    depth = grid[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and 0 <= new_y < W and \
            grid[new_x][new_y] == '.':
            if (new_x, new_y) == (H-1, W-1):
                print(num_shiro-depth-1)
                exit(0)
            else:
                grid_queue.append((new_x, new_y))
                grid[new_x][new_y] = depth+1

if grid[H-1][W-1] == '.':
    print(-1)
else:
    print(num_shiro-grid[H-1][W-1])

Submission status: Accepted

Solution code:
import collections

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

z = [["b"] * W for _ in range(H)] #チェックしたマスはb(before)からa(after)にする
black = 0
for i in range(H):
    black += s[i].count("#") #最初の黒の数を数える
v = [[1,0], [0,1], [-1,0], [0,-1]] #動き方4パターン(↓ → ↑ ←)
que = collections.deque() #調べる候補リスト #調べ終わった要素は消す

#まず[0,0]
z[0][0] = "a"
s[0][0] = 1 #何歩で来れたかを代入していく #最初は1
que.append([0,0]) #最初の候補は[0,0]

#最短ルートを探す
while len(que) != 0: #候補がなくなるまで繰り返す
    i = que.popleft() #候補のうち1つを取り出し、リストから消す
    for dy, dx in v: #4パターンの動き方を考える
        y = i[0] + dy
        x = i[1] + dx
        if (0<=y<H and 0<=x<W and s[y][x]=="." and z[y][x]=="b"):
            z[y][x] = "a"
            s[y][x] = s[i[0]][i[1]] + 1
            que.append([y,x]) #進んだマスを新しく候補に入れる

if s[-1][-1] == ".": #[H,W]のマスに数字が入ってない→ゴールできない
    print(-1)
else: #「消せる白の最大数」=「全マス」-「黒マス」-「最短ルート」
    print(H*W - black - s[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = list(input() for _ in range(H))
dist = [[-1]*W for _ in range(H)]
dist[0][0] = 1

d = deque([[0, 0, 1]])
while d:
    x, y, c = deque.popleft(d)
    if x > 0:
        if dist[x-1][y] == -1 and S[x-1][y] == ".":
            dist[x-1][y] = c+1
            deque.append(d, [x-1, y, c+1])
    if y > 0:
        if dist[x][y-1] == -1 and S[x][y-1] == ".":
            dist[x][y-1] = c+1
            deque.append(d, [x, y-1, c+1])
    if x < H-1:
        if dist[x+1][y] == -1 and S[x+1][y] == ".":
            dist[x+1][y] = c+1
            deque.append(d, [x+1, y, c+1])
    if y < W-1:
        if dist[x][y+1] == -1 and S[x][y+1] == ".":
            dist[x][y+1] = c+1
            deque.append(d, [x, y+1, c+1])

road = 0
for ss in S:
    for s in ss:
        if s == ".":
            road += 1
if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(road-dist[H-1][W-1])