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:
from collections import deque
h,w=map(int,input().split())
s=[]
wall_num=0
for i in range(h):
    s.append(list(input()))
    wall_num+=s[i].count("#")

q=deque()

i=0
j=0
s[0][0]=0
q.appendleft([0,0])
while(len(q)>0):
    qi=q.popleft()
    j,i=qi[0],qi[1]
    num=s[j][i]
    if(i==w-1 and j==h-1):
        print(h*w - wall_num - num - 1)
        break
    if(i>0 and s[j][i-1]=="."):
        s[j][i-1]=num+1
        q.append([j,i-1])
    if(i<w-1 and s[j][i+1]=="."):
        s[j][i+1]=num+1
        q.append([j,i+1])
    if(j>0 and s[j-1][i]=="."):
        s[j-1][i]=num+1
        q.append([j-1,i])
    if(j<h-1 and s[j+1][i]=="."):
        s[j+1][i]=num+1
        q.append([j+1,i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

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

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            dist=1+dist
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

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

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            dist=1+dist
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist])

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

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

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            dist+=1
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist])

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

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

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])
while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()
            # print(x+xd,y+yd)
            dist+=1
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist])
# print(grid)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
if s[0][0]=="#" or s[-1][-1]=="#":
    print(-1)
    exit()
whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])
while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()
            # print(x+xd,y+yd)
            dist+=1
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist])
# print(grid)
print(-1)

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  from collections import deque
  
  h,w=map(int,input().split())

  countWhite=0
  maze=[]
  maze+=[["#"]*(w+2)]
  for e in sys.stdin.readlines():
    maze+=[["#"]+list(e[:-1])+["#"]]
    countWhite+=e.count(".")
  maze+=[["#"]*(w+2)]
  
  xy=[(1,0),(-1,0),(0,1),(0,-1)]
  
  que=deque()
  que.append([1,1,1])
  shortestPath=0
  while(que):
    point=que.popleft()
    x,y,step=point[0],point[1],point[2]

    if (x,y)==(h,w):
      shortestPath=step
      break
    if maze[x][y]!=".":
      continue
    maze[x][y]=str(step)
    for i,j in xy:
      que.append([x+i,y+j,step+1])
  
  print(countWhite-step)
  
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cnt = 0
grid = [list(input()) for i in range(n)]
grid2 = [[]]*n
for i in range(n):
  cnt += "".join(grid[i]).count("#")
  grid2[i] = ["#"] + grid[i] + ["#"]
  
grid2.insert(0,["#"]*(m+2))
grid2.append(["#"]*(m+2))
grid2[1][1] = 0
loc =[[1,1]]

for k in range(1,n*m):
  next_loc = []
  for y,x in loc:
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
      if grid2[y+i][x+j] == ".":
        grid2[y+i][x+j] = k
        next_loc.append([y+i,x+j])
  loc = next_loc
#  print(loc,k)
  if [n,m] in loc:
    break

ans = n*m - (k+1+cnt)

print(ans if ans > 0 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for i in range(1,H+1):
    tmp = input()
    s = list('#'+tmp+'#')
    map[i] = s
    ans += tmp.count('#')

check = [[1]*(W+2) for _ in range(H+2)]
count = [[0]*(W+2) for _ in range(H+2)]
q = deque([(1,1)])
check[1][1] = 0
while q:
    x,y = q.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        if check[x+i][y+j] and map[x+i][y+j] == '.':
            check[x+i][y+j] = 0
            q.append((x+i,y+j))
            count[x+i][y+j] = count[x][y]+1
zz = count[H][W]
count = set((np.array(count)).flatten())
if ans == 0:
    ans += 1
for i in count:
    if i > zz:
        ans -= 1
print(H*W-len(count)-ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for i in range(1,H+1):
    tmp = input()
    s = list('#'+tmp+'#')
    map[i] = s
    ans += tmp.count('#')

check = [[1]*(W+2) for _ in range(H+2)]
count = [[0]*(W+2) for _ in range(H+2)]
q = deque([(1,1)])
check[1][1] = 0
while q:
    x,y = q.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        if check[x+i][y+j] and map[x+i][y+j] == '.':
            check[x+i][y+j] = 0
            q.append((x+i,y+j))
            count[x+i][y+j] = count[x][y]+1
zz = count[H][W]
count = set((np.array(count)).flatten())
for i in count:
    if i > zz:
        ans -= 1
print(H*W-len(count)-ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

wall_count = 0
s = []
for _ in range(max_h):
    line = input()
    wall_count += line.count("#")
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]

# 迷路と同じサイズの距離表を作成.
# 値が0 -> 未訪問, それ以外 -> スタート地点からそれまでの距離となる
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

que = deque([(1, 1)])

while que:
  h, w = que.popleft()

  for i in range(4):
    dx, dy = dis_x[i], dis_y[i]
    if s[h+dy][w+dx] == '.' and dist[h+dy][w+dx] == 0:
      dist[h+dy][w+dx] = dist[h][w] + 1
      que.append((h+dy, w+dx))

print(max_h*max_w - wall_count - dist[max_h][max_w] - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
m = []
cnt_sharp = 0
for i in range(h):
    tmp = input()
    cnt_sharp += tmp.count('#')
    m.append(tmp)

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

# print(m)
q = deque([])
seen = [[0 for _ in range(w)] for _ in range(h)]
q.append((0, 0, 0))
road = 0
while q:
    y, x, cnt = q.popleft()
    seen[y][x] = 1
    if y == h - 1 and x == w - 1:
        road = cnt + 1
        break
    for ny, nx in zip(dy, dx):
        if 0 <= y + ny < h and 0 <= x + nx < w:
            if seen[y + ny][x + nx] == 0 and seen[y + ny][x + nx] != '#':
                seen[y + ny][x + nx] = 1
                # print(y + ny, x + nx, cnt)
                q.append((y + ny, x + nx, cnt + 1))

if road == 0:
    print(-1)
else:
    print(h * w - road - cnt_sharp)

Submission status: Wrong Answer

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


def check(a, b, w):
    return mass[a][b] == "." and not w[a][b]


stack = deque([(0, 0)])
visited = [[0] * w for _ in range(h)]
depth = [[1] * w for _ in range(h)]

while stack:
    i, j = stack.popleft()
    visited[i][j] = 1
    d_now = depth[i][j]
    if j < w-1:
        if check(i, j+1, visited):
            stack.append((i, j+1))
            depth[i][j+1] = d_now + 1
            if i == h-1 and j == w-2:
                break
    if i < h-1:
        if check(i+1, j, visited):
            stack.append((i+1, j))
            depth[i+1][j] = d_now + 1
            if i == h-2 and j == w-1:
                break

black = 0
for i in range(h):
    black += mass[i].count("#")
x = depth[h-1][w-1]
ans = h * w - x - black
if x == 1:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = [int(x) for x in input().split()]
maze = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[float('inf')] * W for i in range(H)]
black = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            black += 1

def bfs():
    q = deque()
    q.append([0, 0])
    d[0][0] = 0

    while q:
        x, y = q.popleft()
        if x == H - 1 and y == W - 1:
            break
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    return d[H-1][W-1]

print(H*W - black - (bfs() + 1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
s = []
black = 0

for i in range(H):
    line = list(input())
    s.append(line)
    black += line.count('#')

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

q = deque()
dq = deque()
q.append((0, 0))
dq.append(1)

visited = [(0, 0)]
while len(q) != 0:
    pos = q.popleft()
    if pos == (W - 1, H - 1):
        break
    d = dq.popleft()
    for dir in dirs:
        next = (pos[0] + dir[0], pos[1] + dir[1])
        if 0 <= next[0] <= W - 1 and 0 <= next[1] <= H - 1 and next not in visited:
            q.append(next)
            dq.append(d + 1)
            visited.append(next)

min_d = dq.popleft()
print(H * W - black - min_d)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())

s = []
black = 0
for i in range(H):
    l = list(input())
    for j in range(W):
        if l[j] == "#":
            black += 1
    s.append(l)
white = H*W-black

def dist():
    from collections import deque
    q = deque([(0,0,0)])
    s[0][0] = "#"
    while q:
        print(q)
        x,y,cnt = q.popleft()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx,ny = x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and s[nx][ny] != "#":
                if nx == H-1 and ny == W-1:
                    return cnt+1
                s[nx][ny] = "#"
                q.append((nx,ny,cnt+1))
    return -1
d = dist()
if d == -1:
    print(-1)
else:
    print(white-d-1)

Submission status: Wrong Answer

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

black = 0
for i in range(h):
    black += mass[i].count("#")
ans = h * w - black
if h == 1:
    ans = -1
print(ans)

Submission status: Wrong Answer

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


def check(a, b, w):
    return mass[a][b] == "." and not (a, b) in w


q = deque([(0, 0)])
visited = {(0, 0)}
depth = [[1] * w for _ in range(h)]

while q:
    i, j = q.popleft()
    visited.add((i, j))
    d_now = depth[i][j]
    if j < w-1:
        if check(i, j+1, visited):
            q.append((i, j+1))
            depth[i][j+1] = d_now + 1
    if 0 < j:
        if check(i, j-1, visited):
            q.append((i, j-1))
            depth[i][j-1] = d_now + 1
    if i < h-1:
        if check(i+1, j, visited):
            q.append((i+1, j))
            depth[i+1][j] = d_now + 1
    if 0 < i:
        if check(i-1, j, visited):
            q.append((i-1, j))
            depth[i-1][j] = d_now + 1


print(1)

Submission status: Wrong Answer

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


def check(a, b, w):
    return mass[a][b] == "." and not (a, b) in w


q = deque([(0, 0)])
visited = {(0, 0)}
depth = [[1] * w for _ in range(h)]

while q:

    i, j = q.popleft()
    visited.add((i, j))
    d_now = depth[i][j]
    if j < w-1:
        if check(i, j+1, visited):
            q.append((i, j+1))
            depth[i][j+1] = d_now + 1
    if 0 < j:
        if check(i, j-1, visited):
            q.append((i, j-1))
            depth[i][j-1] = d_now + 1
    if i < h-1:
        if check(i+1, j, visited):
            q.append((i+1, j))
            depth[i+1][j] = d_now + 1
    if 0 < i:
        if check(i-1, j, visited):
            q.append((i-1, j))
            depth[i-1][j] = d_now + 1

x = depth[h-1][w-1]
black = 0
for i in range(h):
    for j in range(w):
        if mass[i][j] == "#":
            black += 1
ans = h * w - x - black
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    #移動距離　最小値に更新していく
    d = [[float("inf")] * C for _ in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break

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

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                #全周を超えない　&　壁でない　&　未探索である
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]

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

maze = [list(input()) for _ in range(R)]

cnt = 0
for m in maze:
    cnt += m.count(".")

if cnt-bfs()-1 > 0:
    print(cnt-bfs()-1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

#スタート位置、ゴール位置の指定がある場合
def bfs():
    #移動距離　最小値に更新していく
    d = [[float("inf")] * C for _ in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break

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

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                #全周を超えない　&　壁でない　&　未探索である
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]

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

maze = [list(input()) for _ in range(R)]

cnt = 0
for m in maze:
    cnt += m.count(".")

print(cnt-bfs()-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#%%
INF = 1<<30
dist = [[INF]*W for _ in range(H)]
dist[0][0] = 0

import queue

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

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

keiro = [[[] for _ in range(W)] for _ in range(H)]

while not (q.empty()):
    cur = q.get()
    y,x = cur[0],cur[1]
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        d = dist[y][x] + 1
        if nx<0 or nx>=W or ny<0 or ny>=H:
            continue
        elif S[ny][nx] == '#':
            continue
        
        elif dist[ny][nx]>d:
            q.put([ny,nx])
            dist[ny][nx] = d
            keiro[ny][nx] = [y,x]

white = 0
for s in S:
    for t in s:
        if t=='.':
            white += 1

ans = white - dist[H-1][W-1] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    d = [[float('inf')] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

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

    while que:
        p = que.popleft()
        if p[0]==H-1 and p[1]==W-1:
            break

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

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

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

def notcount(H, W, maze):
    cnt = 0

    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                cnt += 1

    return cnt

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
s = (H * W - notcount(H, W, maze)) - (bfs() + 1)
#bfs()
print(s)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  white_cnt=0
  for x in field:
    white_cnt+=x.count('.')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return white_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt>inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]
  counter[h-1][w-1]=-2

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==-1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[-1]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==-1:
            counter[ny][nx]=cnt+1
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    
    if counter[y][x]<=cnt:
      continue
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]==inf:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  ind=0
  while len(q)>0:
    ind+=1
    if ind>10**7:
      break

    y,x,cnt=q.pop()
    counter[y][x]=cnt

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  visit_counter=[[0]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

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

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt
    visit_counter[y][x]+=1

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

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt:
            if visit_counter[ny][nx]<500:
              q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())