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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import deque
def bfs(Y,X,count):
    # print("now",Y+1,X+1)
    # print(count,"手目")
    reached[Y][X]=True

    if Y==goalY and X==goalX:
        result=0
        for i in range(H):
            for j in range(W):
                if F[i][j]=="#":
                    result+=1
        print(H*W - result - count -1)
        exit()

    if Y < H-1 :
        if F[Y+1][X]=="." and reached[Y+1][X]==False:
            # print(Y+1+1,X+1,"を積みます")
            yQUE.appendleft(Y+1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y+1][X]=True
    if X < W-1 :
        if F[Y][X+1]=="." and reached[Y][X+1]==False:
            # print(Y+1,X+1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X+1)
            cQUE.appendleft(count+1)
            reached[Y][X+1]=True
    if 0 < Y :
        if F[Y-1][X]=="." and reached[Y-1][X]==False:
            # print(Y-1+1,X+1,"を積みます")
            yQUE.appendleft(Y-1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y-1][X]=True
    if 0 < X :
        if F[Y][X-1]=="." and reached[Y][X-1]==False:
            # print(Y+1,X-1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X-1)
            cQUE.appendleft(count+1)
            reached[Y][X-1]=True    
    try:
        bfs(yQUE.pop(),xQUE.pop(),cQUE.pop())
    except:
        pass

H,W = map(int,input().split())
# R,C=7,8
# startY,startX = map(int,input().split())
startY=0
startX=0
# startY,startX = 1,1
# goalY,goalX = map(int,input().split())
goalX=W-1
goalY=H-1
# goalY,goalX = 3,4
F = list(list(input()) for _ in range(H))
# F = [
# '########',
# '#......#',
# '#.######',
# '#..#...#',
# '#..##..#',
# '##.....#',
# '########']
reached = [[False for i in range(W)] for i in range(H)]
count=0
# for i in range (R):
#     print("".join(F[i]))
xQUE =  deque(maxlen=1000000000)
yQUE =  deque(maxlen=1000000000)
cQUE =  deque()
# result=0
# for i in range(H):
#     for j in range(W):
#         if F[i][j]=="#":
#             result+=1
# print(result)
bfs(startY,startX,count)
# print(QUE)
print("-1")

Submission status: Wrong Answer

Solution code:
import numpy as np
 
H, W = map(int, input().split())
s = np.array([list(input()) for _ in range(H)])
s = np.pad(s, 1, "constant")
white = (s == ".").sum()
q = [(0, 1, 1)]

goal = False 
while q:
    d, x, y = q.pop(0)
    if x ==H and y == W :
        print(white - (d + 1))
        goal = True
    for dx, dy in [[0,1], [0, -1], [1,0], [-1,0]]:
        x = x + dx
        y = y + dy
        if s[x][y] == '.':
            s[x][y] = '#'
            q.append((d+1, x, y))
if not goal:
    print(-1)

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

from collections import deque

H, W = map(int, input().split())
maze = [ ['.' for _ in range(W)] for _ in range(H) ]
num_white = 0

for y in range(H):
    X = list(input().rstrip())
    for x in range(W):
        maze[y][x] = X[x]
        if X[x] == '.':
            num_white += 1

#print(maze)
# print(num_white)

# 1) まずゴールへの最短距離を求める
# 2) 全体の白ますの数 - 1) が答え

distance = [ [-1 for _ in range(W)] for _ in range(H) ]
#print(distance)

def bfs(x, y):
    distance[y][x] = 0
    q = deque([(x, y)])

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

        if y > 0 and maze[y-1][x] != '#' and distance[y-1][x] == -1:
            distance[y-1][x] = distance[y][x] + 1
            q.append( (x, y-1) )
        if y < H-1 and maze[y+1][x] != '#' and distance[y+1][x] == -1:
            distance[y+1][x] = distance[y][x] + 1
            q.append( (x, y+1) )
        if x > 0 and maze[y][x-1] != '#' and distance[y][x-1] == -1:
            distance[y][x-1] = distance[y][x] + 1
            q.append( (x-1, y) )
        if x < W-1 and maze[y][x+1] != '#' and distance[y][x+1] == -1:
            distance[y][x+1] = distance[y][x] + 1
            q.append( (x+1, y) )

bfs(0, 0)
nearest = distance[H-1][W-1]
#print(nearest)

# -1 はスタート地点の分
print (num_white - nearest - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
s = []
black = 0
for i in range(H):
    tmp = list(input())
    s.append(tmp)
    for j in range(W):
        if tmp[j] == "#":
            black += 1
white = H*W - black


q = [(0,0,0)]
while q:
    i, j, cnt = q.pop(0)
    s[i][j] = "#"
    for di, dj in [(1,0),(0,1),(-1,0),(0,-1)]:
        ni, nj = i+di, j+dj
        if ni == H-1 and nj == W-1:
            print(white-cnt-2)
            exit(0)
        elif 0 <= ni < H and 0 <= nj < W and s[ni][nj] == ".":
            q.append((ni,nj,cnt+1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)

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

Map = [[] for _ in range(H)]
reached = [[-1]*W for _ in range(H)]
route = [[False]*W for _ in range(H)]

q = deque()
check = False
b = 0
for y in range(H):
    for x in input():
        Map[y].append(x)
        if x=="#":
            b += 1

def BFS(x, y, pre):
    global check

    if x>=W or y>=H or x<0 or y<0 or Map[y][x]=="#" or reached[y][x]>=0:
        return

    reached[y][x] = pre + 1

    if x==(W-1) and y==(H-1):
        ans =H * W - reached[y][x] + 1 - b - 2
        print(ans)
        sys.exit()

    else:
        q.append((x + 1, y, pre + 1))
        q.append((x - 1, y, pre + 1))
        q.append((x, y + 1, pre + 1))

q.append((0,0,-1))
while q:
    BFS(*q.popleft())
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import numpy as np

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

Map = [[] for _ in range(H)]
reached = [[-1]*W for _ in range(H)]
route = [[False]*W for _ in range(H)]

q = deque()
check = False
b = 0
for y in range(H):
    for x in input():
        Map[y].append(x)
        if x=="#":
            b += 1

def BFS(x, y, pre):
    global check

    if x>=W or y>=H or x<0 or y<0 or Map[y][x]=="#" or reached[y][x]>=0:
        return

    reached[y][x] = pre + 1

    if x==(W-1) and y==(H-1):
        ans =H * W - reached[y][x] + 1 - b - 2
        print(ans)
        sys.exit()

    else:
        q.append((x + 1, y, pre + 1))
        q.append((x - 1, y, pre + 1))
        q.append((x, y + 1, pre + 1))

q.append((0,0,-1))
while q:
    BFS(*q.popleft())
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
padding = ['#' for _ in range(W + 2)]
Map = tuple([padding])
Map += tuple(['#'] + list(input()) + ['#'] for _ in range(H))
Map += tuple([padding])
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

done = [[-1 for _ in range(W + 2)] for _ in range(H + 2)]

q = deque()
push, pop = q.append, q.popleft
push((1, 1))
done[1][1] = 0
while q:
  y, x = pop()
  for dy, dx in dxy:
    if Map[y + dy][x + dx] == '.' and done[y + dy][x + dx] == -1:
      push((y + dy, x + dx))
      done[y + dy][x + dx] = done[y][x] + 1
  if done[H][W] != -1:
    break
    
cnt = 0
for i in range(1, H + 1):
  for j in range(1, W + 1):
    if Map[i][j] == '.':
      cnt += 1
print(cnt - done[H][W] - 1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
b = 0
l = [0]*h
for k in range(h):
  a = str(input())
  b += a.count('#')
  l[k] = a
#l = [str(input()) for _ in range(h)]
 
from collections import deque
 
s = deque()
visit = [[-1]*w for _ in range(h)]
s.append([0, 0])
visit[0][0] = 1
 
while s:
  y, x = s.pop()
  if y == h-1 and x == w-1:
    print((h-1)*(w-1)-b)
    exit()
  for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
    new_y, new_x = y+i, x+j
    if (new_x<0) or (new_x>=w) or (new_y<0) or (new_y>=h) or l[new_y][new_x]=='#' or visit[new_y][new_x]== 1:
      continue
    else:
      visit[new_y][new_x] = 1
      s.append([new_y,new_x])
else:
  print('-1')

Submission status: Wrong Answer

Solution code:
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = 0
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      count += 1
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import numpy as np

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

Map = [[] for _ in range(H)]
reached = [[-1]*W for _ in range(H)]
route = [[False]*W for _ in range(H)]

q = deque()
check = False
b = 0
for y in range(H):
    for x in input():
        Map[y].append(x)
        if x=="#":
            b += 1

def BFS(x, y, pre):
    global check

    if x>=W or y>=H or x<0 or y<0 or Map[y][x]=="#" or reached[y][x]>=0:
        return

    reached[y][x] = pre + 1

    if x==(W-1) and y==(H-1):
        ans =H * W - reached[y][x] + 1 - b - 2
        print(ans)
        sys.exit()

    else:
        q.append((x + 1, y, pre + 1))
        q.append((x - 1, y, pre + 1))
        q.append((x, y + 1, pre + 1))

q.append((0,0,-1))
while q:
    BFS(*q.popleft())

Submission status: Wrong Answer

Solution code:
from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if -1<x+dx<R and -1<y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
print(R*C-white-need-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if 0<=x+dx<R and 0<=y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
print(R*C-white-need-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]


def dfs(S, i, j):
    if i == H - 1 and j == W - 1:
        return True
    val = False
    if i < H - 1 and S[i + 1][j] != '#':
        val |= dfs(S, i + 1, j)
    if j < W - 1 and S[i][j + 1] != '#':
        val |= dfs(S, i, j + 1)
    return val


reached = dfs(S, 0, 0)
if not reached:
    print(-1)
    exit(0)

b = 0
for r in S:
    for c in r:
        if c == '#':
            b += 1
print((H - 1) * (W - 1) - b)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]

b = 0
for r in S:
    for c in r:
        if c == '#':
            b += 1
print((H - 1) * (W - 1) - b)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())

grid_array = [[0] * (W+2) for _ in range(H+2)]


white_count = 0
for i in range(1, H+1):
    grid = input()
    for j, x in enumerate(grid):
        if x == ".":
            grid_array[i][j+1] = 1
            white_count += 1

used_array = [[0] * (W+2) for _ in range(H+2)]

INF = 10 ** 5

distance_array = [[INF] * (W+2) for _ in range(H+2)]

tile_deque = deque()
tile_deque.append((1, 1))
used_array[1][1] = 1
distance_array[1][1] = 1
while len(tile_deque):
    i, j = tile_deque.pop()
    if used_array[i-1][j] == 0 and grid_array[i-1][j] == 1:
        used_array[i-1][j] = 1
        tile_deque.append((i-1, j))
        distance_array[i-1][j] = min(distance_array[i-1]
                                     [j], distance_array[i][j]+1)
    if used_array[i+1][j] == 0 and grid_array[i+1][j] == 1:
        used_array[i+1][j] = 1
        tile_deque.append((i+1, j))
        distance_array[i+1][j] = min(distance_array[i+1]
                                     [j], distance_array[i][j]+1)
    if used_array[i][j-1] == 0 and grid_array[i][j-1] == 1:
        used_array[i][j-1] = 1
        tile_deque.append((i, j-1))
        distance_array[i][j-1] = min(distance_array[i]
                                     [j-1], distance_array[i][j]+1)
    if used_array[i][j+1] == 0 and grid_array[i][j+1] == 1:
        used_array[i][j+1] = 1
        tile_deque.append((i, j+1))
        distance_array[i][j+1] = min(distance_array[i]
                                     [j+1], distance_array[i][j]+1)
# print(distance_array)
if distance_array[H][W] == INF:
    print(-1)
else:
    print(white_count-distance_array[H][W])

Submission status: Wrong Answer

Solution code:
h , w = map(int, input().split())
field = [["#"] * (w+2)]
for i in range(h):
  temp = input()
  field.append("#" + temp + "#")
field.append(["#"] * (w+2))
now = [[1, 1]]
dots_count = 0
for i in field:
  dots_count += i.count(".")
move = [[0,1], [1, 0], [0,-1], [-1, 0]]
s_field = [[None for _ in range(w+2)] for _ in range(h+2)]
s_field[1][1] = 1
while now:
  x , y = now.pop()
  for v, u in move:
    if field[y+u][x+v] == "." and s_field[y+u][x+v] ==None:
      s_field[y+u][x+v] = s_field[y][x]+1
      if y+u == h and x+v == w:
        print(dots_count-s_field[y+u][x+v])
        break
      now.append([x+v, y+u])
  else:
    if not now:
      print("-10")
      break
    continue
  break

Submission status: Wrong Answer

Solution code:
h , w = map(int, input().split())
field = [["#"] * (w+2)]
for i in range(h):
  temp = input()
  field.append("#" + temp + "#")
field.append(["#"] * (w+2))
now = [[1, 1]]
dots_count = 0
for i in field:
  dots_count += i.count(".")
move = [[0,1], [1, 0], [0,-1], [-1, 0]]
s_field = [[None for _ in range(w+2)] for _ in range(h+2)]
s_field[1][1] = 1
while now:
  x , y = now.pop()
  for v, u in move:
    if field[y+u][x+v] == "." and s_field[y+u][x+v] ==None:
      s_field[y+u][x+v] = s_field[y][x]+1
      if y+u == h and x+v == w:
        print(dots_count-s_field[y+u][x+v])
        break
      now.append([x+v, y+u])
  else:
    if not now:
      print(-1)
      break
    continue
  break

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

que = deque()
dist = [[-1 for i in range(W)] for j in range(H)]
que.append([0,0])
dist[0][0] = 0
while len(que) > 0:
	loc = que.popleft()
	if loc[0] < H - 1 and s[loc[0] + 1][loc[1]] == '.' and dist[loc[0] + 1][loc[1]] == -1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and s[loc[0] - 1][loc[1]] == '.' and dist[loc[0] - 1][loc[1]] == -1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and s[loc[0]][loc[1] + 1] == '.' and dist[loc[0]][loc[1] + 1] == -1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and s[loc[0]][loc[1] - 1] == '.' and dist[loc[0]][loc[1] - 1] == -1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] - 1])


distance = dist[H - 1][W - 1]
num = H*W
for i in range(H):
	for j in range(W):
		if s[i][j] == '#':
			num -= 1
num -= 1 + distance
print(num)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
INF = 10000000000
b = 0
maze = [[] for _ in range(h)]
for i in range(h):
  l = list(input())
  b += l.count("#")
  maze[i] = l

dist = [[INF for _ in range(w)] for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

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

while q:
  x, y = q.popleft()
  if (x == w-1) and (y == h-1): break
  for i in range(len(dx)):
    nx = x + dx[i]
    ny = y + dy[i]
    if (nx >= 0) and (nx < w) and (ny >= 0) and (ny < h) and (maze[ny][nx] != "#") and (dist[ny][nx] == INF):
      q.append((nx, ny))
      dist[ny][nx] = dist[y][x] + 1
      
print((h*w) - (dist[h-1][w-1]+1) - b)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

print(count)

Submission status: Wrong Answer

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

from collections import deque

def solve(R, C, sy, sx, gy, gx, mz):
  queue = deque()
  checked = set( )
  queue.append((sx, sy, 0))
  while queue:
    x, y, n = queue.popleft()
    if x == gx and y == gy:
      return n
    if x < 1 or x > C or y < 1 or y > R or mz[y-1][x-1] == '#':
      continue
    if (x, y) in checked:
      continue
    checked.add((x, y))
    queue.append((x+1, y, n+1))
    queue.append((x-1, y, n+1))
    queue.append((x, y+1, n+1))
    queue.append((x, y-1, n+1))
  return -1


if __name__ == '__main__':
  R, C = map(int, input().split(' '))
  sy, sx = 1, 1
  gy, gx = R, C
  mz = []
  whites = 0
  for r in range(R):
    tmp = input()
    mz.append(tmp)
    whites += tmp.count('.')
  n = solve(R, C, sy, sx, gy, gx, mz)
  if n < 0:
    print(-1)
  print(whites - n - 1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        if visit[hh][ww] == inf:
            visit[hh][ww] = calc_min(hh, ww)
        h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
        
        

def calc_min(hh, ww):
    h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
    min_num = inf
    for h_, w_ in h_w_list:
        if (h_ in range(h)) & (w_ in range(w)):
            min_num = min(min_num, visit[h_][w_])
    return min_num + 1
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
d = [[10**9 for _ in range(W)] for _ in range(H)]

w_count = -2
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      w_count += 1

que = deque()
que.append([0, 0])
d[0][0] = 0
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == 10**9 and maze[nx][ny] == ".":
      d[nx][ny] = d[p[0]][p[1]] + 1
      que.append([nx, ny])
print(w_count - d[H-1][W-1] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
d = [[10**9 for _ in range(W)] for _ in range(H)]

w_count = -2
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      w_count += 1

que = deque()
que.append([0, 0])
d[0][0] = 0
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == 10**9:
      d[nx][ny] = d[p[0]][p[1]] + 1
      que.append([nx, ny])
print(w_count - d[H-1][W-1] + 1)

Submission status: Wrong Answer

Solution code:
# ABC 088 D

from collections import deque

def resolve():
    WALL = -1
    UNVISITED = -2

    H, W = map(int, input().split())
    sy, sx = 0, 0
    gy, gx = H-1, W-1

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

    num_aile = 0

    for i in range(H):
        tmp = input()
        for j in range(W):
            if tmp[j] == '.':
                c[i][j] = UNVISITED
                num_aile += 1
            else:
                c[i][j] = WALL

    que = deque([[sy, sx]])
    c[sy][sx] = 0

    def BFS(x, y):
        for i, j in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if i < 0 or H <= i or j < 0 or W <= j:
                continue
            if c[i][j] == UNVISITED:
                que.append([i, j])
                c[i][j] = c[x][y] + 1

    while len(que) > 0:
        p = que.popleft()
        BFS(p[0], p[1])

    print(num_aile - c[gy][gx] - 1)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, goal_x, goal_y):
    count = 0
    Q = deque([(0, 0, 0)])
    while Q:
        x, y, level = Q.popleft()
        if [x, y] == [goal_x-1, goal_y-1]:
            for j in range(goal_x):
                count += maze[j].count('#')
            print(goal_x*goal_y - count - (level+1))
            exit()
        elif maze[x][y] == '.':
            maze[x][y] = level
            if x+1 < goal_x:
                Q += [(x+1, y, level+1)]
            if y+1 < goal_y:
                Q += [(x, y+1, level+1)]
            if 0 < x-1 < goal_x:
                Q += [(x-1, y, level+1)]
            if 0 < y-1 < goal_y:
                Q += [(x, y-1, level+1)]
    print('-1')
        
            
goal_x, goal_y = map(int, input().split())
maze = []
for i in range(goal_x):
    maze.append(list(input()))


bfs(maze, goal_x, goal_y)

Submission status: Wrong Answer

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

# bfs 
C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.' or len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list

if C[H-1][W-1] == '.':
    print(-1)
else:
    black = 0
    for h in C:
        for v in h:
            if v == "#":
                black += 1
    print(H*W-black-count-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
s = [[c=="." for c in input()] for _ in [0]*H]

def bsf_dist_grid(grid,start):
    H = len(grid)
    W = len(grid[0])
    d = [[-1]*W for _ in [0]*H]
    d[start[0]][start[1]] = 0
    q = [start]
    while q:
        qq = []
        for xy in q:
            x,y = xy
            d0 = d[y][x]
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                d[y+dy][x+dx] = d0+1
                qq.append((x+dx,y+dy))
        q = qq
    return d

print(sum(sum(a) for a in s) - bsf_dist_grid(s,(0,0))[-1][-1]-1)

Submission status: Wrong Answer

Solution code:
import numpy as np

h,w = map(int,input().split())
f = []
bk = 0
f.append(["#" for i in range(w+2)])
for i in range(h):
    l = list(input())
    for c in l:
        if c=="#":
            bk += 1
    f.append(["#"]+l+["#"])
f.append(["#" for i in range(w+2)])
#
# for l in f:
#     print(l)

visited = {"1,1":0}

now = [[1,1]]
next = []

def to_key(l):
    return str(l[0])+","+str(l[1])

flag = True
count = 1
while 1:
    if len(now) == 0:
        flag = False
        break
    for state in now:
        x = state[0]
        y = state[1]

        if x==h and y == w:
            break

        if f[x+1][y]=="." and to_key([x+1,y]) not in visited:
            next.append([x+1,y])
            visited[to_key([x+1,y])] = count
        elif f[x][y+1]=="." and to_key([x,y+1]) not in visited:
            next.append([x,y+1])
            visited[to_key([x,y+1])] = count
        elif f[x-1][y]=="." and to_key([x-1,y]) not in visited:
            next.append([x-1,y])
            visited[to_key([x-1,y])] = count
        elif f[x][y-1] == "." and to_key([x,y-1]) not in visited:
            next.append([x, y-1])
            visited[to_key([x,y-1])] = count
    count += 1
    now = next
    next = []

if flag:
    print(h*w-visited[to_key([h,w])]-bk-1)
else:
    if to_key([h,w]) in visited:
        print(h * w - visited[to_key([h, w])] - bk-1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
def main():
	H, W = map(int,input().split())
	pos = [""]*H
	for i in range(H):
		pos[i] = input()
	x = min(W, H)
	can_clear = True
	for dist in range(H+W):
		impossible_range = True
		for i in range(H):
			if i > dist:
				break
			if dist-i >= W:
				continue
			if pos[i][dist-i] == ".":
				impossible_range = False
				break
		if impossible_range:
			can_clear = False
			break
	if not can_clear:
		print(-1)
		return

	offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	def bfs(s, h, w):
		queue = [[0, 0, 0]]
		is_visited = [[False for _ in range(w)] for _ in range(h)]
		is_visited[0][0] = True
		while queue:
			cur = queue.pop(0)
			for o in offset:
				y, x = cur[0]+o[0], cur[1]+o[1]
				if x < 0 or x >= w or y < 0 or y >= h:
					continue
				if x == w-1 and y == h-1:
					return cur[2]+1
				if is_visited[y][x]:
					continue
				if s[y][x] == ".":
					queue.append([y, x, cur[2]+1])
					is_visited[y][x] = True
		return -1

	white_num = 0
	for i in range(H):
		for j in range(W):
			if pos[i][j] == ".":
				white_num += 1
	print(white_num-bfs(pos, H, W)-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	H, W = map(int,input().split())
	pos = [""]*H
	for i in range(H):
		pos[i] = input()
	x = min(W, H)
	can_clear = True
	for dist in range(H+W-1):
		impossible_range = True
		for i in range(H):
			if i > dist:
				break
			if dist-i >= W:
				continue
			if pos[i][dist-i] == ".":
				impossible_range = False
				break
		if impossible_range:
			can_clear = False
			break
	if not can_clear:
		print(-1)
		return

	offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	def bfs(s, h, w):
		queue = [[0, 0, 0]]
		is_visited = [[False for _ in range(w)] for _ in range(h)]
		is_visited[0][0] = True
		while queue:
			cur = queue.pop(0)
			for o in offset:
				y, x = cur[0]+o[0], cur[1]+o[1]
				if x < 0 or x >= w or y < 0 or y >= h:
					continue
				if x == w-1 and y == h-1:
					return cur[2]+1
				if is_visited[y][x]:
					continue
				if s[y][x] == ".":
					queue.append([y, x, cur[2]+1])
					is_visited[y][x] = True
		return -1

	white_num = 0
	for i in range(H):
		for j in range(W):
			if pos[i][j] == ".":
				white_num += 1
	print(white_num-bfs(pos, H, W)-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque([(0,0)])
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = 99999
dist = [[-1]*W for i in range(H)]
dist[0][0] = 0
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if nx<0 or nx>W-1 or ny<0 or ny>H-1: continue
        if src[ny][nx] == '#': continue
        if dist[ny][nx] >= 0: continue
        q.append((nx,ny))
        dist[ny][nx] = dist[y][x] + 1

d=dist[-1][-1]
ans=0
for w in dist:
	for i in w:
		if i!=-1:
			ans+=1

if d==-1:
	print(d)
else:
	print(ans-d-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque([(0,0)])
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = 99999
dist = [[INF]*W for i in range(H)]
dist[0][0] = 0
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if nx<0 or nx>W-1 or ny<0 or ny>H-1: continue
        if src[ny][nx] == '#': continue
        if dist[ny][nx] < INF: continue
        q.append((nx,ny))
        dist[ny][nx] = dist[y][x] + 1

ans=0
for w in dist:
	for i in w:
		if i!=INF:
			ans+=1

if dist[-1][-1]==INF:
	print(-1)
else:
	print(ans-dist[-1][-1]-1)