Problem:


Score: 400 points

Problem statement

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

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

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

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

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

Constraints

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

209



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


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[[0 for j in range(W)] for i in range(H)]
visited[0][0]=1
pointer=0
ans=10000000000000000000
def bfs(i,j,count):
  global ans
  global pointer
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i][j+1]==0:
      visited[i][j+1]=1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i][j-1]==0:
      visited[i][j-1]=1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[(i+1)][j]==0:
      visited[(i+1)][j]=1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[(i-1)][j]==0:
      visited[(i-1)][j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    ans=min(ans,count)
    #print(ans)
    pointer=1
    visited[-1][-1]=0
bfs(0,0,1)
#print(A)
#print(visited)
if (pointer==0):
  print("-1")
else:
  print(temp-ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[0 for i in range((H)*(W))]
visited[0]=1
pointer=0
ans=10000000000000000000
def bfs(i,j,count):
  global ans
  global pointer
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i*W+j+1]==0:
      visited[i*W+j+1]=1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i*W+j-1]==0:
      visited[i*W+j-1]=1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[(i+1)*W+j]==0:
      visited[(i+1)*W+j]=1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[(i-1)*W+j]==0:
      visited[(i-1)*W+j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    ans=min(ans,count)
    #print(ans)
    pointer=1
    visited[-1]=0
bfs(0,0,1)
#print(A)
#print(visited)
if (pointer==0 or A[0][0]=="#") or A[-1][-1]=="#":
  print(-1)
else:
  print(temp-ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[0 for i in range((H)*(W))]
visited[0]=1

ans=10000000000000000000
def bfs(i,j,count):
  global ans
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i*W+j+1]==0:
      visited[i*W+j+1]=1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i*W+j-1]==0:
      visited[i*W+j-1]=1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[(i+1)*W+j]==0:
      visited[(i+1)*W+j]=1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[(i-1)*W+j]==0:
      visited[(i-1)*W+j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    ans=min(ans,count)
    #print(ans)
  visited[-1]=0
bfs(0,0,1)
#print(A)
#print(visited)
if ans==10000000000000000000:
  print(-1)
else:
  print(temp-ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())

field=[list(input())for i in range(h)]
cnt=0
for i in field:
    for j in i:
        if j=='#':
            cnt+=1
dp=[[0 for i in range(w)]for i in range(h)]

dydx=[[-1,0],[1,0],[0,-1],[0,1]]

queue=[]
queue.append([0,0])

while queue:
    ny,nx=queue.pop(0)
    for dy,dx in dydx:
        nny,nnx=ny+dy,nx+dx
        if 0<=nny<=h-1 and 0<=nnx<=w-1 and field[nny][nnx]!="#" and dp[nny][nnx]==0:
            dp[nny][nnx]=dp[ny][nx]+1
            queue.append([nny,nnx])
            if nny==h-1 and nnx==w-1:
                print(h*w-cnt-dp[h-1][w-1]-1)
                exit()

Submission status: Wrong Answer

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

for ch in range(H):
    for cw in range(W):
        if ch==cw==0:
            pass
        else:
            if s[ch][cw]=="#" or H-1==ch and W-1==cw:
                continue
            s[ch][cw]="#"


        visited=[[0 for i in range(W)] for h in range(H)]
        visited[0][0]=1
        stack=[[0,0]]
        flag=0
        while stack:

            y,x=stack.pop()
            lst=[]
            if y>0:lst.append([-1,0])
            if y<H-1:lst.append([1,0])
            if x>0:lst.append([0,-1])
            if x<W-1:lst.append([0,1])
            for y1,x1 in lst:
                Y=y+y1
                X=x+x1
                if Y==H-1 and X==W-1:
                    flag=1
                    break
                if not visited[Y][X] and s[Y][X]==".":
                    stack.append([Y,X])
                    visited[Y][X]=1
        if flag:
            count+=1

        if ch==cw==0:
            pass
        else:
            if not flag:
                s[ch][cw]="."



print(count)

Submission status: Wrong Answer

Solution code:
# AGC088 D - Grid Repainting
from collections import deque
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())
sy,sx=0,0
gy,gx=h-1,w-1
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
bfs(sy,sx,gx,gy)

ans=0
black=0
for p in path:
    black+=p.count('#')

ans=h*w-(visited[gy][gx]+1)-black
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
import sys
H, W = map(int, input().split())
city = []
dot_count = 0
for i in range(H):
    city.append(input())
    dot_count += city[i].count('.')
search_point = deque([[0, 0, 0]])
direction_list = [[1,0],[-1,0],[0,1],[0,-1]]
searched_point = [[False for _ in range(W)] for _ in range(H)]
while search_point:
    now_point = search_point.popleft()
    for direction in direction_list:
        next_point = [now_point[0] + direction[0], now_point[1] + direction[1], now_point[2] + 1]
        if next_point[0] < 0 or next_point[0] >= H or next_point[1] < 0 or next_point[1] >= W \
        or city[next_point[0]][next_point[1]] == '#' or searched_point[next_point[0]][next_point[1]] == True:
            continue
        if next_point[0] == H-1 and next_point[1] == W-1:
            print(dot_count - next_point[2] - 1)
            sys.exit()
        searched_point[next_point[0]][next_point[1]] = True
        search_point.append(next_point)

Submission status: Wrong Answer

Solution code:
import sys
H, W = map(int, input().split())
city = []
dot_count = 0
for i in range(H):
    city.append(input())
    dot_count += city[i].count('.')
search_point = [[0, 0, 0]]
direction_list = [[1,0],[-1,0],[0,1],[0,-1]]
searched_point = [[False for _ in range(W)] for _ in range(H)]
while search_point:
    now_point = search_point.pop()
    for direction in direction_list:
        next_point = [now_point[0] + direction[0], now_point[1] + direction[1], now_point[2] + 1]
        if next_point[0] < 0 or next_point[0] >= H or next_point[1] < 0 or next_point[1] >= W \
        or city[next_point[0]][next_point[1]] == '#' or searched_point[next_point[0]][next_point[1]] == True:
            continue
        if next_point[0] == H-1 and next_point[1] == W-1:
            print(dot_count - next_point[2] - 1)
            sys.exit()
        searched_point[next_point[0]][next_point[1]] = True
        search_point.append(next_point)

Submission status: Wrong Answer

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

zenbu="#"*w
li.insert(0,zenbu)
li.append(zenbu)

for i in range(h+2):
  li[i]="#"+li[i]
  li[i]+="#"

ys,xs=2,2
yg,xg=h+1,w+1
a=li

n=[(ys-1,xs-1)]
route={n[0]:0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((yg-1,xg-1),0)==0 and count != 10000:
    n2=[]
    for i in n:
        for j in p:
            np=(i[0]+j[0],i[1]+j[1])
            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                n2.append(np)
                route[np]=count
    n=n2
    count+=1
print(h*w-black-count)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = float('inf')
ROAD = '.'
WALL = '#'
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def main():
    H,W = map(int, input().split())
    maze = [None]*H
    white = 0
    
    for i in range(H):
        maze[i] = list(input())
        for j in range(W):
            if maze[i][j] == ROAD:
                white += 1
                maze[i][j] = INF
    
    # mazeにはその地点に到達するまでに必要な白の枚数を記録
    maze[0][0] = 1
    que = deque([[0, 0]])

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

        for (i, j) in STEPS:
            ny, nx = y+i, x+j
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            
            target = maze[ny][nx]
            if target != WALL:
                if target > maze[y][x]+1:
                    maze[ny][nx] = maze[y][x] + 1
                    que.append([ny,nx])
                    
    print(white - maze[H-1][W-1])
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())

    S = [[c for c in s] for s in args[1:]]

    ret = 0
    for s in S:
        ret += s.count('.')

    Q = deque()
    Q.append((0, 0, 1))
    while Q:
        x, y, n = Q.popleft()
        if S[y][x] == '.':
            S[y][x] = str(n)
            if (x, y) == (w-1, h-1):
                ret -= n

            if 0 < x:
                Q.append((x-1, y, n+1))
            if x+1 < w:
                Q.append((x+1, y, n+1))
            if 0 < y:
                Q.append((x, y-1, n+1))
            if y+1 < h:
                Q.append((x, y+1, n+1))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
H, W  = map(int, input().split())
f = []
INF = 10**10
dist = [[INF] * W for _ in range(H)]
cnt = 0
for i in range(H):
    S = list(input())
    for j,s in enumerate(S):
        if s == "#": dist[i][j] = -1
    cnt += S.count("#")
    f.append(s)
# print(cnt)

# 最短路以外を消す？
mvs = [(0,1),(0,-1),(1,0),(-1,0)]
from collections import deque
s = (0,0)
g = (H-1,W-1)
dist[0][0] = 0
q = deque()
q.append(s)
while q:
    h,w = q.popleft()
    # print(h,w)
    for dh, dw in mvs:
        if 0 <= h+dh < H and 0 <= w+dw < W: 
            # print("checked",h+dh,w+dw)
            if dist[h+dh][w+dw] == -1:
                continue
            elif dist[h+dh][w+dw] > dist[h][w] + 1:
                q.append((h+dh,w+dw))
                dist[h+dh][w+dw] = dist[h][w] + 1
# print(H*W)
# print(cnt)
# print(dist[H-1][W-1])
ans = H*W - dist[H-1][W-1] - 1 - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  q = deque()
  q.append([[1,1],0])
  used = set((1,1))
  
  while len(q)>0:
    prv_pos,prv_cost = q.pop()
    i,j = prv_pos
    for ii,jj in [[i+1,j],[i,j+1]]:
      if (ii,jj) in used: continue
      if S[jj][ii]=='.':
        if [ii,jj] == [W,H]:
          return prv_cost+1
        else:
          q.append([[ii,jj],prv_cost+1])
          used.add((ii,jj))
  return -1

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

res = bfs()
if res == -1:
  print(-1)
else:
  cntb = sum([row.count('#') for row in S])-2*(H+2)-2*(W+2)+4
  print(H*W-res-cntb-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  q = deque()
  q.append([[1,1],0])
  used = set((1,1))
  
  while len(q)>0:
    prv_pos,prv_cost = q.pop()
    i,j = prv_pos
    for ii,jj in [[i+1,j],[i,j+1]]:
      if (ii,jj) in used: continue
      if S[jj][ii]=='.':
        if [ii,jj] == [W,H]:
          return prv_cost+1
        else:
          q.append([[ii,jj],prv_cost+1])
          used.add((ii,jj))
  return -1

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

res = bfs()
if res == inf:
  print(-1)
else:
  cntb = sum([row.count('#') for row in S])-2*(H+2)-2*(W+2)+4
  print(H*W-res-cntb-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    distance = [[-1]*w for _ in range(h)]
    que = deque([])
    que.append((y, x))
    distance[y][x] = 0
    while que:
        y, x = que.popleft()
        if x == w-1 and y == h-1:
            break
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return distance

d = bfs(0, 0)
m = set()
for row in d:
    m |= set(row)
m -= set([-1])
cnt = 0
for row in field:
    cnt += row.count("#")
ans = h*w - cnt - len(m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
meiro = []
for h in range(H):
    meiro.append(input())
from collections import deque
Q = deque([[0,0]])
ansmap = [[-1 for _ in range(W)] for __ in range(H)]
ansmap[0][0] = 0
step = 0
while Q:
    cue = Q.popleft()
    step = ansmap[cue[0]][cue[1]]
    for i in range(4):
        # 上
        if cue[0]-1 >= 0:
            if meiro[cue[0]-1][cue[1]] == "." and (ansmap[cue[0]-1][cue[1]] > step+1 or ansmap[cue[0]-1][cue[1]] == -1):
                ansmap[cue[0]-1][cue[1]] = step+1
                Q.append([cue[0]-1,cue[1]])
        # 右
        if cue[1]+1 < W:
            if meiro[cue[0]][cue[1]+1] == "." and (ansmap[cue[0]][cue[1]+1] > step+1 or ansmap[cue[0]][cue[1]+1] == -1):
                ansmap[cue[0]][cue[1]+1] = step+1
                Q.append([cue[0],cue[1]+1])
        # 下
        if cue[0]+1 < H:
            if meiro[cue[0]+1][cue[1]] == "." and (ansmap[cue[0]+1][cue[1]] > step+1 or ansmap[cue[0]+1][cue[1]] == -1):
                ansmap[cue[0]+1][cue[1]] = step+1
                Q.append([cue[0]+1,cue[1]])
        # 左
        if cue[1]-1 >= 0:
            if meiro[cue[0]][cue[1]-1] == "." and (ansmap[cue[0]][cue[1]-1] > step+1 or ansmap[cue[0]][cue[1]-1] == -1):
                ansmap[cue[0]][cue[1]-1] = step+1
                Q.append([cue[0],cue[1]-1])
cnt=0
for m in meiro:
    cnt += m.count('.')
print(cnt - step + 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
meiro = []
for h in range(H):
    meiro.append(input())
from collections import deque
Q = deque([[0,0]])
ansmap = [[-1 for _ in range(W)] for __ in range(H)]
ansmap[0][0] = 0
step = 0
while Q:
    cue = Q.popleft()
    step = ansmap[cue[0]][cue[1]]
    for i in range(4):
        # 上
        if cue[0]-1 >= 0:
            if meiro[cue[0]-1][cue[1]] == "." and (ansmap[cue[0]-1][cue[1]] > step+1 or ansmap[cue[0]-1][cue[1]] == -1):
                ansmap[cue[0]-1][cue[1]] = step+1
                Q.append([cue[0]-1,cue[1]])
        # 右
        if cue[1]+1 < W:
            if meiro[cue[0]][cue[1]+1] == "." and (ansmap[cue[0]][cue[1]+1] > step+1 or ansmap[cue[0]][cue[1]+1] == -1):
                ansmap[cue[0]][cue[1]+1] = step+1
                Q.append([cue[0],cue[1]+1])
        # 下
        if cue[0]+1 < H:
            if meiro[cue[0]+1][cue[1]] == "." and (ansmap[cue[0]+1][cue[1]] > step+1 or ansmap[cue[0]+1][cue[1]] == -1):
                ansmap[cue[0]+1][cue[1]] = step+1
                Q.append([cue[0]+1,cue[1]])
        # 左
        if cue[1]-1 >= 0:
            if meiro[cue[0]][cue[1]-1] == "." and (ansmap[cue[0]][cue[1]-1] > step+1 or ansmap[cue[0]][cue[1]-1] == -1):
                ansmap[cue[0]][cue[1]-1] = step+1
                Q.append([cue[0],cue[1]-1])
cnt=0
for m in meiro:
    cnt += m.count('#')
print(H*W - ansmap[H-1][W-1]-1 - cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
meiro = []
for h in range(H):
    meiro.append(input())
from collections import deque
Q = deque([[0,0]])
ansmap = [[-1 for _ in range(W)] for __ in range(H)]
ansmap[0][0] = 0
step = 0
while Q:
    cue = Q.popleft()
    step = ansmap[cue[0]][cue[1]]
    for i in range(4):
        # 上
        if cue[0]-1 >= 0:
            if meiro[cue[0]-1][cue[1]] == "." and (ansmap[cue[0]-1][cue[1]] > step+1 or ansmap[cue[0]-1][cue[1]] == -1):
                ansmap[cue[0]-1][cue[1]] = step+1
                Q.append([cue[0]-1,cue[1]])
        # 右
        if cue[1]+1 < W:
            if meiro[cue[0]][cue[1]+1] == "." and (ansmap[cue[0]][cue[1]+1] > step+1 or ansmap[cue[0]][cue[1]+1] == -1):
                ansmap[cue[0]][cue[1]+1] = step+1
                Q.append([cue[0],cue[1]+1])
        # 下
        if cue[0]+1 < H:
            if meiro[cue[0]+1][cue[1]] == "." and (ansmap[cue[0]+1][cue[1]] > step+1 or ansmap[cue[0]+1][cue[1]] == -1):
                ansmap[cue[0]+1][cue[1]] = step+1
                Q.append([cue[0]+1,cue[1]])
        # 左
        if cue[1]-1 >= 0:
            if meiro[cue[0]][cue[1]-1] == "." and (ansmap[cue[0]][cue[1]-1] > step+1 or ansmap[cue[0]][cue[1]-1] == -1):
                ansmap[cue[0]][cue[1]-1] = step+1
                Q.append([cue[0],cue[1]-1])
cnt=0
for m in meiro:
    cnt += m.count('#')
print(H*W - ansmap[H-1][W-1]+1 - cnt -2)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(" "))
grid = list()
for _ in range(H):
    l = list()
    for c in input():
        if c == ".":
            l.append(True)
        else:
            l.append(None)
    grid.append(l)


def get_neighbors(x, y):
    neighbors = ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
    result = list()
    for neighbor in neighbors:
        x, y = neighbor
        if 0 <= x <= W-1 and 0 <= y <= H-1:
            result.append((x, y))
    return result


current_x = 0
current_y = 0
distance = 0
queue = list()
queue.append((current_x, current_y, distance))
while True:
    if not queue:
        break
    current_x, current_y, distance = queue.pop(0)
    grid[current_y][current_x] = distance
    if current_y == H - 1 and current_x == W - 1:
        break
    for neighbor in get_neighbors(current_x, current_y):
        x, y = neighbor
        if grid[y][x] is not None:
            if grid[y][x] is True:
                queue.append((x, y, distance+1))


if grid[H-1][W-1] is None:
    print(-1)
else:
    test = [l.count(None) for l in grid]
    num_black = sum(l.count(None) for l in grid)
    print(H*W - num_black - grid[H-1][W-1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(" "))
grid = list()
for _ in range(H):
    l = list()
    for c in input():
        if c == ".":
            l.append(True)
        else:
            l.append(None)
    grid.append(l)


def get_neighbors(x, y):
    neighbors = ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
    result = list()
    for neighbor in neighbors:
        x, y = neighbor
        if 0 <= x <= W-1 and 0 <= y <= H-1:
            result.append((x, y))
    return result


current_x = 0
current_y = 0
distance = 0
queue = list()
queue.append((current_x, current_y, distance))
while True:
    if not queue:
        break
    current_x, current_y, distance = queue.pop(0)
    grid[current_y][current_x] = distance
    for neighbor in get_neighbors(current_x, current_y):
        x, y = neighbor
        if grid[y][x] is not None:
            if grid[y][x] is True:
                queue.append((x, y, distance+1))

test = [l.count(None) for l in grid]
num_black = sum(l.count(None) for l in grid)
print(H*W - num_black - grid[H-1][W-1] - 1)

Submission status: Wrong Answer

Solution code:
#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False

def result():
    cnt = 0
    for j in range(W):
        for i in range(H):
            if s_tmp[i][j] =='.':
                cnt += 1
    if flg == False:
        print(-1)
    else :
        print(cnt-z-2)
        
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    #print(z+1)
                    flg = True
                    result()
                    sys.exit()
                s[ny][nx] = 'y'

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    s=[[] for _ in range(H+2)]
    s[0]=s[H+1]=['#']*(W+2)
    white=-1
    for i in range(1,H+1):
        row=['#']+list(input())+['#']
        s[i]=row
        for cell in row:
            if cell=='.':
                white+=1
    queue=deque()
    queue.append([1,1])
    d=[[INF]*(W+2) for _ in range(H+2)]
    d[1][1]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while queue:
        cell=queue.popleft()
        for k in range(4):
            if s[cell[0]+dx[k]][cell[1]+dy[k]]=='.' and d[cell[0]+dx[k]][cell[1]+dy[k]]==INF:
                queue.append([cell[0]+dx[k],cell[1]+dy[k]])
                d[cell[0]+dx[k]][cell[1]+dy[k]]=min(d[cell[0]+dx[k]][cell[1]+dy[k]],d[cell[0]][cell[1]]+1)
    print(white-d[H][W])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]

import sys
from collections import deque

moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
H, W = fetch_int_input()
maze = [list(fetch_one_line()) for _ in range(H)]
X, Y = 0, 1
STARTS = (0, 0)
GOALS = (H - 1, W - 1)


def count_wall(maze, wall="#"):
    wall_num = 0
    for one_line in maze:
        wall_num += "".join(one_line).count(wall)
    return wall_num

def bfs():
    que = deque()
    d = [[sys.maxsize for _ in range(W)] for _ in range(H)]
    que.append(STARTS)
    d[STARTS[X]][STARTS[Y]] = 0

    while que:
        now_pos = que.popleft()
        if now_pos == GOALS:
            break
        for move in moves:
            np = (now_pos[X] + move[X], now_pos[Y] + move[Y])
            if np[X] >= 0 and np[Y] >= 0 and np[X] < H and np[Y] < W and maze[np[X]][np[Y]] == '.' and d[np[X]][np[Y]] == sys.maxsize:
                que.append(np)
                d[np[X]][np[Y]] = d[now_pos[X]][now_pos[Y]] + 1

    return d[GOALS[X]][GOALS[Y]]

min_distance = bfs()
wall_num = count_wall(maze, "#")
changable_num = H * W - 2 - (min_distance - 1) - wall_num
print(changable_num)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
s_y, s_x = (0, 0)
g_y, g_x = (H-1, W-1)

c = [input() for a in range(H)]

d = [[ sys.maxsize for b in range(W)] for a in range(H)]

blackcount = 0
for y in range(H):
  blackcount += c[y].count('#')

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

q = deque([[s_y, s_x]])

d[s_y][s_x] = 0

while len(q) > 0:
  y, x = q.popleft()
  if y==g_y and x==g_x:
    print(H * W - blackcount - 1 - d[y][x])
    exit()
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and c[ny][nx] == '.' and d[ny][nx] == sys.maxsize:
      q.append([ny, nx])
      d[ny][nx] = d[y][x]+1

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
mat = []
wsum = 0
for i in range(H):
    mat.append(list(input()))
    wsum += mat[i].count('.')
start = [0,0]
x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
alr = [[-1 for i in range(W)] for j in range(H)]
alr[0][0] = 0
que = deque()
count = 0
que.append([0,0])
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if q[0]+x1[i] == H-1 and q[1]+y1[i] == W-1:
                count = alr[q[0]][q[1]] + 1
                que.clear()
            elif mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                que.append([q[0]+x1[i],q[1]+y1[i]])
print(wsum - (count+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
maze = [input() for i in range(H)]
visit = [[0]*W for i in range(H)]
x, y = 0, 0
cnt = 0
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      cnt += 1
def bfs(maze, visit, x, y):
  queue = deque()
  queue.append([0, 0])
  visit[y][x] = 1
  ans = 10**18
  while queue:
    y, x = queue.popleft()
    if y == H-1 and x == W-1:
      return cnt-visit[y][x]-1
    for i, j in [[1,0],[-1,0],[0,1],[0,-1]]:
      nextx, nexty = x+i, y+j
      if nextx<0 or nextx>=W or nexty<0 or nexty>=H:
        continue
      elif maze[nexty][nextx] != "#" and visit[nexty][nextx] ==0:
        visit[nexty][nextx] = visit[y][x] + 1
        queue.append([nexty,nextx])
  return -1
print(bfs(maze,visit,x,y))

Submission status: Wrong Answer

Solution code:
import numpy as np
temp=list(map(int, input().split()))
H=temp[0]
W=temp[1]

s=(0,0)
g=(H-1,W-1)

c=np.zeros((H,W)).astype(int)

for i in range(H):
  temp=input()
  a=np.zeros(W).astype(int)
  for j in range(W):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  c[i]=a
n_black=int(np.sum(c))
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<H and v[1]>=0 and v[1]<W:
        adj.append(v)
  return adj  

color=np.zeros((H,W)).astype(int)
d=np.zeros((H,W)).astype(int)-1
d[s[0],s[1]]=0
def BFS():
  Q=[s]
  while Q !=[]:
    u=Q[0]
    if g==u:
      print(H*W-n_black-(d[u[0],u[1]]+1))
      return
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0 and color[v[0],v[1]]==0:
        color[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
BFS()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
c=[['#']*(W+2)]
ten=0
for i in range(H):
    ip=list(input())
    ten+=ip.count('.')
    c.append(['#']+ip+['#'])
c.append(['#']*(W+2))
Q=deque([[1,1,1]])

def move(yxc):
    global Q,c
    y,x,cost=yxc[0],yxc[1],yxc[2]
    if c[y+1][x]=='.':
        c[y+1][x]=cost+1
        Q.append([y+1,x,cost+1])
    if c[y-1][x]=='.':
        c[y-1][x]=cost+1
        Q.append([y-1,x,cost+1])
    if c[y][x+1]=='.':
        c[y][x+1]=cost+1
        Q.append([y,x+1,cost+1])
    if c[y][x-1]=='.':
        c[y][x-1]=cost+1
        Q.append([y,x-1,cost+1])

c[1][1]=1
while len(Q)>0:
    move(Q.popleft())

ans=0
for i in range(H+2):
    for j in range(W+2):
        if c[i][j]!='.' and c[i][j]!='#':
            ans=max(ans,c[i][j])
print(ten-ans)

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 = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mt = min(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 mt !=10 ** 10 else -1)


if __name__ == '__main__':
    solve()