Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    s = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    bc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                bc += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and [s] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print((h * w - mt - 1) - bc if fq[h-1, w-1] != 0 and s[0][0] != "#" else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    s = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    bc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                bc += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and [s] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print((h * w - mt - 1) - bc if fq[h-1,w-1] != 0 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    s = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    bc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                bc += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and [s] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print((h * w - mt - 1) - bc)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

M=["."]*H
C=[[0]*50 for i in range(50)]
L=[[0,0,0] for i in range(10**5)]

s=0
for i in range(H):
    t=list(input())
    s+=t.count("#")
    M[i]=t


c=0
i=0
P=0
while(True):
    x=L[i][0]
    y=L[i][1]
    p=L[i][2]
    if(i>c):
        print(-1)
        break
    
    if((H-1)==y and (W-1)==x):
        print(H*W-s-p-1)
        exit()
    if(y>1):
        if(M[y-1][x]=="." and C[y-1][x]==0):    
            c+=1
            L[c][0]=x
            L[c][1]=y-1
            L[c][2]=p+1
            C[y-1][x]=1
    if(x<(W-1)):
        if(M[y][x+1]=="." and C[y][x+1]==0):
            c+=1
            L[c][0]=x+1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x+1]=1
    if(y<(H-1)):
        if(M[y+1][x]=="." and C[y+1][x]==0):
            c+=1
            L[c][0]=x
            L[c][1]=y+1
            L[c][2]=p+1
            C[y+1][x]=1
    if(x>1):
       if(M[y][x-1]=="." and C[y][x-1]==0):
            c+=1
            L[c][0]=x-1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x-1]=1
    i+=1

print()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())

inf = 1009
grid = np.zeros((h + 2, w + 2), dtype=int)
for i in range(h):
    grid[i + 1][1:-1] = np.array([1 if j == "." else 0 for j in input()])
white = grid.sum()

cost = np.ones((h+2, w+2), dtype=int)*inf
cost[1][1] = 1

d = ((1, 0), (0, 1), (-1, 0), (0, -1))
to = deque([(1, 1)])
while to:
    x, y = to.popleft()
    c = cost[x][y]
    for xi, yi in d:
        nx = x + xi
        ny = y + yi
        if not grid[nx][ny]:
            continue
        to.append((nx, ny))
        cost[nx][ny] = min(cost[nx][ny], c+1)
        grid[nx][ny] = 0

if cost[-1][-1] == inf:
    ans = -1
else:
    ans = white-cost[-2][-2]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())

inf = 1009
grid = np.zeros((h + 2, w + 2), dtype=int)
for i in range(h):
    grid[i + 1][1:-1] = np.array([1 if j == "." else 0 for j in input()])
white = grid.sum()

cost = np.ones((h+2, w+2), dtype=int)*inf
cost[1][1] = 1

d = ((1, 0), (0, 1), (-1, 0), (0, -1))
to = deque([(1, 1)])
while to:
    x, y = to.popleft()
    c = cost[x][y]
    for xi, yi in d:
        nx = x + xi
        ny = y + yi
        if not grid[nx][ny]:
            continue
        to.append((nx, ny))
        cost[nx][ny] = min(cost[nx][ny], c+1)
        grid[nx][ny] = 0

ans = white-cost[-2][-2]
print(ans)

Submission status: Wrong Answer

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

H, W = map(int, input().split())
M = [["#" for _ in range(W+2)]]+[list("#"+input()+"#") for _ in range(H)]+[["#" for _ in range(W+2)]]
seen = deque((1, 1)) #x, y
q = deque([(1, 1, 0)]) #x, y, d
depth = -1
goal = False
wall = 0
for m in M[1:H+1]:
  for b in m[1:W+1]:
    if b == "#":
      wall += 1
while q:
  x, y, d = q.popleft()
  if x == W and y == H:
    depth = d
    goal = True
    break
  for dx, dy in zip((0, 0, -1, 1), (1, -1, 0, 0)):
    if x + dx != "#" and y +dy != "#" and not (x+dx, y+dy) in seen:
      seen.append((x+dx, y+dy))
      q.append((x+dx, y+dy, d+1))

if goal:
  print(W*H-wall-(depth+1))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = list(list(input())for i in range(h))
cntng = 0
for i in range(h):
    cntng+= s[i].count("#")


start = (0,0) 
goal = (h-1,w-1)
vec = ((1,0),(0,1),(-1,0),(0,-1))

stack = [start]
move = 0

while stack:
    next = []
    move+=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            
            if ty>h-1 or tx>w-1 or ty<0 or tx<0:continue
            if s[ty][tx] == ".":
                s[ty][tx] = move
                next.append((ty,tx))
    stack = next
         
    stack = next
    if goal in stack:
        break
ans = max(0,h*w - (move+1)-cntng)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = list(list(input())for i in range(h))
cntng = 0
for i in range(h):
    cntng+= s[i].count("#")


start = (0,0) 
goal = (h-1,w-1)
vec = ((1,0),(0,1),(-1,0),(0,-1))

stack = [start]
move = 0

while stack:
    next = []
    move+=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            
            if ty>h-1 or tx>w-1 or ty<0 or tx<0:continue
            if s[ty][tx] == ".":
                s[ty][tx] = move
                next.append((ty,tx))
    stack = next
         
    stack = next
    if goal in stack:
        break
ans = h*w - (move+1)-cntng
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))

    Q = deque([(0, 0)])
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        h, w = Q.popleft()

        if h == H - 1 and w == W - 1:
            break

        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]

            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                Q.append((nh,nw))

    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

    print(cnt - d[H-1][W-1] - 1)

         

    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    t=0
    b=0
    l=0
    r=0
    cntw=0
    si=[[-1 for _ in range(w)]for _ in range(h)]
    before=0
    after=0
    # print(si)
    si[0][0]=0

    tempw=0

    # print(si)
    for i in range(0,h):
        for j in range(0,w):
            if s[i][j]=='.':
                tempw+=1


    before=1
    temps=0
    flag=1
    while flag==1:
        flag=0
        for i in range(0,h):
            for j in range(0,w):

                if i==0 and j ==0:
                    j=1

                if s[i][j]=='.' :
                    cntw+=1
                    if i==0 or s[i-1][j]=='#' or si[i-1][j]<0:
                        t=10000
                    else:
                        t=si[i-1][j]
                    if j ==0 or s[i][j-1]=='#' or si[i][j-1]<0:
                        # print(i)
                        # print(j)
                        # print(s[i][j-1])
                        # print(si[i][j-1])
                        l=10000
                    else:
                        l=si[i][j-1]
                    if i==h-1 or s[i+1][j] =='#' or si[i+1][j]<0:
                        b=10000
                    else:
                        b=si[i+1][j]
                    if j==w-1 or s[i][j+1]=='#' or si[i][j+1]<0:
                        r=10000
                    else:
                        r=si[i][j+1]
                    temps=min(t,l,b,r)+1
                    # print(temps)
                    if temps<si[i][j] or si[i][j]==-1:
                        si[i][j]=temps
                        flag=1



    if si[-1][-1]<0:
        print(-1)
        return
    else:
        print(tempw-si[-1][-1]-1)





if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

    t=0
    b=0
    l=0
    r=0
    cntw=0
    si=[[-1 for _ in range(w)]for _ in range(h)]
    before=0
    after=0
    # print(si)
    si[0][0]=0

    tempw=0

    # print(si)
    for i in range(0,h):
        for j in range(0,w):
            if s[i][j]=='.':
                tempw+=1


    before=1
    temps=0
    flag=1
    while flag==1:
        flag=0
        for i in range(0,h):
            for j in range(0,w):

                if i==0 and j ==0:
                    j=1

                if s[i][j]=='.' :
                    cntw+=1
                    if i==0 or s[i-1][j]=='#' or si[i-1][j]<0:
                        t=10000
                    else:
                        t=si[i-1][j]
                    if j ==0 or s[i][j-1]=='#' or si[i][j-1]<0:
                        # print(i)
                        # print(j)
                        # print(s[i][j-1])
                        # print(si[i][j-1])
                        l=10000
                    else:
                        l=si[i][j-1]
                    if i==h-1 or s[i+1][j] =='#' or si[i+1][j]<0:
                        b=10000
                    else:
                        b=si[i+1][j]
                    if j==w-1 or s[i][j+1]=='#' or si[i][j+1]<0:
                        r=10000
                    else:
                        r=si[i][j+1]
                    temps=min(t,l,b,r)+1
                    # print(temps)
                    if temps<si[i][j] or si[i][j]==-1:
                        si[i][j]=temps
                        flag=1



    if si[-1][-1]==-1:
        print(-1)
        return
    else:
        print(tempw-si[-1][-1]-1)





if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = 10**5
d = [[10**5] * W for _ in range(H)]
d[0][0] = 0

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

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

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

    if y == H-1 and x == W-1:
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            d[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

if d[H-1][W-1] == INF:
    print(-1)
else:
    black = 0
    for a in maze:
        black += a.count('#')
    
    print(H * W - black - d[H-1][W-1] - 1)

Submission status: Wrong Answer

Solution code:
import sys
import copy
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
masu = [0 for h in range(H+2)]
masu[0] = ['#' for _ in range(W+2)]
masu[H+1] = ['#' for _ in range(W+2)]
init = 0
for h in range(1, H + 1):
    w = list(input().strip())
    init += w.count('#')
    masu[h] = ['#'] + w + ['#']

def dfs(h, w, c, masu):
    if w == W and h == H:
        return c
    elif masu[h][w] == '#':
        return 10 ** 9 + 7
    #print('w = {}, h = {}, c = {}'.format(w, h, c))
    ans = 10 ** 9 + 7
    masu_ = copy.deepcopy(masu)
    masu_[h][w] = '#'
    for ww, hh in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ans = min(ans, dfs(h+hh, w+ww, c+1, copy.deepcopy(masu_)))
        if ans != 10 ** 9 + 7:
            break
    return ans
   
ans = dfs(1, 1, 1, copy.deepcopy(masu))
if ans == 10 ** 9 + 7:
    print(-1)
else:
    print(H*W-ans-init)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count(".")
    s.append(temp)

d=[[0,0]]
step=[[-1,0],[0,-1],[1,0],[0,1]]
c={(0,0):1}

while d:
    h0,w0=d.pop()
    s[h0][w0]="#"
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="#":
            continue
        if h==H-1 and w==W-1:
            ans = cnt - c[(h0,w0)]-1
            print(ans)
            exit()
        c[(h,w)]=c[(h0,w0)]+1
        d.append([h,w])
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count("#")
    s.append(temp)

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

while d:
    h0,w0,c=d.pop()
    s[h0][w0]="#"
    c+=1
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="#":
            continue
        if h==H-1 and w==W-1:
            c+=1
            ans = H * W - cnt - c
            print(ans)
            exit()
        d.append([h,w,c])
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# メモ配列
INF = 10**7
memo = [[INF]*w for i in range(h)]

wcnt = 0
for i in p:
    for j in i:
        if j == '.':
            wcnt+=1

# 最短経路格納用
root = 0

# 幅探索用キュー初期化
q = deque()
q.append((0, 0))
memo[0][0]  = 0

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

ans = -1
for i in range(INF):
    # キューが空なら終了
    if len(q) == 0:
        break
        
    # キューから一つ取り出す
    x, y = map(int, q.pop())
    
    # ゴールなら終了
    if x == w-1 and y == h-1:
        ans = memo[y][x]
        break
        
        
    # 4方向の距離を確定して、エンキューする
    for j in range(4):
        nx, ny = x+vx[j], y+vy[j]
        
        # エリア外 or 探索済み or 黒色なら探索しない
        if nx < 0 or w <= nx or ny < 0 or h <= ny or memo[ny][nx] != INF or p[ny][nx] == '#':
            continue
            
        memo[ny][nx] = memo[y][x]+1
        q.append((nx, ny))

if p[0][0] == '#' or p[h-1][w-1] == '#' or ans == -1:
    print(ans)
else:
    print(wcnt-ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# メモ配列
INF = 10**5
memo = [[INF]*w for i in range(h)]

wcnt = 0
for i in p:
    for j in i:
        if j == '.':
            wcnt+=1

# 最短経路格納用
root = 0

# 幅探索用キュー初期化
q = deque()
q.append((0, 0))
memo[0][0]  = 0

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

ans = -1
for i in range(INF):
    # キューが空なら終了
    if len(q) == 0:
        break
        
    # キューから一つ取り出す
    x, y = map(int, q.pop())
    
    # ゴールなら終了
    if x == w-1 and y == h-1:
        ans = memo[y][x]
        break
        
        
    # 4方向の距離を確定して、エンキューする
    for j in range(4):
        nx, ny = x+vx[j], y+vy[j]
        
        # エリア外 or 探索済み or 黒色なら探索しない
        if nx < 0 or w <= nx or ny < 0 or h <= ny or memo[ny][nx] != INF or p[ny][nx] == '#':
            continue
            
        memo[ny][nx] = memo[y][x]+1
        q.append((nx, ny))

if p[0][0] == '#' or p[h-1][w-1] == '#' or ans == -1:
    print(ans)
else:
    print(wcnt-ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# メモ配列
INF = 10**5
memo = [[INF]*w for i in range(h)]

wcnt = 0
for i in p:
    for j in i:
        if j == '.':
            wcnt+=1

# 最短経路格納用
root = 0

# 幅探索用キュー初期化
q = deque()
q.append((0, 0))
memo[0][0]  = 0

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

ans = -1
for i in range(INF):
    # キューが空なら終了
    if len(q) == 0:
        break
        
    # キューから一つ取り出す
    x, y = map(int, q.pop())
    
    # ゴールなら終了
    if x == w-1 and y == h-1:
        ans = memo[y][x]
        break
        
        
    # 4方向の距離を確定して、エンキューする
    for j in range(4):
        nx, ny = x+vx[j], y+vy[j]
        
        # エリア外 or 探索済み or 黒色なら探索しない
        if nx < 0 or w <= nx or ny < 0 or h <= ny or memo[ny][nx] != INF or p[ny][nx] == '#':
            continue
            
        memo[ny][nx] = memo[y][x]+1
        q.append((nx, ny))

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

Submission status: Wrong Answer

Solution code:
import queue

def bfs(h, w, maps):
    distance = [[float("inf")] * w for _ in range(h)]
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

    distance[0][0] = 0
    pri_queue = queue.Queue()
    pri_queue.put((0, 0))
    while True:
        if pri_queue.empty():
            break
        p = pri_queue.get()
        if p[0] == h - 1 and p[1] == w - 1:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] != "#" and distance[nx][ny] == float("inf"):
                pri_queue.put((nx, ny))
                distance[nx][ny] = distance[p[0]][p[1]] + 1

    if distance[h - 1][w - 1] != 'inf':
        return distance[h - 1][w - 1]

    else:
        return -1

h, w = map(int, input().split())
maps = [list(input()) for _ in range(h)]
wall = 0

for i in maps:
    for j in range(w):
        if i[j] == "#":
            wall += 1

min_dis = bfs(h, w, maps)

print(h * w - (wall + min_dis + 1) if min_dis != -1 else -1)

Submission status: Wrong Answer

Solution code:
import queue

def bfs(h, w, maps):
    distance = [[float("inf")] * w for _ in range(h)]
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

    distance[0][0] = 0
    pri_queue = queue.Queue()
    pri_queue.put((0, 0))
    while True:
        if pri_queue.empty():
            break
        p = pri_queue.get()
        if p[0] == h - 1 and p[1] == w - 1:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] != "#" and distance[nx][ny] == float("inf"):
                pri_queue.put((nx, ny))
                distance[nx][ny] = distance[p[0]][p[1]] + 1

    if distance[h - 1][w - 1] != 'inf':
        return distance[h - 1][w - 1]

    else:
        return -1

h, w = map(int, input().split())
maps = [list(input()) for _ in range(h)]
wall = 0

for i in maps:
    for j in range(w):
        if i[j] == "#":
            wall += 1

min_dis = bfs(h, w, maps)

print(h * w - (wall + min_dis + 1))

Submission status: Wrong Answer

Solution code:
# ABC088
from collections import deque
import copy
# 入力
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
field_original = copy.deepcopy(field)

# 4方向の移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# BFSのためのデータ構造
dist = [[-1] * W for _ in range(H)]
que_x = deque()
que_y = deque()

# 探索中に各マスはどこからきたのかを表す配列
prev_x = [[-1] * W for _ in range(H)]
prev_y = [[-1] * W for _ in range(H)]

# 初期条件(スタート地点を0にする)
dist[0][0] = 0
que_x.append(0)
que_y.append(0)

# BFS開始
while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
            continue
        if field[nx][ny] == "#":     # 壁はスルー
            continue
        if dist[nx][ny] == -1:          # まだ見ていない時
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1   # 距離の更新
            prev_x[nx][ny] = x      # どの頂点から伝播してきたかを 縦 方向の座標をメモ
            prev_y[nx][ny] = y      # どの頂点から伝播してきたかを 横 方向の座標をメモ
x = H - 1
y = W - 1
##print(dist[H-1][W-1])
while x != -1 and y != -1:
    field[x][y] = "o"

    # 前の頂点へいく
    px = prev_x[x][y]
    py = prev_y[x][y]
    x, y = px, py
##print(field)
ans = 0
for i in range(H):
    for k in range(W):
        if field[i][k] == field_original[i][k] == ".":
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>-1 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [0] * H
shortest_path = [[-1] * W for i in range(H)]
sharp_count = 0
for i in range(H):
    S[i] = input()
    sharp_count += S[i].count("#")

que_list = deque()
que_list.append((0, 0))
shortest_path[0][0] = 0
while que_list:
    q = que_list.popleft()
    if H > q[0]-1 >= 0 and W > q[1] >= 0:
        if S[q[0]-1][q[1]] != "#" and shortest_path[q[0]-1][q[1]] == -1:
            que_list.append((q[0]-1,q[1]))
            shortest_path[q[0]-1][q[1]] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]+1 >= 0:
        if S[q[0]][q[1]+1] != "#" and shortest_path[q[0]][q[1]+1] == -1:
            que_list.append((q[0],q[1]+1))
            shortest_path[q[0]][q[1]+1] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]-1 >= 0:
        if S[q[0]][q[1]-1] != "#" and shortest_path[q[0]][q[1]-1] == -1:
            que_list.append((q[0],q[1]-1))
            shortest_path[q[0]][q[1]-1] = shortest_path[q[0]][q[1]]+1
    if H > q[0]+1 >= 0 and W > q[1] >= 0:
        if S[q[0]+1][q[1]] != "#" and shortest_path[q[0]+1][q[1]] == -1:
            que_list.append((q[0]+1,q[1]))
            shortest_path[q[0]+1][q[1]] = shortest_path[q[0]][q[1]]+1

print(H*W - (shortest_path[H-1][W-1]+1+sharp_count))

Submission status: Wrong Answer

Solution code:
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "#":
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = queue.Queue()
    q.put([0,0])
    step = mas.copy()
    for i in range(h):
        for j in range(w):
            step[i][j] = -1
    step[0][0] = 0
    while not q.empty():
        s = q.get()
        if s[0] == h-1 and s[1] == w-1:
            break
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and mas[nx][ny] !="#" and step[nx][ny] == -1):
                q.put([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1
    return step[h-1][w-1]

least = bfs()
if(least == -1):
    print(-1)
else:
    print(h * w - black_num - least - 1)

Submission status: Wrong Answer

Solution code:
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
inf = 10 ** 5
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "#":
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = queue.Queue()
    q.put([0,0])
    step = mas.copy()
    for i in range(h):
        for j in range(w):
            step[i][j] = inf
    step[0][0] = 0
    while not q.empty():
        s = q.get()
        if s[0] == h-1 and s[1] == w-1:
            break
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and step[nx][ny] == inf):
                q.put([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1
    bcnt = 0
    cnt = 0
    
    while cnt <= step[h-1][w-1]:
        whe = 0
        for i in range(h):
            for j in range(w):
                if step[i][j] == cnt:
                    if(mas[i][j] == "#"):
                        whe += 1
                    else:
                        whe -= 1
        if(whe == 1):
            bcnt += 1
        cnt += 1
        
    return [step[h-1][w-1],bcnt]

least = bfs()[0]
bcnt = bfs()[1]
print(h * w - black_num - (least - bcnt) - 1)

Submission status: Wrong Answer

Solution code:
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
inf = 10 ** 5
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "#":
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = queue.Queue()
    q.put([0,0])
    step = mas.copy()
    for i in range(h):
        for j in range(w):
            step[i][j] = inf
    step[0][0] = 0
    while not q.empty():
        s = q.get()
        if s[0] == h-1 and s[1] == w-1:
            break
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and step[nx][ny] == inf):
                q.put([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1
    bcnt = 0
    cnt = 0
    whe = 0
    while cnt <= step[h-1][w-1]:
        for i in range(h):
            for j in range(w):
                if step[i][j] == cnt:
                    if(mas[i][j] == "#"):
                        whe += 1
                    else:
                        whe -= 1
        if(whe == 1):
            bcnt += 1
        cnt += 1
            
    return [step[h-1][w-1],bcnt]

least = bfs()[0]
bcnt = bfs()[1]
print(h * w - black_num - (least - bcnt) - 1)

Submission status: Wrong Answer

Solution code:
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
inf = 10 ** 5
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "#":
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = queue.Queue()
    q.put([0,0])
    step = mas.copy()
    for i in range(h):
        for j in range(w):
            step[i][j] = inf
    step[0][0] = 0
    while not q.empty():
        s = q.get()
        if s[0] == h-1 and s[1] == w-1:
            return step[h-1][w-1]
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and mas[nx][ny] != "#" and step[nx][ny] == inf):
                q.put([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1

least = bfs()
print(h * w - black_num -least - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

dd = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def BFS():
    Q = deque([(0, 0)])
    D = [[-1] * W for _ in range(H)]
    D[0][0] = 0
    while Q:
        i, j = Q.popleft()
        for di, dj in dd:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if D[ni][nj] == -1 and A[ni][nj] == 0:
                    D[ni][nj] = D[i][j] + 1
                    Q.append((ni, nj))
    return D

print(H * W - sum([sum(a) for a in A]) - BFS()[-1][-1] - 1)