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:
h,w=map(int, input().split())
m=[input() for _ in range(h)] 
#m = Input.split()
from collections import deque
cnt_black = 0
for y in range(h):
    for x in range(w):
        if(m[y][x]=='#'):
            cnt_black += 1
cnt_white =h*w-cnt_black

sy,sx = 0,0
#q: 次に訪れる予定の座標
q = deque([(sy,sx)])
#print(q)

#カウンタ
cnt = [[-1]*w for _ in range(h)]
cnt[sy][sx]=0
while q:
    cy,cx = q.popleft() #popleftで幅、popで深さ
    for dy,dx in ([1,0],[-1,0],[0,1],[0,-1]):
        ny, nx = cy + dy, cx + dx
        if(0<=ny<h and 0<=nx<w and cnt[ny][nx]==-1 and m[ny][nx]!='#'):
            #print(cy,cx,ny,nx)
            cnt[ny][nx] = cnt[cy][cx]+1
            q.append((ny,nx))
            #print(q)
            #pprint(cnt)
ans = cnt_white-1-cnt[h-1][w-1]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = list(map(int, input().split()))
s = ['#'*(w+2)]
[s.append('#'+input()+'#') for _ in range(h)]
s.append('#'*(w+2))
whitecount = 0
for i in s:
    whitecount += i.count('.')

ans = 0
queue = deque([[1,1]])
cost = [[1]*(w+2) for _ in range(h+2)]
visited = [[False]*(w+2) for _ in range(h+2)]
while queue:
    x,y = queue.popleft()
    visited[y][x] = True
    hjkl = [[x-1,y], [x,y-1], [x+1,y], [x,y+1]]
    for dx,dy in hjkl:
        if (s[dy][dx]=='.') and (visited[dy][dx]==False):
            queue.append([dx,dy])
            cost[dy][dx] = cost[y][x] + 1

print(whitecount - cost[h][w])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()
grid = [list(S()) for i in range(H)]

ans = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == ".":
      ans += 1

data = [[MAX_INT]*W for i in range(H)]

d = deque()
d.append((1, 0, 0)) # (cnt, h, w)
while d:
  cnt, h, w = d.popleft()
  if data[h][w] > cnt:
    data[h][w] = cnt
    for i,j in ((-1,0), (0,-1),(1,0),(0,1)):
      if 0 <= h+i < H and 0 <= w+j < W:
        if grid[h+i][w+j] == ".":
          d.append((cnt+1, h+i, w+j))
print(ans - data[-1][-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = [int(i) for i in input().split(' ')]

MAP = []
SUM = 0 
for i in range(H):
    tmp = list(input())
    a = []
    for i in tmp:
        if i == '.':
            a.append(0)
        else:
            a.append(1)
    SUM += tmp.count('#')
    MAP.append(a)

# print(MAP,SUM)
mapp =np.array(MAP)
S = [[0,0]]
# print(S)
# print(H,W)
for _ in range(105):
    tmp = []
    for s in S:
        if not s[1] == W -1:
            if mapp[s[0], s[1]+1] == 0:
                a = [s[0], s[1]+1]
                tmp.append(a)
        
        if not s[0] == H -1:
            if mapp[s[0]+1,s[1]] == 0:
                a = [s[0]+1, s[1]]
                tmp.append(a)
    S = tmp
    if len(S) == 0:
        print(-1)
        exit()
    if [H-1,W-1] in S:
        move = H+ W -1
        print(H*W - move - SUM)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = [int(i) for i in input().split(' ')]

MAP = []
SUM = 0 
for i in range(H):
    tmp = list(input())
    a = []
    for i in tmp:
        if i == '.':
            a.append(0)
        else:
            a.append(1)
    SUM += tmp.count('#')
    MAP.append(a)

# print(MAP,SUM)
mapp =np.array(MAP)
S = [[0,0]]

for _ in range(105):
    tmp = []
    for s in S:
        if not s[1] == W -1:
            if mapp[s[0], s[1]+1] == 1:
                a = [s[0], s[1]+1]
                tmp.append(a)
        
        if not s[0] == H -1:
            if mapp[s[0]+1,s[1]] == 0:
                a = [s[0]+1, s[1]]
                tmp.append(a)
    S = tmp
    if len(s) == 0:
        print(-1)
        exit()

move = H+ W -1
print(H*W - move - SUM)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import heapq
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    H, W = map(int, input().split())
    G = []
    for _ in range(H):
        G.append(list(input()[:-1]))
    
    C = [[INF] * W for _ in range(H)]
    C[0][0] = 1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == "#":
                cnt += 1
                continue
            if i + 1 < H:
                C[i+1][j] = min(C[i+1][j], C[i][j] + 1)
            if j + 1 < W:
                C[i][j+1] = min(C[i][j+1], C[i][j] + 1)

    if C[H-1][W-1] == INF or G[H-1][W-1] == "#":
        print(-1)
    else:
        print(H * W - (C[H-1][W-1] + cnt))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
memo = [[0 for _ in range(w)] for _ in range(h)]
step = [[1, 0], [-1, 0], [0, 1], [0, -1]]

memo[0][0] = 1
white = 0
for row in maze:
    white += row.count('.')

q = [[0, 0, 0]]

while q:
    x, y, c = q.pop(0)
    for a, b in step:
        next_x = x + a
        next_y = y + b
        if next_x == h - 1 and next_y == w - 1:
            print(white - (c + 2))
            exit()
        if next_x >= h or next_x < 0:
            continue
        if next_y >= w or next_y < 0:
            continue
        if memo[next_x][next_y] == 1:
            continue
        memo[next_x][next_y] = 1
        q.append([next_x, next_y, c + 1])
print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
memo = [[0 for _ in range(w)] for _ in range(h)]
step = [[1, 0], [-1, 0], [0, 1], [0, -1]]

memo[0][0] = 1
white = 0
for row in maze:
    white += row.count('.')

q = [[0, 0, 0]]

while q:
    x, y, c = q.pop(0)
    for a, b in step:
        next_x = x + a
        next_y = y + b
        if next_x == h - 1 and next_y == w - 1:
            print(white - (c + 2))
            exit()
        if next_x >= h or next_x < 0:
            continue
        if next_y >= w or next_y < 0:
            continue
        if memo[next_x][next_y] == 1:
            continue
        memo[next_x][next_y] = 1
        q.append([next_x, next_y, c + 1])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

count_w = 0
for i in range(H):
    for j in range(W):
        if M[i][j] == ".":
            count_w += 1
            
def bfs():
    que = deque()
    que.append((0,0))
    dx = [0,1,0,-1]
    dy = [-1,0,1,0]
    d = [[float("Inf")]*W for i in range(H)]
    d[0][0] = 0
    while que :
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if M[nx][ny] != "#" and d[nx][ny] == "Inf" and 0<=nx <H and 0 <= ny <W:
                que.append(M[nx][ny])
                d[nx][ny] = d[p[0]][p[1]]+1
    if d[nx][ny] == H+W-2:
        return True
    else:
        return False

if bfs:
    print(count_w -(H+W-2)-1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = [int(i) for i in input().split(' ')]

MAP = []
SUM = 0 
for i in range(H):
    tmp = list(input())
    SUM += tmp.count('#')
    MAP.append(tmp)

print(MAP,SUM)

S = [[0,0]]

while True:
    tmp = []
    for s in S:
        if not s[1] == W -1:
            if MAP[s[0]][s[1]+1] == '.':
                a = [s[0], s[1]+1]
                tmp.append(a)
        
        if not s[0] == H -1:
            if MAP[s[0]+1][s[1]] == '.':
                a = [s[0]+1, s[1]]
                tmp.append(a)
    S = tmp
    if len(s) == 0:
        print(-1)
        exit()

    if [H-1,W-1] in S:
        move = H + W - 1
        print(H*W - move - SUM)
        exit()

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

q = deque()
qq = deque()
q.append((1, 1))

i = 0
while len(q) > 0:
    while len(q) > 0:
        x, y = q.popleft()
        cost[x, y] = i
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx = x + dx
            ny = y + dy
            if S[nx, ny] == 0 and cost[nx, ny] == -1:
                qq.append((nx, ny))
    q = qq
    qq = deque()
    i += 1

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]
queue = deque()
dist = [[-1] * W for _ in range(H)]
queue.append((0, 0))
dist[0][0] = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
    i, j = queue.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
ans = 0
if dist[-1][-1] == -1:
    ans = -1
else:
    ans = sum(row.count('.') for row in s) - (dist[-1][-1] + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
def bfs(sy,sx,gy,gx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])

h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=h-1,w-1
bfs(sy,sx,gy,gx)
# print(visited)

c=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            c+=1
print(h*w-c-(visited[gy][gx]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import exit
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[False] * W for _ in range(H)]
whites_count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            whites_count += 1

que = deque()
que.append((0,0,1))
while len(que) > 0:
    h, w, dist = que.popleft()
    if h == H - 1 and w == W - 1:
        print(whites_count - dist)
        exit()
    if h + 1 < H and not done[h+1][w]:
        done[h+1][w] = True
        que.append((h+1, w, dist+1))
    if h - 1 >= 0 and not done[h-1][w]:
        done[h-1][w] = True
        que.append((h-1, w, dist+1))
    if w + 1 < W and not done[h][w+1]:
        done[h][w+1] = True
        que.append((h, w+1, dist+1))
    if w - 1 >= 0 and not done[h][w-1]:
        done[h][w-1] = True
        que.append((h, w-1, dist+1))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import exit
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[False] * W for _ in range(H)]
whites_count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            whites_count += 1

que = deque()
que.append((0,0,1))
while len(que) > 0:
    h, w, dist = que.popleft()
    if h == H - 1 and w == W - 1:
        print(whites_count - dist)
        exit()
    if h + 1 < H and not done[h+1][w]:
        done[h+1][w] = True
        que.append((h+1, w, dist+1))
    if w + 1 < W and not done[h][w+1]:
        done[h][w+1] = True
        que.append((h, w+1, dist+1))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import exit
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[False] * W for _ in range(H)]
whites_count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            whites_count += 1

que = deque()
que.append((0,0,1))
while True:
    h, w, dist = que.popleft()
    if h == H - 1 and w == W - 1:
        print(whites_count - dist)
        exit()
    if h + 1 < H and not done[h+1][w]:
        done[h+1][w] = True
        que.append((h+1, w, dist+1))
    if w + 1 < W and not done[h][w+1]:
        done[h][w+1] = True
        que.append((h, w+1, dist+1))

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import heapq
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    H, W = map(int, input().split())
    G = []
    for _ in range(H):
        G.append(list(input()[:-1]))
    
    C = [[INF] * W for _ in range(H)]
    C[0][0] = 1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == "#":
                cnt += 1
                continue
            if i + 1 < H:
                C[i+1][j] = min(C[i+1][j], C[i][j] + 1)
            if j + 1 < W:
                C[i][j+1] = min(C[i][j+1], C[i][j] + 1)

    if C[H-1][W-1] == INF:
        print(-1)
    else:
        print(H * W - (C[H-1][W-1] + cnt))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [input() for i in range(H)]
q = deque([(0,0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 1

while q:
    y, x = q.popleft()
    L = [(1,0), (-1,0), (0,1), (0,-1)]
    for i, j in L:
        if ((0 <= y+i <= H-1 and 0 <= x+j <= W-1)
            	and dist[y+i][x+j] == -1
            	and graph[y+i][x+j] == "."):
        	dist[y+i][x+j] = dist[y][x] + 1
        	q.append((y+i, x+j))

white = 0
for i in range(H):
    white += graph[i].count(".")
    
ans = white - dist[H-1][W-1]
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    h,w=MI()
    ss=[[c=="#" for c in SI()] for _ in range(h)]
    dist=[[-1]*w for _ in range(h)]
    q=deque()
    q.append((0,0))
    dist[0][0]=1
    while q:
        i,j=q.popleft()
        d=dist[i][j]
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if (ni,nj)==(h-1,w-1):
                ans = h * w - (d + 1) - sum(sum(row) for row in ss)
                print(ans)
                exit()
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if dist[ni][nj]!=-1:continue
            dist[ni][nj]=d+1
            q.append((ni,nj))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import heapq
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    H, W = map(int, input().split())
    G = []
    for _ in range(H):
        G.append(list(input()[:-1]))
    
    C = [[INF] * W for _ in range(H)]
    C[0][0] = 1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == "#":
                cnt += 1
                continue
            if i + 1 < H:
                C[i+1][j] = min(C[i+1][j], C[i][j] + 1)
            if j + 1 < W:
                C[i][j+1] = min(C[i][j+1], C[i][j] + 1)

    print(H * W - (C[H-1][W-1] + cnt))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    h,w=MI()
    ss=[[c=="#" for c in SI()] for _ in range(h)]
    dist=[[-1]*w for _ in range(h)]
    q=deque()
    q.append((0,0))
    dist[0][0]=1
    while q:
        i,j=q.popleft()
        d=dist[i][j]
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if (ni,nj)==(h-1,w-1):break
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if dist[ni][nj]!=-1:continue
            dist[ni][nj]=d+1
            q.append((ni,nj))
    else:
        print(-1)
        exit()
    ans=h*w-(d+1)-sum(sum(row) for row in ss)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque

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

    already_black = sum(row.count('#') for row in s)

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

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

    while dq:
        r, c = dq.popleft()
        if r == H - 1 and c == W - 1:
            break
        if r > 0 and s[r - 1][c] == '.' and not (~dist[r - 1][c] and dist[r - 1][c] <= dist[r][c] + 1):
            dist[r - 1][c] = dist[r][c] + 1
            dq.append((r - 1, c))
        if c > 0 and s[r][c - 1] == '.' and not (~dist[r][c - 1] and dist[r][c - 1] <= dist[r][c] + 1):
            dist[r][c - 1] = dist[r][c] + 1
            dq.append((r, c - 1))
        if r < H - 1 and s[r + 1][c] == '.' and not (~dist[r + 1][c] and dist[r + 1][c] <= dist[r][c] + 1):
            dist[r + 1][c] = dist[r][c] + 1
            dq.append((r + 1, c))
        if c < W - 1 and s[r][c + 1] == '.' and not (~dist[r][c + 1] and dist[r][c + 1] <= dist[r][c] + 1):
            dist[r][c + 1] = dist[r][c] + 1
            dq.append((r, c + 1))

    ans = H * W - (dist[H - 1][W - 1] + already_black)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    inf = 10 ** 9 + 7
    grid = [list(input()) for _ in range(h)]
    count = [[inf for _ in range(w)] for _ in range(h)]
    d = [[0, 1], [1, 0]]
    wall = 0
    count[0][0] = 1
    for g in grid:
        wall += g.count("#")
    s = deque([[0, 0]])
    while s:
        y, x = s.popleft()
        if grid[y][x] == ".":
            grid[y][x] = "#"
            for dy, dx in d:
                if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == ".":
                    count[y + dy][x + dx] = min(count[y + dy][x + dx], count[y][x] + 1)
                    s.append([y + dy, x + dx])
    print(h * w - count[-1][-1] - wall if count[-1][-1] != inf else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    inf = 10 ** 9 + 7
    grid = [list(input()) for _ in range(h)]
    count = [[inf for _ in range(w)] for _ in range(h)]
    d = [[0, 1], [1, 0]]
    wall = 0
    count[0][0] = 1
    for g in grid:
        wall += g.count("#")
    s = deque([[0, 0]])
    while s:
        y, x = s.pop()
        if grid[y][x] == ".":
            grid[y][x] = "#"
            for dy, dx in d:
                if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == ".":
                    count[y + dy][x + dx] = min(count[y + dy][x + dx], count[y][x] + 1)
                    s.append([y + dy, x + dx])
    print(h * w - count[-1][-1] - wall if count[-1][-1] != inf else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    from collections import deque

    def bfs(sy, sx):
        que = deque()
        dist = [[-1]*W for i in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if c[next_h][next_w] == '#':
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                que.append((next_h, next_w))
        return dist
    d = bfs(0, 0)
    seen = [True]*(d[H-1][W-1] + 1)
    ans = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                continue
            elif d[h][w] != -1 and d[h][w] <= d[-1][-1] and seen[d[h][w]]:
                seen[d[h][w]] = False
                continue
            else:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
sm = 0
for i in range(H): sm += S[i].count(".")
Q = dq([0])
dp = [H * W] * (H * W)
dp[0] = 1
d = [-1, 0, 1, 0]
while len(Q):
  p = Q.popleft()
  y = p // W
  x = p % W
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if dp[u * W + v] == H * W:
        dp[u * W + v] = dp[p] + 1
        Q.append(u * W + v)

if dp[-1] == H * W: print(-1)
else: print(sm - dp[-1])

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    h,w=MI()
    ss=[[c=="#" for c in SI()] for _ in range(h)]
    dist=[[-1]*w for _ in range(h)]
    q=deque()
    q.append((0,0))
    dist[0][0]=1
    while q:
        i,j=q.popleft()
        d=dist[i][j]
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if (ni,nj)==(h-1,w-1):break
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if dist[ni][nj]!=-1:continue
            dist[ni][nj]=d+1
            q.append((ni,nj))
    ans=h*w-(d+1)-sum(sum(row) for row in ss)
    print(ans)

main()

Submission status: Wrong Answer

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

ans = H*W - 2
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            ans -= 1
q = collections.deque()
q.append((0, 0, 0))
flag = False
while(q):
    x, y, d = q.popleft()
    if x == W-1 and y == H - 1:
        ans -= (d-1)
        flag = True
        break
    if y < H - 1 and s[y+1][x] == ".":
        q.append((x, y+1, d+1))
        s[y+1][x] = "#"
    if x < W - 1 and s[y][x+1] == ".":
        q.append((x+1, y, d+1))
        s[y][x+1] = "#"

if flag:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
sm = 0
for i in range(H): sm += S[i].count(".")
Q = dq([0])
dp = [H * W] * (H * W)
dp[0] = 1
while len(Q):
  p = Q.popleft()
  y = p // W
  x = p % W
  if (y + 1) in range(H):
    if S[y + 1][x] == "." and (dp[(y + 1) * W + x] == H * W):
      dp[(y + 1) * W + x] = dp[p] + 1
      Q.append((y + 1) * W + x)
  if (x + 1) in range(W):
    if S[y][x + 1] == "." and (dp[y * W + x + 1] == H * W):
      dp[y * W + x + 1] = dp[p] + 1
      Q.append(y * W + x + 1)

if dp[-1] == H * W: print(-1)
else: print(sm - dp[-1])

Submission status: Wrong Answer

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

ans = H*W - 2
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            ans -= 1
q = collections.deque()
q.append((0, 0, 0))
while(q):
    x, y, d = q.popleft()
    if x == W-1 and y == H - 1:
        ans -= (d-1)
        break
    if y < H - 1 and s[y+1][x] == ".":
        q.append((x, y+1, d+1))
        s[y+1][x] = "#"
    if x < W - 1 and s[y][x+1] == ".":
        q.append((x+1, y, d+1))
        s[y][x+1] = "#"

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    inf = 10 ** 9 + 7
    grid = [list(input()) for _ in range(h)]
    count = [[inf for _ in range(w)] for _ in range(h)]
    d = [[0, 1], [1, 0]]
    wall = 0
    count[0][0] = 1
    for g in grid:
        wall += g.count("#")
    s = deque([[0, 0]])
    while s:
        y, x = s.pop()
        if grid[y][x] == ".":
            for dy, dx in d:
                if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == ".":
                    count[y + dy][x + dx] = min(count[y + dy][x + dx], count[y][x] + 1)
                    s.append([y + dy, x + dx])
    print(h * w - count[-1][-1] - wall if count[-1][-1] != inf else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
sm = 0
for i in range(H): sm += S[i].count(".")
Q = dq([0])
dp = [H * W] * (H * W)
dp[0] = 1
while len(Q):
  p = Q.popleft()
  y = p // W
  x = p % W
  if (y + 1) in range(H):
    if S[y + 1][x] == ".":
      dp[(y + 1) * W + x] = dp[p] + 1
      Q.append((y + 1) * W + x)
  if (x + 1) in range(W):
    if S[y][x + 1] == ".":
      dp[y * W + x + 1] = dp[p] + 1
      Q.append(y * W + x + 1)

if dp[-1] == H * W: print(-1)
else: print(sm - dp[-1])

Submission status: Wrong Answer

Solution code:
import collections
import itertools

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


def adjacent_squares(i, j):
    return [
        (i + di, j + dj)
        for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]
        if i + di in range(H) and j + dj in range(W)
    ]


def distance_to_goal():
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[0][0] = 0
    queue = collections.deque([(0, 0)])

    d = 0
    while queue:
        i, j = queue.popleft()
        to_visit = [(k, l) for k, l in adjacent_squares(i, j) if distances[k][l] == -1]
        for k, l in to_visit:
            if (k, l) == (H - 1, W - 1):
                return distances[i][j] + 1

            distances[k][l] = distances[i][j] + 1
            queue.append((k, l))

    return -1


def black_squares():
    return sum(1 for c in itertools.chain.from_iterable(s) if c == "#")


distance = distance_to_goal()
if distance == -1:
    print(-1)
else:
    print(H * W - (distance + 1) - black_squares())

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((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[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    if d[gy][gx] != float("inf"):
        return d[gy][gx]
    else:
        return -1
h, w = map(int, input().split())
sy, sx = 0, 0
gy, gx = h - 1, w - 1
s = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            black += 1
print(h * w - bfs() - black - 1)