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=[list(input()) for _ in range(H)]
dflt_cnt=0
for i in range(H):
    dflt_cnt+=s[i].count(".")
que=deque([(0,0)])
step=[[-1]*W for _ in range(H)]
step[0][0]=0
move_h=[1,0,-1,0]
move_w=[0,1,0,-1]
cnt=1
while que:
    v=que.popleft()
    if v[0]==H-1 and v[1]==W-1:
        cnt+=step[H-1][W-1]
        break
    for i in range(4):
        next_h=v[0]+move_h[i]
        next_w=v[1]+move_w[i]
        if 0<=next_h<H and 0<=next_w<W and s[next_h][next_w]=="." and step[next_h][next_w]==-1:
            que.append((next_h,next_w))
            step[next_h][next_w]=step[v[0]][v[1]]+1
print(dflt_cnt-cnt)

Submission status: Wrong Answer

Solution code:
import sys
import copy
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def bfs():
    d = [[-1] * w for _ in range(h)]

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

    while que:
        x, y = que.popleft()
        if x == h - 1 and y == w - 1:
            break
        for dx, dy in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == -1:
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1

    return d[h - 1][w - 1]

h, w = na()
maze = [list(input()) for _ in range(h)]
ct = 0
for i in range(h):
    ct += maze[i].count("#")
print(h * w - bfs() - 1 - ct)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
board = [0]*(H+2)
board[0] = [1]*(W+2)
total = 0
for i in range(1,H+1):
    board[i] = [1]+list(1 if c == '#'else 0 for c in input())+[1]
    total += sum(1 for c in board[i] if c == 0)
board[H+1] = [1]*(W+2)

D = [[H*W] * (W+2) for _ in range(H+2)]
D[1][1] = 0
from heapq import heappush, heappop

q = [(0, (1, 1))]

while q:
    d, (i, j) = heappop(q)
    alt = d + 1

    for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if board[x][y] == 0:
            if D[x][y] > alt:
                D[x][y] = alt
                heappush(q, (alt, (x, y)))

#for r in range(H+2): print(*[board[r][c] for c in range(W+2)])
#for r in range(H+2): print(*[D[r][c] for c in range(W+2)])
print(total - D[H][W] - 1)

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 1
 
queue = [(0, 0)]
counter = 0

while not queue == []:

    if counter >= 10000:
        print(-1)
        exit()

    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
if num_step != INF:
    ans = R*C - black - num_step[R-1][C-1]
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 1
 
queue = [(0, 0)]
counter = 0

while not queue == []:
    counter += 1

    if counter >= 10000:
        print(-1)
        exit()

    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
ans = R*C - black - num_step[R-1][C-1]
print(ans)

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 0
 
queue = [(0, 0)]
counter = 0

while not queue == []:
    counter += 1

    if counter >= 10000:
        print(-1)
        exit()

    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
ans = R*C - black - num_step[R-1][C-1]-1
print(ans)

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 0
 
queue = [(0, 0)]
counter = 0

while not queue == []:
    counter += 1

    if counter >= 2600:
        print(-1)
        exit()

    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
ans = R*C - black - num_step[R-1][C-1]-1
print(ans)

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("#")

INF = R * C + 1
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '#':
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 1
 
queue = [(0, 0)]
 
while not queue == []:
    h = queue.pop(0) # here
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
ans = R*C - black - num_step[R-1][C-1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
grid=[list(input()) for _ in range(h)]
dist=[[-1]*w for _ in range(h)]
dist[0][0]=0
Q=[(0,0)]
tile=h*w
cnt=0

white=0
for i in range(h):
    white+=grid[i].count(".")

while Q:
    Q_alt=[]
    for q in Q:
        if grid[q[1]][q[0]]!="#":
            if q[0]!=0:
                if grid[q[1]][q[0]-1]!="#" and dist[q[1]][q[0]-1]==-1:
                    dist[q[1]][q[0]-1]=cnt+1
                    Q_alt.append((q[0]-1,q[1]))
            if q[0]!=w-1:
                if grid[q[1]][q[0]+1]!="#" and dist[q[1]][q[0]+1]==-1:
                    dist[q[1]][q[0]+1]=cnt+1
                    Q_alt.append((q[0]+1,q[1]))
            if q[1]!=0:
                if grid[q[1]-1][q[0]]!="#" and dist[q[1]-1][q[0]]==-1:
                    dist[q[1]-1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]-1))
            if q[1]!=h-1:
                if grid[q[1]+1][q[0]]!="#" and dist[q[1]+1][q[0]]==-1:
                    dist[q[1]+1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]+1))
    cnt+=1
    Q=Q_alt

print(white-dist[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().strip().split(' '))
s = [0] * h
num = 0
for i in range(h):
  s[i] = input()
  num = num + s[i].count('.')
change = 0
slist = [(0,0)]
road = False
while slist != []:
  change = change + 1
  for k in range(len(slist)):
    (i, j) = slist.pop(0)
    if (i+1, j+1) == (h, w):
      print(num-change)
      road = True
      slist = []
      break
    if i+1 < h and s[i+1][j] == ".":
      slist.append((i+1,j))
    if j+1 < w and s[i][j+1] == ".":
      slist.append((i,j+1))
if road == False:
  print(-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
G = [[-1]*W for _ in range(H)]
G[0][0] = 1
q = [(0, 0)]

while q :
    i, j = q[0]
    q = q[1:]
    for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
        t, u = i+x, j+y
        if 0<=t<H and 0<=u<W and G[t][u]<0 and S[t][u]==".":
            G[t][u] = 1+G[i][j]
            q.append((t, u))

d = sum(s.count(".") for s in S)
print(d-G[-1][-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
G = [[-1]*W for _ in range(H)]
G[0][0] = 1
q = [(0, 0)]

while q :
    i, j = q[0]
    q = q[1:]
    if S[i][j] == "." :
        for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
            t, u = i+x, j+y
            if 0<=t<H and 0<=u<W and G[t][u]<0 :
                G[t][u] = 1+G[i][j]
                q.append((t, u))

d = sum(s.count(".") for s in S)
a = d-G[-1][-1]
print(-1 if a==-float("inf") else a)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

for p, q in product(range(H), range(W)) :
    for i, j in product(range(p, H), range(q, W)) :
        if S[i][j] == "." :
            for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
                if 0 <= i+x < H and 0<= j+y < W :
                    G[i][j] = min(1+G[i+x][j+y], G[i][j])

d = sum(s.count(".") for s in S)
a = d-G[-1][-1]
print(-1 if a==-float("inf") else a)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

for _ in range(H*W) :
    for i, j in product(range(H), range(W)) :
        if S[i][j] == "." :
            for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
                try :
                    G[i][j] = min(1+G[i+x][j+y], G[i][j])
                except : pass

d = sum(s.count(".") for s in S)
print(d-G[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

white = sum(s.count(".") for s in S)

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

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    visited[h][w] = True

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] != "#" and not visited[nh][nw]:
            Q.append((nh, nw, count + 1))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

black = sum(s.count("#") for s in S)

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

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(H * W - black - count)
        quit()

    visited[h][w] = True

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] != "#" and not visited[nh][nw]:
            Q.append((nh, nw, count + 1))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
cnt[0][0] = 0

def bfs():
    q = deque([(0, 0)])
    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] != '#' and cnt[y+dy][x+dx] == float('inf'):
                q.append([y+dy, x+dx])
                cnt[y+dy][x+dx] = cnt[y][x] + 1
    
bfs()
short_path = cnt[h-1][w-1]
ans = 0
ans += short_path + 1
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            ans += 1

ans = h*w - ans 
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
cnt[0][0] = 0

def bfs():
    q = deque([(0, 0)])
    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            if 0 <= y+dy < h and 0 <= x+dx < w and cnt[y+dy][x+dx] == float('inf'):
                q.append([y+dy, x+dx])
                cnt[y+dy][x+dx] = cnt[y][x] + 1
    
bfs()
short_path = cnt[h-1][w-1]
ans = 0
ans += short_path + 1
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            ans += 1

ans = h*w - ans 
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, a = IR(2)
    n %= 500
    if a >= n:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    _ = II()
    a = LI()
    a.sort(reverse=True)
    op = 0
    ans = 0
    for ai in a:
        ans += -ai * op or ai
        op ^= 1
    print(ans)
    return

#C
def C():
    c = LIR(3)
    for x in range(c[0][0] + 1):
        b = (c[0][0] - x, c[0][1] - x, c[0][2] - x)
        if (c[1][0] - b[0]) == (c[1][1] - b[1]) == (c[1][2] - b[2]):
            if (c[2][0] - b[0]) == (c[2][1] - b[1]) == (c[2][2] - b[2]):
                print("Yes")
                return
    print("No")
    return
#D
def D():
    move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    h, w = LI()
    s = SR(h)
    q = deque([(0, 0, 1)])
    ans = h * w
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                ans -= 1
    check = [[True] * w for _ in range(h)]
    while q:
        x, y, tern = q.pop()
        for mx, my in move:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if s[my][mx] == "." and check[my][mx]:
                    check[my][mx] = False
                    if my == h - 1 and mx == w - 1:
                        print(ans - tern - 1)
                        return
                    q.appendleft((mx, my, tern + 1))


    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, a = IR(2)
    n %= 500
    if a >= n:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    _ = II()
    a = LI()
    a.sort(reverse=True)
    op = 0
    ans = 0
    for ai in a:
        ans += -ai * op or ai
        op ^= 1
    print(ans)
    return

#C
def C():
    c = LIR(3)
    for x in range(c[0][0] + 1):
        b = (c[0][0] - x, c[0][1] - x, c[0][2] - x)
        if (c[1][0] - b[0]) == (c[1][1] - b[1]) == (c[1][2] - b[2]):
            if (c[2][0] - b[0]) == (c[2][1] - b[1]) == (c[2][2] - b[2]):
                print("Yes")
                return
    print("No")
    return
#D
def D():
    move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    h, w = LI()
    s = SR(h)
    q = deque([(0, 0, 1)])
    ans = h * w
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                ans -= 1
    while q:
        x, y, tern = q.pop()
        for mx, my in move:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if s[my][mx] == ".":
                    if my == h - 1 and mx == w - 1:
                        print(ans - tern - 1)
                        return
                    q.appendleft((mx, my, tern + 1))


    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (0, 1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (0, 1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (0, 1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def bfs() -> None:
    q = [(0, 0)]
    while len(q):
        x, y = q.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (0, 1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def dfs(x: int, y: int, cur: int) -> None:
    D[x][y] = cur
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy  # next x, y
        if nx < H and ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
            dfs(nx, ny, cur + 1)


def main():
    global H, W, S, D, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    D = [[0] * W for _ in range(H)]  # distance
    dxy = [(1, 0), (0, 1)]
    dfs(0, 0, 1)
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def dfs(x: int, y: int, cur: int) -> None:
    C[x][y] = cur
    if x + 1 < H and S[x + 1][y] == "." and C[x + 1][y] == 0:
        dfs(x + 1, y, cur + 1)
    if y + 1 < W and S[x][y + 1] == "." and C[x][y + 1] == 0:
        dfs(x, y + 1, cur + 1)

def main():
    global H, W, S, C
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    C = [[0] * W for _ in range(H)]  # count
    dfs(0, 0, 1)
    white = sum(s.count(".") for s in S)
    x = C[-1][-1]
    if x:
        ans = white - x
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def dfs(x: int, y: int, cur: int) -> None:
    C[x][y] = cur
    if x + 1 < H and S[x + 1][y] == "." and C[x + 1][y] == 0:
        dfs(x + 1, y, cur + 1)
    if y + 1 < W and S[x][y + 1] == "." and C[x][y + 1] == 0:
        dfs(x, y + 1, cur + 1)

def main():
    global H, W, S, C
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    C = [[0] * W for _ in range(H)]  # count
    dfs(0, 0, 1)
    black = sum(s.count("#") for s in S)
    x = C[-1][-1]
    if x:
        ans = H * W - black - x
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def bfs(S,H,W):
    stk = [(0,0)]
    cnt = 0
    seen = set()
    while True:
        nxt = []
        while stk:
            h,w = stk.pop()
            if(not (0<=h<H and 0<=w<W) or S[h][w]=='#' or (h,w) in seen):
                continue
            elif(h==H-1 and w==W-1):
                break
            seen.add((h,w))
            li=[(1,0),(-1,0),(0,-1),(0,1)]
            for x,y in li:
                nxt.append((h+y,w+x))
        else:
            stk = nxt
            cnt += 1
            if(cnt>H+W+10):return -1
            continue
        break
    return cnt

H,W = [int(x) for x in input().split()]
S = [list(input()) for _ in range(H)]
wht = 0
for s in S:
    wht += s.count('.')
rt = bfs(S,H,W)
if(rt>=0):
    print(wht-(rt+1))
else:
    print(rt)

Submission status: Wrong Answer

Solution code:
def bfs(S,H,W):
    stk = [(0,0)]
    cnt = 0
    seen = set()
    while True:
        nxt = []
        while stk:
            h,w = stk.pop()
            if(not (0<=h<H and 0<=w<W) or S[h][w]=='#' or (h,w) in seen):
                continue
            elif(h==H-1 and w==W-1):
                break
            seen.add((h,w))
            li=[(1,0),(-1,0),(0,-1),(0,1)]
            for x,y in li:
                nxt.append((h+y,w+x))
        else:
            stk = nxt
            cnt += 1
            if(cnt>H+W+1):return -1
            continue
        break
    return cnt

H,W = [int(x) for x in input().split()]
S = [list(input()) for _ in range(H)]
wht = 0
for s in S:
    wht += s.count('.')
rt = bfs(S,H,W)
if(rt>0):
    print(wht-(rt+1))
else:
    print(rt)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
cnt = 0
INF = 10**4
dp = [[INF] * (W) for _ in range(H)]
dp[0][0] = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == '.':
      cnt += 1
dy = [1,0,-1,0]
dx = [0,1,0,-1]
que = deque([])
que.append((0, 0))
while len(que) > 0:
  cy, cx = que.popleft()
  if cy == H-1 and cx == W-1:
    break
  for i in range(4):
    ny, nx = cy+dy[i], cx+dx[i]
    if ny >= 0 and ny <= H-1 and nx >= 0 and nx <= W-1:
      if dp[ny][nx] == INF and grid[ny][nx] == '.':
        dp[ny][nx] = dp[cy][cx] + 1
        que.append((ny, nx))
print(cnt-dp[H-1][W-1]-1)