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 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 = deque([(sy,sx)])

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

    return dist

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

Grid = [input() for _ in range(H)]

cnt = 0

for i in range(H):
    cnt += Grid[i].count('.')

d = gridbfs(Grid,0,0)

if d[H-1][W-1] == 10**18:
    print(-1)
else:
    print(cnt - d[H-1][W-1] -1)

Submission status: Accepted

Solution code:
#bfs
import queue

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
emp = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == '.':
            emp += 1

visited = [[0 for i in range(w)] for j in range(h)]
q = queue.Queue()
q.put([0, 0, 1])
visited[0][0] = 1
dyx = [[0, 1], [1, 0], [-1, 0], [0, -1]]
flag = False
while not q.empty():
    now = q.get()
    if now[0] == h-1 and now[1] == w-1:
        flag = True
        break
    for i in range(4):
        y = now[0] + dyx[i][0]
        x = now[1] + dyx[i][1]
        z = now[2]
        if 0 <= y < h and 0 <= x < w:
            if c[y][x] != '#' and visited[y][x] == 0:
                visited[y][x] = 1
                q.put([y, x, z+1])
if flag:
    print(emp-now[2])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

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

# よく考えたらBFSでOKだった
i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = deque([[i, j]])
while next_v:
    i, j = next_v.popleft()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "#":
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))

last = dist[h-2][w-2]
if last != INF:
    ans = total - last
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

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

i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = [(i, j)]
while next_v:
    i, j = next_v.pop()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "#":
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))

last = dist[h-2][w-2]
if last != INF:
    ans = total - last
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
black=0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      black+=1
s=[0,0,1]
g=[h-1,w-1]
queue=[s]
go=[[0,1],[0,-1],[1,0],[-1,0]]
ans=-1
check=[[True for i in range(w)] for j in range(h)]
while len(queue)>0:
  p=queue.pop(0)
  for i in range(4):
    x=p[0]+go[i][0]
    y=p[1]+go[i][1]
    count=p[2]+1
    if x>-1 and x<h and y>-1 and y<w and check[x][y] and maze[x][y]=='.':
      if x==g[0] and y==g[1]:
        ans=count
        break
      else:
        check[x][y]=False
        queue.append([x,y,count])
  if ans>0:
    break
if ans<0:
  print(ans)
else:
  print(h*w-black-ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

#幅優先探索（別ver）
def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "#"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
  return


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H,W = map(int,input().split())
G = [list(map(str, input())) for i in range(H)]
ans = 0
n = 0

#print(S)

for i in range(H):
    for j in range(W):
        if(G[i][j]=="."):
            n += 1
#print(n)
G[0][0] = 0
bfs(0,0)
#print(S)

if(type(G[H-1][W-1]) is str):
    ans = -1
else:
    ans = n - G[H-1][W-1]-1


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = []
for i in range(h):
    s = input()
    maze.append(list(s))
# 最短経路の道筋以外は全て黒にしていい
# dotの数の合計-スタートからゴールまでの最短経路で答えを求める
dotsum = 0
for row in maze:
    for j in row:
        if j == ".":
            dotsum += 1

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dp = [[-1] * (w + 1) for i in range(h + 1)]
dp[0][0] = 0

pos = deque([[0, 0, 0]])
dotroute = 0

while len(pos) > 0:
    x, y, depth = pos.popleft()
    if x == w - 1 and y == h - 1:
        dotroute = depth + 1
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == "." and dp[ny][nx] == -1:
            dp[ny][nx] = dp[y][x] + 1
            pos.append([nx, ny, depth + 1])
if dotroute == 0:
    print(-1)
else:
    print(dotsum - dotroute)

Submission status: Accepted

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

dist = [[0]*W for _ in range(H)]
count = 0

for i in range(H):
    for j in range(W):
        if s[i][j] == '#':  # 黒マスだった場合
            dist[i][j] = -1
        else:
            count += 1
dist[0][0] = 1  # スタートを１に更新

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

def bfs(move, dist):
    while move:
        y,x = move.popleft()
        d = dist[y][x]
        for dy,dx in ((0,1), (0,-1), (1,0), (-1,0)):
            new_y = y + dy
            new_x = x + dx
            if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
                continue
            if dist[new_y][new_x] == 0:  # セルが未到達のとき
                dist[new_y][new_x] = d+1
                move.append((new_y,new_x))
    return dist[H-1][W-1]
move_score = bfs(move,dist)
if move_score == 0:
    print(-1)
else:
    print(count - move_score)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [['#'] * (W + 2) for _ in range(H + 2)]
c = 0
for i in range(1, H+1):
    s = list(input())
    S[i] = ['#'] + s + ['#']
    c += s.count('.')

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = deque([(1, 1)])
S[1][1] = 1
while que:
    h, w = que.popleft()
    if (h, w) == (H, W):
        break
    for dh, dw in step:
        nh = h + dh
        nw = w + dw
        if S[nh][nw] != '.':
            continue
        que.append((nh, nw))
        S[nh][nw] = S[h][w] + 1
print(-1 if S[H][W] == '.' else c - S[H][W])

Submission status: Accepted

Solution code:
h , w = map(int,input().split())
g = ['#'*(w+2)]+['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
s = [[100]*(w+2)]+[[100]+[0]*w+[100]for i in range(h)]+[[100]*(w+2)]
queue=[]
head = 0
tail = 0
s[1][1]=1
queue.append([1,1])
tail+=1
while tail!=head:
    y = queue[head][0]
    x = queue[head][1]
    if g[y][x+1]=='.' and s[y][x+1]==0:
        queue.append([y,x+1])
        tail+=1
        s[y][x+1]=s[y][x]+1
    if g[y][x-1]=='.' and s[y][x-1]==0:
        queue.append([y,x-1])
        tail+=1
        s[y][x-1]=s[y][x]+1
    if g[y+1][x]=='.' and s[y+1][x]==0:
        queue.append([y+1,x])
        tail+=1
        s[y+1][x]=s[y][x]+1
    if g[y-1][x]=='.' and s[y-1][x]==0:
        queue.append([y-1,x])
        tail+=1
        s[y-1][x]=s[y][x]+1
    head+=1
if s[h][w]==0:
    print('-1')
else:
    count = 0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if g[i][j]=='#':
                count+=1
    ans = h*w - s[h][w]-count
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
WHITE_CELL_NUM = 0
for h in range(H):
    for w in range(W):
        if FIELD[h][w] == '.':
            WHITE_CELL_NUM += 1
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
ch, cw = sh, sw
frontier.append((ch, cw))
steps = [[-1 for _ in range(W)] for _ in range(H)]
steps[ch][cw] = 0
while len(frontier) > 0:
    ch, cw = frontier.popleft()  # current
    if ch == gh and cw == gw:  # reach goal
        break
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = ch + dh, cw + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if steps[nh][nw] >= 0:
            continue
        steps[nh][nw] = steps[ch][cw] + 1
        frontier.append((nh, nw))
if ch != gh and cw != gw:
    print(-1)
    exit(0)
shortest_path_length = steps[gh][gw] + 1
print(WHITE_CELL_NUM - shortest_path_length)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W + 2)

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

move = [1, -1, W + 2, -(W + 2)]
se = set([start])
q = deque([start])

T = [-1] * len(grid)
T[start] = 0


def bfs():
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid[y] == '#':
                continue
            if y in se:
                continue
            if y == goal:
                return T[x] + 1
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal]


ret = bfs()
print(len(root[1:]) - ret if ret != -1 else -1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    b = sum(r.count("#") for r in s)
    m = [[9999] * w for _ in range(h)]
    m[0][0] = 1
    n = deque([(0, 0)])
    d = set()
    while n:
        x, y = n.popleft()
        if (x, y) in d:
            continue
        if x == w - 1 and y == h - 1:
            break
        d.add((x, y))
        if x > 0 and s[y][x - 1] == ".":
            m[y][x - 1] = min(m[y][x - 1], m[y][x] + 1)
            n.append((x - 1, y))
        if x < w - 1 and s[y][x + 1] == ".":
            m[y][x + 1] = min(m[y][x + 1], m[y][x] + 1)
            n.append((x + 1, y))
        if y > 0 and s[y - 1][x] == ".":
            m[y - 1][x] = min(m[y - 1][x], m[y][x] + 1)
            n.append((x, y - 1))
        if y < h - 1 and s[y + 1][x] == ".":
            m[y + 1][x] = min(m[y + 1][x], m[y][x] + 1)
            n.append((x, y + 1))
    if m[h - 1][w - 1] == 9999:
        print(-1)
    else:
        print(h * w - b - m[h - 1][w - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])
    que.append((0,0))
    d[0][0] = 0
    while que:
        p = que.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<W and 0<=ny<H and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
    return d[H-1][W-1]

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

cnt = 1

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

if bfs() == float("inf"):
    print(-1)
else:
    print(H*W-bfs()-cnt)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        if [y,x]==[gy,gx]: #終了条件
            return visited[gy][gx]
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
    return -1 #たどり着けないとき

tate,yoko=map(int,input().split())
maze=[]
black=0
for i in range(tate):
    line=list(input())
    maze.append(line)
    black+=line.count('#')
sy,sx=0,0
gy,gx=tate-1,yoko-1
white=1+bfs()
if white==0: #たどり着けないとき1+-1=0
    ans=-1
else:
    ans=tate*yoko-black-white
print(ans)

Submission status: Accepted

Solution code:
from collections import  deque

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

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

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

for h in range(H):
    for w in range(W):
        if s[h][w] == ".":
            white += 1

q = deque()
q.append([0, 0])
dist[0][0] = 0
while(q):
    a = q.popleft()
    for i in range(4):
        if a[0] + dx[i] < 0 or a[0] + dx[i] >= W or a[1] + dy[i] < 0 or a[1] + dy[i] >= H:
            continue
        if s[a[1] + dy[i]][a[0] + dx[i]] == "#":
            continue
        if dist[a[1] + dy[i]][a[0] + dx[i]] == -1:
            dist[a[1] + dy[i]][a[0] + dx[i]] = dist[a[1]][a[0]] + 1
            q.append([a[0] + dx[i], a[1] + dy[i]])

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

Submission status: Accepted

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


def bfs(y, x):
    queue = deque([])
    queue.append((y, x))
    vgrid = [[float("inf")] * w for _ in range(h)]
    vgrid[y][x] = 0

    while queue:
        p = queue.popleft()
        if (p[0], p[1]) == (gy, gx):
            break
        for i in range(4):
            ny = p[0] + move[i][0]
            nx = p[1] + move[i][1]
            if 0 <= ny < h and 0 <= nx < w and vgrid[ny][nx] == float("inf") and grid[ny][nx] != "#":
                queue.append((ny, nx))
                vgrid[ny][nx] = vgrid[p[0]][p[1]] + 1

    return vgrid[gy][gx]


shortest_distance = bfs(0, 0)
if shortest_distance == float("inf"):
    print("-1")
    exit()
white = 0
for li in grid:
    white += li.count(".")
ans = white - shortest_distance - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def bfs(maze,visited,sy,sx):
  queue=deque([[sy,sx]])
  visited[sy][sx]=1
  while queue:
    y,x=queue.popleft()
    if [y,x]==[h-1,w-1]:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      n_y,n_x=y+j,x+k
      if not (0<=n_y<h and 0<=n_x<w):
        continue
      if maze[n_y][n_x]=='.' and visited[n_y][n_x]==0:
        visited[n_y][n_x]=visited[y][x]+1
        queue.append([n_y,n_x])
  return -1
cnt=0
for i in s:
  cnt+=i.count('.')
visited=[[0]*w for _ in range(h)]
route=bfs(s,visited,0,0)
print(-1 if route<0 else cnt-route)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze,visited,start_h,start_w,goal_h,goal_w):
  queue=deque([[start_h,start_w]])
  visited[start_h][start_w]=0
  while queue:
    h,w=queue.popleft()
    if [h,w]==[goal_h,goal_w]:
      return visited[goal_h][goal_w]
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
      new_h,new_w=h+i,w+j
      if new_h<0 or new_h>=H or new_w<0 or new_w>=W:
        continue
      if maze[new_h][new_w]=='.' and visited[new_h][new_w]==-1:
        visited[new_h][new_w]=visited[h][w]+1
        queue.append([new_h,new_w])

H,W=map(int,input().split())
maze=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]

cost=bfs(maze,visited,0,0,H-1,W-1)
if cost==None:
  print(-1)
else:
  cnt=-1
  for i in range(H):
    cnt+=maze[i].count('.')
  print(cnt-cost)

Submission status: Accepted

Solution code:
import queue

INF = 10 ** 10

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

costs = [[-1] * (W+2)]
for _ in range(H):
    costs.append([-1] + list(map(lambda c: -1 if c == '#' else INF, input())) + [-1])
costs.append([-1] * (W+2))

num_of_white = sum(row.count(INF) for row in costs)

togo = queue.Queue()
togo.put((1, 1))
costs[1][1] = 1

arrived = False
while not togo.empty():
    x, y = togo.get()
    
    if x == H and y == W:
        arrived = True
        break
    
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if costs[x+dx][y+dy] > costs[x][y] + 1:
            costs[x+dx][y+dy] = costs[x][y] + 1
            togo.put( (x+dx, y+dy) )

if arrived:
    print(num_of_white - costs[H][W])
else:
    print(-1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc088/tasks/abc088_d
# 最短経路を求めて，それ以外を塗る

# from heapq import heappush, heappop, heapify
from collections import deque

INF = int(1e18)
neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]

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


d = [[INF for _ in range(w)] for _ in range(h)]
queue = deque([(0, 0)])
# visited = set({})
# queue = [(0, (0, 0))]
# heapify(queue)
d[0][0] = 0
while len(queue) > 0:
    (y, x) = queue.popleft()
    for (dy, dx) in neighbors:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h:
            if MAP[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                queue.append((ny, nx))

# for drow in d: print(*drow)
if d[h - 1][w - 1] == INF:
    print(-1)
else:
    distST = d[h - 1][w - 1]
    count0 = 0
    for row in MAP:
        for ch in row:
            if ch == '#':
                count0 += 1
    print(h * w - count0 - distST - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
H, W = map(int, readline().split())
S = [['#'] * (W+2)] + [['#'] + list(readline().rstrip()) + ['#'] for _ in range(H)] + [['#'] * (W+2)] 
black = sum(row.count('#') for row in S) - 2*(W+2) - 2*H

# bfs
q = deque([(1, 1)])
S[1][1] = 1
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
while q:
    x, y = q.popleft()
    d = S[x][y]
    for dx, dy in direction:
        # print(x+dx, y+dy, S[x+dx][y+dy])
        if S[x+dx][y+dy] == '.':
            S[x+dx][y+dy] = d + 1
            q.append((x+dx, y+dy))
ans = -1
if S[H][W] != '.':
    ans = H*W - S[H][W] - black
print(ans)

Submission status: Accepted

Solution code:
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    cnt_white = sum(row.count('.') for row in grid)
    
    dist = [[-1] * w for _ in range(h)]
    q = deque([(0,0)])
    dist[0][0] = 1
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y >= h:
                continue
            if x < 0 or x >= w:
                continue
            if dist[y][x] < 0 and grid[y][x] == '.':
                dist[y][x] = dist[i][j] + 1
                q.append((y,x))
    
    ans = cnt_white - dist[-1][-1]
    print(ans if dist[-1][-1] >= 0 else -1)          
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

h,w=map(int,input().split())
s=[]
dist=[]
cnt=0
for i in range(h):
  s.append(input())
  dist.append([5000]*w)
  cnt+=s[i].count("#")
que=queue.Queue()
que.put([0,0])
dist[0][0]=0
d=[[0,1],[0,-1],[1,0],[-1,0]]
while not que.empty():
  place=que.get()
  for p in d:
    if -1<place[0]+p[0]<h and -1<place[1]+p[1]<w:
      if s[place[0]+p[0]][place[1]+p[1]]=="." and dist[place[0]][place[1]]+1<dist[place[0]+p[0]][place[1]+p[1]]:
        dist[place[0]+p[0]][place[1]+p[1]] = dist[place[0]][place[1]]+1
        que.put([place[0]+p[0],place[1]+p[1]])
if dist[h-1][w-1]<5000:
  print(h*w-cnt-dist[h-1][w-1]-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math



s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます

H = p[0]
W = p[1]

a = []
for i in range(H):
    a.append(input())


#パディング
#グリッド入力と組み合わせる
#上と下に入れる行を作る
b = ''
for i in range(W+2):
    b += '#'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = '#' + a[i] + '#'
a.append(b)











header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))

c=[]
for i in range(H+2):
    c.append([])

for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])


#print(header)
#for i in range(len(c)):
    #print('{}{}'.format(i,''.join(c[i])))



white = 0
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '.'):
            white += 1
#print('white:{}'.format(white))



start = [1, 1]
goal = [H, W]

c[start[0]][start[1]] = 'u'


def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))


queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 0
mode = 0
answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
answer = -1
#see_banmen()
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = 'u'
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = 'u'
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = 'u'
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = 'u'
            next_list.append([x, y-1])
        c[x][y] = 'd'
    else:
        #stepを進めます
        if(len(next_list) > 0):
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                answer = step
                answer_mode = 1
                #print()
                #print('goal:step{}'.format(answer))
                #print()
            step += 1
            #see_banmen()
        elif(mode == 0):
            #もう進めない
            mode = 1
            #print()
            #print('step{}end'.format(step))
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                #goal についているならgoal歩数を登録してanswer_mode を　1にする
                answer = step
                answer_mode = 1
                #print()
                #print('goal:step{}'.format(answer))
                #print()
            #goalについていない/goalについていなかったら歩数を進める
            step += 1
            #see_banmen()
        else:
            status = False
#print(answer)

#print(white - answer - 1)
if(answer == -1):
    print(-1)
else:
    print(white - answer - 1)

Submission status: Accepted

Solution code:
from collections import deque
r,c =map(int,input().split())
G = [input() for _ in range(r)]
black = 0
for i in range(r):
    for j in range(c):
        if G[i][j] == "#":
            black += 1
# print(black)

M = [[10**7 for _ in range(c)] for i in range(r)]
queue = deque([(0,0)])
M[0][0] = 0
while len(queue) != 0:
    now = queue.popleft()
    dxy = [(0,1),(0,-1),(1,0),(-1,0)]
    for p in dxy:
        nexte = (now[0]+p[0],now[1]+p[1])
        if nexte[0]<0 or nexte[0]>=r or nexte[1]<0 or nexte[1]>=c:
            continue
        else:
            if G[nexte[0]][nexte[1]] == ".":
                if M[nexte[0]][nexte[1]] > M[now[0]][now[1]] + 1:
                    M[nexte[0]][nexte[1]] = M[now[0]][now[1]] + 1
                    queue.append(nexte)
if M[r-1][c-1] == 10**7:
    print("-1")
else:
    print(r*c-1 - M[r-1][c-1] - black)

Submission status: Accepted

Solution code:
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(S, G):

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

    visited[S[0]][S[1]] = True
    que = deque([(S[0], S[1], 0)])

    while que:
        ci, cj, c = que.popleft()

        if ci == G[0] and cj == G[1]:
            return c

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and C[ni][nj] != '#':
                visited[ni][nj] = True
                que.append((ni, nj, c+1))
    return 0


sg = [[0, 0], [H-1, W-1]]
ans = 0
ans += bfs(sg[0], sg[1])

if ans == 0:
    print('-1')
else:
    num = sum([n.count('#') for n in C])
    result = H * W - (num + ans + 1)
    print(result)

Submission status: Accepted

Solution code:
r, c = map(int, input().split())
cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く


# 保留スタックtodoにスタートの位置情報を入れる
todo=deque([[0,0]])
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# 黒を数える
bcount=0
for i in range(r):
    bcount+=cc[i].count("#")

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
seen[0][0]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]

f=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
    if seen[r-1][c-1]!=-1:
        f=1
        break
if f==1: #到達可能
    # 面積-ゴールまでの最短手数-1(スタートのマス分)-元々あった黒のマス
    print(r*c-seen[r-1][c-1]-1-bcount)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start):
    Q = deque()
    child = deque()
    Q.append(start)
    dist[start[1] - 1][start[0] - 1] = 0

    while Q:
        x, y = Q.popleft()
        x = x - 1
        y = y - 1

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

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx + 1, ny + 1))

            if len(child) > 0:
                for c in child:
                    dist[c[1] - 1][c[0] - 1] = dist[y][x] + 1
                    Q.append(c)


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

kuro = 0
for i in range(H):
    G[i] = list(input())
    kuro += G[i].count('#')

dist = [[-1 for _ in range(W)] for _ in range(H)]
dx = [1, 0, -1, 0]  # 斜めも含むならその方向もプラス
dy = [0, 1, 0, -1]

start = (1, 1)
bfs(start)

# for i in range(H):
#     print(dist[i])

if dist[H - 1][W - 1] == -1:
    res = -1
else:
    res = H * W - (dist[H - 1][W - 1] + 1) - kuro

print(res)

Submission status: Accepted

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

def bfs(sx, sy):
    ans = 10**9
    dire = ((0, -1), (-1, 0), (1, 0), (0, 1))
    dist = [[-1]*W for _ in range(H)] # 未訪問は-1,訪問済みは距離
    dist[sx][sy] = 1
    que = deque([(sx, sy)]) # (sx, sy)からスタート
    while que:
        x, y = que.popleft()
        d = dist[x][y]
        for dx, dy in dire:
            nx,ny = x+dx,y+dy
            if nx==H-1 and ny==W-1 and S[nx][ny] == '.':
                ans = min(d+1,ans)
            # 内部で、通行可能('.')で、未訪問なら距離を更新し、dequeに入れる
            if 0<=nx<H and 0<=ny<W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                dist[nx][ny] = d+1
                que.append((nx, ny))
    return ans # これは(sx,sy)からの最長距離
black = 0
ans = bfs(0,0)
if ans == 10**9:
    print(-1)
else:
    for i in range(H):
        black += S[i].count('#')

    print(H*W-ans-black)