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

H,W = map(int,input().split())
_input = []
for i in range(H):
    row = list(map(str,input().split()))
    _input.append(list(row[0]))

sy,sx = 0,0
gy,gx = H-1,W-1

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

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

reach = False

while queue:
    y,x = queue.popleft()

    if (y,x) == (gy,gx):
        reach = True
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

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

        # 空きマスかつ未訪問
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

if not reach:
    print(-1)
    exit()
'''
y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'
'''

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res-counted_map[gy][gx]-1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

move = [[0,1],[1,0],[-1,0],[0,-1]]
distance = [[-1]*W for _ in range(H)]
distance[0][0] = 0
q = collections.deque()
q.append((0,0))

while q:
    h, w = q.popleft()
    cur = distance[h][w]
    for dh, dw in move:
        if not 0<=h+dh<=H-1 or not 0<=w+dw<=W-1:
            continue
        if distance[h+dh][w+dw] == -1 and s[h+dh][w+dw] == '.':
            distance[h+dh][w+dw] = cur + 1
            q.append((h+dh, w+dw))

num_white = 0
for x in s:
    num_white += x.count('.')

if distance[H-1][W-1] == -1:
    print(-1)
else:
    print(num_white - distance[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
H, W = [int(i) for i in input().split()]
sy, sx = [0,0]
gy, gx = [H-1, W-1]
c_ls = list()
yet_ls = [(sy,sx)]
dist_dict = {(sy, sx): 0}
road_len = 0
for i in range(H):
    c_ls.append([i for i in list(input())])
    road_len += len([i for i in c_ls[-1] if i == "."])


def dfs():
    ind = 0
    while len(yet_ls) > ind:
        y, x = yet_ls[ind]
        for move_y, move_x in [(1,0),(-1,0),(0,1),(0,-1)]:
            next_y = y + move_y
            next_x = x + move_x
            if 0 <= next_y < H and 0 <= next_x < W:
                pass
            else:
                continue
            if c_ls[next_y][next_x] == "#":
                continue
            c_ls[next_y][next_x] = "#"
            if (next_y, next_x) not in dist_dict:
                dist_dict[(next_y, next_x)] = dist_dict[(y,x)] + 1
                yet_ls.append((next_y,next_x))
            if (next_y, next_x) == (gy, gx):
                return dist_dict[(next_y, next_x)]
        ind += 1
    return road_len


print(road_len - dfs() - 1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
hw = [];count = 0;check = False
for i in range(h):
    ls = [x for x in input()]
    for j in range(w):
        if ls[j] == '.':count += 1
    hw.append(ls)
deq = deque()
matrix = [[False for j in range(w)] for i in range(h)]
deq.appendleft([0,0,0])
while deq:
    ls = deq.pop()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        x = ls[0]+i[0];y = ls[1]+i[1]
        if x < 0 or y < 0 or x >= h or y >= w:continue
        if matrix[x][y] or hw[x][y] == '#':continue
        if h-1 == x and w-1 == y:check = True;num = ls[2];break
        deq.appendleft([x,y,ls[2]+1])
        matrix[x][y] = True
    if check:break
if check:print(count-num-2)
else:print(-1)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python

H,W = map(int, input().split())
S   = [ input() for _ in range(H)]
inf = float("inf")
costmap = [ [inf] * W for _ in range(H)]


kuro_num = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            kuro_num += 1
shiro_num = H*W - kuro_num

from collections import deque
q = deque()

q.append( (0,0,0) )

shortest  = inf
while q:
    h,w,cost = q.popleft()
    if h == H-1 and w == W-1:
        shortest = cost
        break

    if w < W-1 and S[h][w+1] == "." and  costmap[h][w+1]==inf:
        q.append( (h, w+1, cost+1) )
        costmap[h][w+1] = cost+1

    if h < H-1 and S[h+1][w] == "." and  costmap[h+1][w] == inf:
        q.append( (h+1, w, cost+1) )
        costmap[h+1][w] = cost+1

    if 0< h and S[h-1][w] == "." and  costmap[h-1][w] == inf:
        q.append( (h-1, w, cost+1) )
        costmap[h-1][w] = cost+1
    if 0< w and S[h][w-1] == "." and  costmap[h][w-1] == inf:
        q.append( (h, w-1, cost+1) )
        costmap[h][w-1] = cost+1
if shortest == inf:
    ans = -1
else:
    ans  =  shiro_num - (shortest+1)
print(ans)

Submission status: Accepted

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

kabe = 0
for x in range(w):
    for y in range(h):
        if board[y][x] == "#":
            kabe += 1
s = [0, 0]
g = [h-1, w-1]
d = [[-1 for _ in range(w)] for _ in range(h)]
queue = []
queue.append(s)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while len(queue) != 0:
    p = queue.pop(0)
    if p[0] == g[0] and p[1] == g[1]:
        break
    for x, y in zip(dx, dy):
        nx = p[1] + x
        ny = p[0] + y
        if 0<=nx<w and 0<=ny<h and board[ny][nx] != "#" and d[ny][nx] == -1:
            d[ny][nx] = d[p[0]][p[1]] + 1
            queue.append([ny, nx])
if d[g[0]][g[1]] == -1:
    print(-1)
else:
    print(h*w - d[g[0]][g[1]] - kabe - 2)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
white = 0
for line in M:
    white += line.count('.')
visited = [[False for _ in range(W)] for _ in range(H)]
que = deque()
que.append((0, 0, 1))
visited[0][0] = True
dirction = ((1, 0), (0, 1), (-1, 0), (0, -1))
while que:
    h, w, count = que.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        break
    for i in range(4):
        nh, nw = (h + dirction[i][0], w + dirction[i][1])
        if 0 <= nh <= H - 1 and 0 <= nw <= W - 1:
            if M[nh][nw] == '.' and not visited[nh][nw]:
                que.append((nh, nw, count + 1))
                visited[nh][nw] = True
else:
    print(-1)

Submission status: Accepted

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

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

grid[0][0]=0
loc=[[0,0]]      
    
ans=0
for k in range(1,h*w):
  next_loc=[]
  for [y,x] in loc:
    for [i,j] in ([1,0],[-1,0],[0,1],[0,-1]):
      if 0<=y+i<=h-1 and 0<=x+j<=w-1:
        if grid[y+i][x+j]=='.':
          grid[y+i][x+j]=k
          next_loc.append([y+i,x+j])
    loc=next_loc
  if [h-1,w-1] in loc:
    ans=k
    break

if ans==0:
  print(-1)
else:
  print(sum-k-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
sx, sy = 0, 0
gx, gy = h - 1, w - 1
A = [list(input()) for i in range(h)]

INF = 100000000
D = [[INF] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]

def bfs():
    que = []
    que.append([sx, sy])
    D[sx][sy] = 0
    
    while que != []:
        p = que.pop(0)
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            
    return D[gx][gy]

r = bfs()

cnt = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == '.':
            cnt += 1
            
print(cnt - r - 1 if r != INF else -1)

Submission status: Accepted

Solution code:
import queue
H,W=map(int,input().split())
s=[list(input()) for i in range(H)]
dist=[[-1 for i in range(W)] for i in range(H)]
q=queue.Queue()
q.put((0,0))
dist[0][0]=0
dx=[-1,1,0,0]
dy=[0,0,1,-1]
while(not(q.empty())):
    r=q.get()
    x,y=r
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if dist[nx][ny]!=-1:
                continue
            if s[nx][ny]=="#":
                continue
            dist[nx][ny]=dist[x][y]+1
            q.put((nx,ny))
ans=dist[H-1][W-1]
sharp=0
for i in range(H):
    for j in range(W):
        if s[i][j]=="#":
            sharp+=1
if ans==-1:
    print(ans)
else:
    print(H*W-ans-1-sharp)

Submission status: Accepted

Solution code:
R, C = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
    (y, x, z) = q.pop(0)
    for v, w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        t = x + v
        u = y + w
        if t < 0 or t >= C or u < 0 or u >= R:
            continue
        if c[u][t] == '.' and (u, t) not in d:
            q.append((u, t, z + 1))
            d[u, t] = z + 1
if (R - 1, C - 1) not in d:
    ans = -1
else:
    ans = R * C - d[R - 1, C - 1] - 1
    for i in c:
        for j in i:
            if j == '#':
                ans -= 1
print(ans)

Submission status: Accepted

Solution code:
#ABC088D
H,W=map(int,input().split())
MAP=[]
brack=0
for i in range(H):
    line=input()
    brack+=line.count('#')
    MAP.append([line[j] for j in range(W)])
    

def bfs(H,W,MAP):
    dist=[[-1 for j in range(W)] for i in range(H)]
    dist[0][0]=1
    check=[(0,0)]
    while len(check)>0:
        now=check.pop(0)
        dnow=dist[now[0]][now[1]]
        for x in [(now[0]+1,now[1]),(now[0]-1,now[1]),(now[0],now[1]+1),(now[0],now[1]-1)]:
            if x[0]>=0 and x[1]>=0 and x[0]<H and x[1]<W:
                if x==(H-1,W-1):return dnow+1
                if MAP[x[0]][x[1]]=='.' and dist[x[0]][x[1]]==-1:
                    dist[x[0]][x[1]]=dnow+1
                    check.append(x)
    return dist[H-1][W-1]

ans=bfs(H,W,MAP)
if ans==-1:print(-1)
else:print(H*W-brack-ans)

Submission status: Accepted

Solution code:
from queue import deque

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

q = deque()
q.append((0,0))
distance = [[-1]*w for _ in range(h)]
distance[0][0] = 0
neighbors = [[0,1],[0,-1],[1,0],[-1,0]]

while q:
    pos_i, pos_j = q.popleft()
    cur_d = distance[pos_i][pos_j]
    for di, dj in neighbors:
        ni, nj = pos_i+di, pos_j+dj
        if not(0<=ni<h and 0<=nj<w):
            continue
        elif state[ni][nj]=='.' and distance[ni][nj]<0:
            distance[ni][nj] = cur_d+1
            q.append((ni,nj))

if distance[h-1][w-1] == -1:
    print(-1)
    exit()

n_white = sum(state[i].count('.') for i in range(h))
print(n_white-distance[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int, input().split())
adj = deque(maxlen=h*w)
maze = [list(input()) for _ in range(h)]
# maze = [[0]*w for _ in range(h)]
inf = 999999
dist = [[inf]*w for _ in range(h)]
max = h*w
for l in maze:
    max -= l.count('#')
# print(max)


def bfs(i,j):
    if maze[i][j]=='#' or (i,j) == (w-1,j-1):
        return
    maze[i][j]='#'
    d=dist[i][j] + 1
    if i+1<h:
        if maze[i+1][j]!='#' and dist[i+1][j]>d:
            adj.append([i+1,j])
            dist[i+1][j] = d
    if j+1<w:
        if maze[i][j+1]!='#' and dist[i][j+1]>d:
            adj.append([i,j+1])
            dist[i][j+1] = d
    if i-1>=0:
        if maze[i-1][j]!='#' and dist[i-1][j]>d:
            adj.append([i-1,j])
            dist[i-1][j] = d
    if j-1>=0:
        if maze[i][j-1]!='#' and dist[i][j-1]>d:
            adj.append([i,j-1])
            dist[i][j-1] = d

def print_maze(lst):
    for l in lst:
        print(l)
    print('\n')

adj.append([0,0])
dist[0][0]=1
time=0
while len(adj)>0:
    p = adj.popleft()
    bfs(p[0],p[1])
if dist[h-1][w-1] == inf:
    print(-1)
else:
    print(max - dist[h-1][w-1])

Submission status: Accepted

Solution code:
DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

H, W = [int(x) for x in input().split()]
G = []
B = 0

G.append('#' * (W + 2))
for i in range(H):
    s = input()
    B += s.count('.')
    G.append(['#'] + list(s) + ['#'])
G.append('#' * (W + 2))

que = [(1, 1, 1)]
ans = -1

while que:
    y, x, c = que.pop(0)
    if (y, x) == (H, W):
        ans = c
        break
    for dir in DIR:
        ny = y + dir[0]
        nx = x + dir[1]
        if G[ny][nx] == '.':
            G[ny][nx] = '#'
            que.append((ny, nx, c + 1))

print(B - ans if ans != -1 else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

neig = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

F = []
nW = 0
for _ in range(H):
    F.append(list(input()))
    nW += sum([1 for s in F[-1] if s == '.'])

ans = -1
q = deque()
q.append((0, 0, 1))
F[0][0] = 'V' # Visited

while q:
    y, x, count = q.popleft()
    if y == H - 1 and x == W - 1:
        ans = nW - count
        break
    for n in neig:
        ny, nx = y + n[0], x + n[1]
        if 0 <= ny < H and 0 <= nx < W:
            if F[ny][nx] == '.':
                q.append((ny, nx, count + 1))
                F[ny][nx] = 'V' # Visited

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
for j in range(h):
  s.append(list(map(str, input())))
  
def check(x, y):
  if x >= h or x < 0 or y >= w or y < 0:
    return False
  if s[x][y] ==  ".":
    return True
  else:
    return False

phase = 1
queue = [[0,0]]
while len(queue) > 0:
  tmp = []
  for q in queue:
    s[q[0]][q[1]] = phase
    if check(q[0] + 1, q[1]):
      tmp.append([q[0] + 1, q[1]])
    if check(q[0] - 1, q[1]):
      tmp.append([q[0] - 1, q[1]])
    if check(q[0], q[1] + 1):
      tmp.append([q[0], q[1] + 1])
    if check(q[0], q[1] - 1):
      tmp.append([q[0], q[1] - 1])
  queue = list(map(list, set(map(tuple, tmp)))) # 重複するリストを除く
  phase += 1
count = 0
for i in range(h):
  count += s[i].count("#")
if s[h-1][w-1] == ".":
  print(-1)
else:
  print(h*w - count - s[h-1][w-1])

Submission status: Accepted

Solution code:
# 最短経路を探す bfs
# (全体の白の数) - (けぬす君が通ったマスの数) = (答え)
from collections import deque
H,W = map(int,input().split())
grid = [[""]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
white = 0

for i in range(H):
    s = input()
    for j in range(W):
        grid[i][j] = s[j]
        if grid[i][j] == ".":
            white += 1

q = deque([[0,0]])
d = [[0,1],[1,0],[0,-1],[-1,0]]

while q:
    i,j = q.popleft()
    if (i,j) == (H-1,W-1):
        break
    for di,dj in d:
        ni = i+di; nj = j+dj
        if 0 <= ni <= H-1 and 0 <= nj <= W-1\
             and visited[ni][nj] == 0 and grid[ni][nj] == ".":
            visited[ni][nj] = visited[i][j] + 1
            np = [ni,nj]
            q.append(np)
if visited[H-1][W-1] > 0:
    ans = white - visited[H-1][W-1]
else:
    ans = -1
print(ans)

Submission status: Accepted

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

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

# 0,0 to h-1, w-1
d[0][0] = 0

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

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    count += l.count(".")

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Accepted

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

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

# 0,0 to h-1, w-1
d[0][0] = 0

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

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    for c in l:
        if c == ".":
            count += 1

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Accepted

Solution code:
from queue import Queue

inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

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

    while not q.empty():
        p = q.get()
        x = p[0]
        y = p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.put([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int, input().split())
sy,sx=1,1
gy,gx=h,w
cnt=0
delta=[[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d=[[float('inf')]*(w+2) for _ in range(h+2)]
d[sy][sx]=1
a=['#']*(w+2)
m.append(a)
for i in range(h):
    a='#'
    a+=input()
    a+='#'
    cnt+=a.count('.')
    m.append(a)
a=['#']*(w+2)
m.append(a)
q=deque()
q.append((sy,sx))
while len(q)>0:
    y,x=q.popleft()
    if y==gy and x==gx:
        break
    for dx,dy in delta:
        if d[y+dy][x+dx]==float('inf') and m[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
if d[gy][gx]==float('inf'):
    print(-1)
else:
    print(cnt-d[gy][gx])

Submission status: Accepted

Solution code:
from collections import deque

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


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

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    # print(i, j)

    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break
    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        # visited[tmpy][tmpx] = True

        # if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
            visited[tmpy][tmpx] = True
else:
    print(-1)
    exit()
# print(sum(visited[4]))
print(H * W - kuro - cost - 1)

Submission status: Accepted

Solution code:
#from queue import Queue

inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = []

    d[0][0] = 1
    q.append([0, 0])

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

    while q:
        p = q.pop()
        x, y = p[0], p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.append([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Submission status: Accepted

Solution code:

from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

cnt = 0
for i in range(H):
    l = input()
    for j in range(W):
        grid[i][j] = l[j]
        if l[j] == '.':
            cnt += 1


# 動的計画法 dp[i][j]->grid[i][j]に行くための最短距離
dp = [[float('inf')]*W for _ in range(H)]


def check_in(x, y):
    return 0 <= x < W and 0 <= y < H


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

    while Q:
        s = Q.popleft()
        if s[0] == H-1 and s[1] == W-1:
            return
        else:
            s_x = s[1]
            s_y = s[0]
            for x, y in zip(dx, dy):
                n_x = s_x+x
                n_y = s_y+y

                if check_in(n_x, n_y):
                    if grid[n_y][n_x] != "#" and dp[n_y][n_x] == float('inf'):
                        Q.append([n_y, n_x])
                        dp[n_y][n_x] = dp[s_y][s_x]+1


def solve():
    bfs()
    min_dist = dp[H-1][W-1]
    if min_dist == float('inf'):
        return -1
    else:
        return cnt - min_dist-1


print(solve())

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
mp = ["#" * (w + 1)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 1)]
white = 0
for y in range(h + 2):
    white += mp[y].count(".")
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
que = deque()
que.append((1, 1, 1))
visited = [[False] * (w + 2) for _ in range(h + 2)]
visited[1][1] = True
while que:
    score, x, y = que.popleft()
    if (x, y) == (w, h):
        print(white - score)
        break

    for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if mp[ny][nx] != "#" and not visited[ny][nx]:
            que.append((score + 1, nx, ny))
            visited[ny][nx] = True
else:
    print(-1)

Submission status: Accepted

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

# construct graph
from collections import defaultdict
edges = defaultdict(list)
for i in range(h):
    for j in range(w):
        idx = i * w + j
        if li[i][j] == '.':
            if i + 1 < h and li[i + 1][j] == '.':
                edges[idx].append(idx + w)
                edges[idx + w].append(idx)
            if j + 1 < w and li[i][j + 1] == '.':
                edges[idx].append(idx + 1)
                edges[idx + 1].append(idx)
goal = h * w - 1
# root search
from collections import deque
Q = deque()
Q.append(0)
reach = False
visited = {0}
pre = {0: None}
while len(Q) > 0:
    u = Q.popleft()
    if u == goal:
        reach = True
        break
    for v in edges[u]:
        if v not in visited:
            pre[v] = u
            visited |= {v}
            Q.append(v)

ans = -1
if reach:
    white = sum(a.count('.') for a in li)
    path = [goal]
    while True:
        path.append(pre[path[-1]])
        if pre[path[-1]] is None:
            break
    ans = white - len(path)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
c = 0
d = [[0]*(W+2) for _ in range(H+2)]
d[1][1]= 1
m.append("#"*(W+2))
for i in range(H):
    b = input()
    c +=b.count(".")
    a= "#"+b+"#"
    m.append(a)
q = deque()
m.append("#"*(W+2))
q.append((1,1))

while len(q)>0:
    y,x = q.popleft()
    if y == H and x == W:
        print(c-d[H][W])
        exit()
    for dx,dy in con:
        #print(y+dy,x+dx,d[y+dy][x+dx])
        if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] ==".":
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]+=d[y][x]+1
    #print(q)
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(i,j):
  visited = [[-1]*w for i in range(h)]
  que = deque()
  que.append([i,j])
  visited[i][j]=0
  
  while True:
    if not que:
      return -1
    
    [current_i,current_j] = que.popleft()
    
    if  current_i == h-1 and current_j == w-1:
      return visited[current_i][current_j]
  
    for next in [[-1,0],[+1,0],[0,-1],[0,+1]]:
      next_i = current_i + next[0]
      next_j = current_j + next[1]
      if 0<=next_i<h and 0<=next_j<w:
        if visited[next_i][next_j] == -1 and s[next_i][next_j]==".":
          visited[next_i][next_j] = visited[current_i][current_j]+1
          que.append([next_i,next_j])

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


if bfs(0,0)==-1:
  print(-1)
else:
  print(count_point-bfs(0,0)-1)

Submission status: Accepted

Solution code:
def bfs_min(w,h,data):
    queue = [[0,0]]
    check = [[0,0]]
    memo = [[0 for j in range(w)] for i in range(h)]
    while True:
        if len(queue) != 0:
            s = queue[0]
            hNow,wNow = s[0],s[1]
        else:
            return -1

        if hNow == H-1 and wNow == W-1:
            return memo[H-1][W-1]
        queue.pop(0)

        if hNow < h-1:
            if (data[hNow+1][wNow] == '.') and ([hNow+1,wNow] not in check):
                queue.append([hNow+1,wNow])
                check.append([hNow+1,wNow])
                memo[hNow+1][wNow] = memo[hNow][wNow] + 1

        if wNow < w-1:
            if (data[hNow][wNow+1] == '.') and ([hNow,wNow+1] not in check):
                queue.append([hNow,wNow+1])
                check.append([hNow,wNow+1])
                memo[hNow][wNow+1] = memo[hNow][wNow] + 1

        if hNow > 0:
            if (data[hNow-1][wNow] == '.') and ([hNow-1,wNow] not in check):
                queue.append([hNow-1,wNow])
                check.append([hNow-1,wNow])
                memo[hNow-1][wNow] = memo[hNow][wNow] + 1

        if wNow > 0:
            if (data[hNow][wNow-1] == '.') and ([hNow,wNow-1] not in check):
                queue.append([hNow,wNow-1])
                check.append([hNow,wNow-1])
                memo[hNow][wNow-1] = memo[hNow][wNow] + 1
        
        
            
    
    
    
    





H,W = list(map(int,input().split()))
s = [list(input()) for i in range(H)]
wh = 0
bl = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            wh += 1
        else:
            bl += 1

if bfs_min(W,H,s) >= 0:
    print(wh - bfs_min(W,H,s) - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import queue


class HW(object):
    def __init__(self, height: int, width: int):
        self.h = height
        self.w = width


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

cnt = 0
visited = [[0] * w for j in range(h)]


def bfs() -> int:
    q = queue.Queue()
    start = HW(0, 0)
    goal = HW(h - 1, w - 1)
    q.put([start.h, start.w])
    visited[start.h][start.w] = 1

    while q.qsize() > 0:
        tmp = q.get()
        now = HW(tmp[0], tmp[1])
        if now.h == goal.h and now.w == goal.w:
            return cnt - visited[now.h][now.w]

        for k in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nxt = HW(now.h + k[0], now.w + k[1])
            if not 0 <= nxt.h < h or not 0 <= nxt.w < w:
                continue
            elif maze[nxt.h][nxt.w] == '#':
                continue
            elif visited[nxt.h][nxt.w] == 0:
                q.put([nxt.h, nxt.w])
                visited[nxt.h][nxt.w] = visited[now.h][now.w] + 1
    return -1


def main() -> None:
    global cnt
    for i in range(h):
        cnt += maze[i].count('.')

    cnt = bfs()
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
white=0
S=[]
for _ in range(H):
    s=list(input())
    white+=s.count('.')
    S.append(s)

f=[[0 for i in range(W)] for j in range(H)]

def path(i,j):
    q=[]
    for k in [1,-1]:
        if 0<=i+k<H and f[i+k][j]==0 and S[i+k][j]=='.':
            q.append((i+k,j))
        if 0<=j+k<W and f[i][j+k]==0 and S[i][j+k]=='.':
            q.append((i,j+k))
    return q

flag=False
if S[0][0]=='.' and S[-1][-1]=='.':
    que = path(0,0)
else:
    que = []
f[0][0]=1

l=1
while len(que)>0 and flag==False:
    l+=1
    tmp=[]
    for q in que:
        if f[q[0]][q[1]]==0:
            tmp+=path(*q)
            f[q[0]][q[1]]=1
            if q==(H-1,W-1):
                flag=True
        que=tmp

if flag:
    print(white-l)
else:
    print(-1)