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:
cin = open(0).read().strip().split('\n')
h,w = map(int, cin[0].split(' '))
s = [list(a) for a in cin[1:]]

from collections import deque
q = deque()

dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0]=0

q.append((0,0))
while q:
    ph, pw = q.popleft()
    for dyi, dxi in zip([0,-1,0,1],[1,0,-1,0]):
        if 0<=ph+dyi<h and 0<=pw+dxi<w:
            if dist[ph+dyi][pw+dxi] != -1: continue
            if s[ph+dyi][pw+dxi] == '#': continue
            q.append((ph+dyi, pw+dxi))
            dist[ph+dyi][pw+dxi] = dist[ph][pw]+1

last = dist[h-1][w-1]
dic = {key:0 for key in range(last+1)}
ret = 0
for i in range(h):
    for j in range(w):
        if dist[i][j] in dic:
            dic[dist[i][j]] += 1
        elif s[i][j] == '.':
            ret += 1

for i in dic.values():
    ret += i-1

print(ret)

Submission status: Wrong Answer

Solution code:
import math
import bisect
from queue import Queue
from collections import deque

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

count = 0
for i in range(h):
    for j in range(w):
        if(table[i][j] == "."):
            count += 1

q = deque()
q.append(0)
q.append(0)
table[0][0] = 1
flag = -1
while(len(q)):
    nowx = q.popleft()
    nowy = q.popleft()

    if((nowx == h-1) and (nowy == w-1)):
        flag = int(table[nowx][nowy])

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

    for i in range(4):
        tempx = nowx + dx[i]
        tempy = nowy + dy[i]
        if((0 <= tempx)and(tempx < h)and(0 <= tempy)and(tempy < w)):
            if(table[tempx][tempy] =="."):
                table[tempx][tempy] = table[nowx][nowy] + 1
                q.append(tempx)
                q.append(tempy)


print(count-flag)

Submission status: Wrong Answer

Solution code:
import sys

h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  for j in s:
    if j=="#":
      black+=1

dist=[[False]*w for i in range(h)]
done=[[float('inf')]*w for i in range(h)]

cnt=0
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    dist[y][x]=True
    
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]

    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or dist[my][mx]==True:
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
    
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()


if __name__=="__main__":
  bfs()

Submission status: Wrong Answer

Solution code:
import sys
h,w=[int(x) for x in input().rstrip().split()]
l=[]
cnt=0
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  for j in s:
    if j=="#":
      black+=1
dist=[[False]*w for i in range(h)]
done=[[float('inf')]*w for i in range(h)]
cnt=0
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    dist[y][x]=True
    
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]

    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#":
        continue

      if dist[my][mx]==True:
        continue

      if done[my][mx]==float('inf'):
        done[my][mx]=done[y][x]+1
      else:
        done[my][mx]=min(done[my][mx],done[y][x]+1)
      stack.append([mx,my])
    
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()


if __name__=="__main__":
  bfs()

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    ans = white - max(0,visit[(H-2)*W+W-2])
    if ans == 0:
        return -1
    else:
        return ans


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    return white - max(0,visit[(H-2)*W+W-2])


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w=map(int,input().split(' '))
maze=[0]*h
kuro=0
for y in range(h):
    line=input()
    kuro+=line.count('#')
    maze[y]=line
count=[[-1]*w for _ in range(h)]
count[0][0]=1

q=deque([[0,0]])
def BFS():
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):
            return h*w-kuro-count[h-1][w-1]
        for dy,dx in [[0,1],[1,0],[-1,0],[0,1]]:
            ny,nx=y+dy,x+dx
            if not (0<=ny<h and 0<=nx<w):
                continue
            if maze[ny][nx]=='.' and count[ny][nx]==-1:
                q.append([ny,nx])
                count[ny][nx]=count[y][x]+1
    return -1

print(BFS())

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w=map(int,input().split(' '))
maze=[0]*h
kuro=0
for y in range(h):
    line=input()
    kuro+=line.count('#')
    maze[y]=line
count=[[-1]*w for _ in range(h)]
count[0][0]=1

q=deque([[0,0]])
def BFS():
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):
            return count[h-1][w-1]
        for dy,dx in [[0,1],[1,0],[-1,0],[0,1]]:
            ny,nx=y+dy,x+dx
            if not (0<=ny<h and 0<=nx<w):
                continue
            if maze[ny][nx]=='.' and count[ny][nx]==-1:
                q.append([ny,nx])
                count[ny][nx]=count[y][x]+1
    return -1

print(h*w-kuro-BFS())

Submission status: Wrong Answer

Solution code:
from queue import Queue
import copy
import collections

R, C = map(int, input().split(' '))
M = [[s for s in input()] for _ in range(R)]
trial = 0


Sy = 1
Sx = 1
Gy = R
Gx = C

cnt  = 0
for i in range(R):
  cnt += M[i].count('#')

L = copy.deepcopy(M)

move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = Queue()
ans = 0

q.put([(Sy, Sx)])
L[Sy-1][Sx-1] = '#'

while not q.empty():
  pos = q.get()
  valid_pos = []
  for p in pos:
      for m in move:
          y, x = p[0]+m[0], p[1]+m[1]
          if y == Gy and x == Gx:
            ans += 1
            print(R*C-ans-1-cnt)
            exit()            
          if 1<= y  <= R and 1<= x <= C:
            if L[y-1][x-1] == '.':
              L[y-1][x-1] = '#'
              valid_pos.append((y, x))
  if len(valid_pos) != 0:
      q.put(valid_pos)
  ans += 1

Submission status: Wrong Answer

Solution code:
from queue import Queue
import copy
import collections

R, C = map(int, input().split(' '))
M = [[s for s in input()] for _ in range(R)]
trial = 0

for i in range(R):
  for j in range(C):
    Sy = i+1
    Sx = j+1
    L = copy.deepcopy(M)
    if L[Sy-1][Sx-1] == '.':
      move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
      q = Queue()
      ans = 0

      q.put([(Sy, Sx)])
      L[Sy-1][Sx-1] = '#'

      while not q.empty():
          pos = q.get()
          valid_pos = []
          for p in pos:
              for m in move:
                  y, x = p[0]+m[0], p[1]+m[1]
                  if 1<= y  <= R and 1<= x <= C:
                    if L[y-1][x-1] == '.':
                      L[y-1][x-1] = '#'
                      valid_pos.append((y, x))
          if len(valid_pos) != 0:
              q.put(valid_pos)
          ans += 1
      trial = max(ans, trial)

cnt  = 0
for i in range(R):
  cnt += M[i].count('#')
print(R*C-trial-cnt)

Submission status: Wrong Answer

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

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
            break
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j] if d[i][j] != INF else 0 
solvable = bfs(0, 0)
print(h*w - cnt_b - solvable if solvable else -1)

Submission status: Wrong Answer

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

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
            break
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]
print(h*w - cnt_b - bfs(0, 0))

Submission status: Wrong Answer

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

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]
print(h*w - cnt_b - bfs(0, 0))

Submission status: Wrong Answer

Solution code:
from queue import Queue
import itertools
import numpy as np

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

field = [["#"] * (C + 2)] + \
        [list("#" + input() + "#") for i in range(R)] + \
        [["#"] * (C + 2)]
field = np.array(field)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

field_1d = list(itertools.chain.from_iterable(field))
field01 = [1 if i == '.' else 0 for i in field_1d]
dot_num = np.array(field01).sum()

q = Queue()
q.put([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.get()
    cnt = int(field[yx[0]][yx[1]])
    for dy, dx in dxy:
        y_n, x_n = yx[0] + dy, yx[1] + dx
        if y_n == gy and x_n == gx:
            field[y_n][x_n] = cnt + 1
            flg = True
            print(dot_num - (cnt+2))
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.put([y_n, x_n])
            field[y_n][x_n] = cnt + 1
if flg == False:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
h,w=LI()
s=[S() for _ in range(h)]
blackcount=0
for i,j in itertools.product(range(h),range(w)):
    if s[i][j]=="#":
        blackcount+=1
dhdw=[[-1,0],[1,0],[0,-1],[0,1]]
mindist=[[-1]*w for _ in range(h)]
seen=[[0]*w for _ in range(h)]
queue=collections.deque()
def bfs():
    seen[0][0]=1
    queue.append([0,0])
    mindist[0][0]=1
    while queue:
        qh,qw=queue.popleft()
        for dh,dw in dhdw:
            nh,nw=qh+dh,qw+dw
            if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or s[nh][nw]=="#":
                continue
            if [nh,nw]==[h-1,w-1]:
                return mindist[qh][qw]
            seen[nh][nw]=1
            queue.append([nh,nw])
            mindist[nh][nw]=mindist[qh][qw]+1
    else:
        return -1
mindist=bfs()
print(h*w-blackcount-mindist if mindist!=-1 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
lst=[[] for f in range(H)]
for i in range(H):
 lst[i] = [d for d in input()]
stack = deque([[0,0]])
muki=[[1,0],[-1,0],[0,1],[0,-1]]
check=[[0 for e in range(W)] for f in range(H)] #チェック済みリスト
check[0][0]=1
t=0
while stack != deque([]) :
 a=stack.pop()
 for i in muki:
  b0=a[0]+i[0]
  b1=a[1]+i[1]
  if b0<=H-1 and b0>=0 and b1<=W-1 and  b1>=0:
   if check[b0][b1]==0 and lst[b0][b1]==".":
    if check[b0][b1]!=0:
     check[b0][b1]=min(check[b0][b1],check[a[0]][a[1]]+1)
    else:
     check[b0][b1]=check[a[0]][a[1]]+1
    stack.append([b0,b1])
if check[H-1][W-1]==0:
 print(-1)
else:
 ct=0
 for i in range(H):
  for j in range(W):
   if lst[i][j]==".":
    ct+=1
 print(ct-check[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
lst=[[] for f in range(H)]
for i in range(H):
 lst[i] = [d for d in input()]
stack = deque([[0,0]])
muki=[[1,0],[-1,0],[0,1],[0,-1]]
check=[[0 for e in range(W)] for f in range(H)] #チェック済みリスト
check[0][0]=1
t=0
while stack != deque([]) and check[H-1][W-1]==0:
 a=stack.pop()
 for i in muki:
  b0=a[0]+i[0]
  b1=a[1]+i[1]
  if b0<=H-1 and b0>=0 and b1<=W-1 and  b1>=0:
   if check[b0][b1]==0 and lst[b0][b1]==".":
    check[b0][b1]=check[a[0]][a[1]]+1
    stack.append([b0,b1])
if check[H-1][W-1]==0:
 print(-1)
else:
 ct=0
 for i in range(H):
  for j in range(W):
   if lst[i][j]==".":
    ct+=1
 if ct-check[H-1][W-1]==0:
  print(-1)
 else:
  print(ct-check[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
lst=[[] for f in range(H)]
for i in range(H):
 lst[i] = [d for d in input()]
stack = deque([[0,0]])
muki=[[1,0],[-1,0],[0,1],[0,-1]]
check=[[0 for e in range(W)] for f in range(H)] #チェック済みリスト
check[0][0]=1
t=0
while stack != deque([]) and check[H-1][W-1]==0:
 a=stack.pop()
 for i in muki:
  b0=a[0]+i[0]
  b1=a[1]+i[1]
  if b0<=H-1 and b0>=0 and b1<=W-1 and  b1>=0:
   if check[b0][b1]==0 and lst[b0][b1]==".":
    check[b0][b1]=check[a[0]][a[1]]+1
    stack.append([b0,b1])
if check[H-1][W-1]==0:
 print(-1)
else:
 ct=0
 for i in range(H):
  for j in range(W):
   if lst[i][j]==".":
    ct+=1
 print(ct-check[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for i in range(H)]
Q = deque()
Q.append([0, 0])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
c = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            c += 1

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

while (len(Q) > 0):
    q = Q.popleft()

    for i in range(4):
        y = q[0] + yudrl[i]
        x = q[1] + xudrl[i]

        if y < 0 or y > H - 1 or x < 0 or x > W - 1:
            continue  
        if dist[y][x] != -1 or s[y][x] == '#':
            continue
        dist[y][x] = dist[q[0]][q[1]] + 1
        Q.append([y, x])

print(c - dist[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append(input())
queue = deque([[0,0]])
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1 and s[nh][nw] == ".":
            queue.append([nh, nw])
            dist[nh][nw] = dist[h][w] + 1
ans = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            ans += 1
ans = ans - dist[H-1][W-1] -1
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
L=[]
for i in range(H):
    l=list(input())
    L.append(l)
T=[[0 for i in range(W)] for l in range(H)]
T[0][0]=1
S=[[0,0]]
SS=[[0,0]]
v=0
count=0
while 1:
    count+=1
    S=SS
    SS=[]
    while 1:
        x=S[0][1]
        y=S[0][0]
        if 0<=y and y<H-1:
            if L[y+1][x]=="." and T[y+1][x]==0:
                s=[y+1,x]
                T[y+1][x]=1
                SS.append(s)
                if y+1==H-1 and x==W-1:
                    v=1
                    break
        if 0<y and y<=H-1:
            if L[y-1][x]=="." and T[y-1][x]==0:
                s=[y-1,x]
                T[y-1][x]=1
                SS.append(s)
                if y-1==H-1 and x==W-1:
                    v=1
                    break
        if 0<=x and x<W-1:
            if L[y][x+1]=='.' and T[y][x+1]==0:
                s=[y,x+1]
                T[y][x+1]=1
                SS.append(s)
                if y==H-1 and x+1==W-1:
                    v=1
                    break
        if 0<x and x<=W-1:
            if L[y][x-1]=='.' and T[y][x-1]==0:
                s=[y,x-1]
                T[y][x-1]=1
                SS.append(s)
                if y==H-1 and x-1==W-1:
                    v=1
                    break
        S.pop(0)
        if len(S)==0:
            break
    if v==1:
        break
    if len(SS)==0:
        v=0
        break
x=0
print(count)
if v==0:
    print(-1)
else:
    for i in range(H):
        for l in range(W):
            if L[i][l]=='#':
                x+=1
    print(W*H-x-count-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
field = []
countd = 0
for _ in range(H):
    ls = []
    st = str(input())
    for ss in st:
        ls.append(ss)
        if ss =='.':
            countd += 1
    field.append(ls)
import heapq
import copy
ans = float('inf')
dis = [[float('inf')]*51 for i in range(51)]
def caldis(x,y):#ある点を黒にして計算できる距離の中で際異端のものを求める
    fieldf = copy.deepcopy(field)
    fieldf[x][y] = '#'
    disf = copy.deepcopy(dis)
    used = [[False]*50 for i in range(50)]
    que = []
    heapq.heappush(que,[0,0,0])
    while len(que)>0:
        pre = heapq.heappop(que)
        d = pre[0]
        px = pre[1]
        py = pre[2]
        if used[px][py] ==True:
            continue
        used[px][py] = True
        disf[px][py] = d
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=px+dx<=H-1:
                    if fieldf[px+dx][py]=='.':
                        heapq.heappush(que,[d+1,px+dx,py])
                if 0<=py+dy<=W-1:
                    if fieldf[px][py+dy]=='.':
                        heapq.heappush(que,[d+1,px,py+dy])

    res = disf[H-1][W-1]
    return res
mdis = float('inf')
for i in range(H):
    for j in range(W):
        if field[i][j]=='.' and (not(i==0 and j==0)) and (not(i==(H-1) and j==(W-1))):
            mdis = min(mdis,caldis(i,j))

ans = countd - (mdis)-1
if mdis==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

bc = 0
for h in range(H):
  n = Counter(s[h])
  bc += n['#']


def dfs():
  que = deque()
  que.append((0,0))
  di = [1, 0, -1, 0]
  dj = [0, 1, 0, -1]
  d = [[float('inf')]*W for h in range(H)]
  d[0][0] = 0
  while que:
    point = que.popleft()
    if point[0] == H-1 and point[1] == W-1:
      break
    for i in range(4):
      ni = point[0] + di[i]
      nj = point[1] + dj[i]
      if 0 <= ni < H and 0 <= nj < W and d[ni][nj] == float('inf') and s[ni][nj] != '#':
        que.append((ni, nj))
        d[ni][nj] = d[point[0]][point[1]] + 1
  return d[H-1][W-1]

    
dfs()
score = H*W - bc - dfs() -1 
print(score)

Submission status: Wrong Answer

Solution code:
import collections
import time
def bfs(G,l):
    l.append([1,1])
    visited = [[0] * len(G[0]) for i in range(len(G))]
    chk = 0
    G[1][1] = 0
    while(len(l)):
        [n0,n1] = l.popleft()
        if visited[n0][n1] == 1:
            continue
        else:
            visited[n0][n1] = 1
        if [n0,n1] == [len(G)-2,len(G[0])-2]:
            chk = 1
            break
        if G[n0][n1+1] != "#" and visited[n0][n1+1] == 0:
            l.append([n0,n1+1])
            G[n0][n1+1] = min(G[n0][n1] + 1,G[n0][n1+1])

        if G[n0][n1-1] != "#" and visited[n0][n1-1] == 0:
            l.append([n0,n1-1])
            G[n0][n1-1] = min(G[n0][n1] + 1,G[n0][n1-1])

        if G[n0+1][n1] != "#" and visited[n0+1][n1] == 0:
            l.append([n0+1,n1])
            G[n0+1][n1] = min(G[n0][n1]+1,G[n0+1][n1])

        if G[n0-1][n1] != "#" and visited[n0-1][n1] == 0:
            l.append([n0-1,n1])
            G[n0-1][n1] = min(G[n0][n1]+1,G[n0-1][n1])
        #print(n0,n1)
    return chk

[h,w] = [int(i) for i in input().split()]
st = time.time()
s = [["#"] * (w+2)]
whites = 0
for i in range(h):
    ls = ["#"]
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            ls.append(200)
        else:
            ls.append(tmp[j])
    ls.append("#")
    whites += tmp.count(".")
    s.append(ls)
s.append(["#"] * (w+2))
l = collections.deque()
#print(time.time() - st)
if bfs(s,l):
    print(whites - s[h][w]-1)

else:
    print(-1)
print(time.time() - st)

Submission status: Wrong Answer

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

visited = [[-1] * w for _ in range(h)]
visited[0][0] = 1

black = 0

for i in grid :
    black += i.count('#')
                     
queue = deque([[0,0]])

while queue:
    x,y = queue.popleft()
    if x == h -1  and y == w - 1:
        break
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
        nx,ny = x+i,y+j
        if nx < 0 or ny <0 or nx >= h or ny >= w:
            continue
        if grid[nx][ny] == '.' and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx,ny])
            
ans = h*w - visited[h-1][w-1] - black


print(ans)

Submission status: Wrong Answer

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

s = list([list(input()) for i in range(H)])
dist = list([[-1 for j in range(W)] for i in range(H)])

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

while q.empty() != True:
  x, y = map(int, q.get())
  for i in range(-1,2):
    for j in range(-1,2):
      if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and s[nx][ny] == '.' and dist[nx][ny] == -1:
          dist[nx][ny] = dist[x][y] + 1
          s[nx][ny] = str(dist[x][y] + 1)
          q.put([nx,ny])

dCount = set()
wallCount = 0
notShortest = 0
goal = dist[H-1][W-1]
for i in s:
  for j in range(len(i)):
    if i[j] =='#':
      wallCount += 1
    elif i[j] == '.':
      pass
    elif goal < int(i[j]):
      pass
    else:
      dCount.add(i[j])
print( H*W - wallCount - goal - 1)
# for i in s:
  # print("".join(i))

Submission status: Wrong Answer

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

s = list([list(input()) for i in range(H)])
dist = list([[-1 for j in range(W)] for i in range(H)])

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

while q.empty() != True:
  x, y = map(int, q.get())
  for i in range(-1,2):
    for j in range(-1,2):
      if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and s[nx][ny] == '.' and dist[nx][ny] == -1:
          dist[nx][ny] = dist[x][y] + 1
          s[nx][ny] = str(dist[x][y] + 1)
          q.put([nx,ny])

dCount = set()
wallCount = 0
notShortest = 0
goal = dist[H-1][W-1]
for i in s:
  for j in range(len(i)):
    if i[j] =='#':
      wallCount += 1
    elif i[j] == '.':
      pass
    elif goal < int(i[j]):
      pass
    else:
      dCount.add(i[j])
print(H*W - wallCount - len(dCount))
# for i in s:
  # print("".join(i))

Submission status: Wrong Answer

Solution code:
from collections import deque, namedtuple

P = namedtuple('p', 'y x')
# moves are up, right, down or left
moves = [P(-1, 0), P(0, 1), P(1, 0), P(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
s = P(0, 0)
g = P(h - 1, w - 1)
S[s.y][s.x] = 0
d = deque()
d.append(s)
reach_goal = False
while len(d) != 0:
    cur = d.pop()
    if cur == g:
        reach_goal = True
        break
    for move in moves:
        nxt = P(cur.y + move.y, cur.x + move.x)
        can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and S[nxt.y][nxt.x] == '.'
        if can_move:
            S[nxt.y][nxt.x] = S[cur.y][cur.x] + 1
            d.append(nxt)
if reach_goal:
    sharp_cnt = 0
    for S_ in S:
        for S__ in S_:
            if S__ == '#':
                sharp_cnt += 1
    ans = h * w - (sharp_cnt + S[g.y][g.x] + 1)
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int,input().split())
field = [list(input()) for i in range(h)]
seen = [[False]*w for i in range(h)]
dis = [[0]*w for i in range(h)]

sx, sy = 0, 0
gx, gy = h-1, w-1

que = deque([[sx, sy]])

while len(que) != 0:
    x, y = que.popleft()
    for i, j in ([1,0], [0,1], [-1,0], [0,-1]):
        px, py = x+i, y+j
        
        if px < 0 or px > h-1 or py < 0 or py > w-1:
            continue
        
        if field[px][py] == '#':
            continue
        
        if seen[px][py]:
            continue
        
        else:
            dis[px][py] = dis[x][y] + 1
            seen[px][py] = True
            que.append([px, py])

c_dot = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            c_dot += 1

print(c_dot-dis[gx][gy]-1)

Submission status: Wrong Answer

Solution code:

from collections import deque

def bfs(sx, sy, gx, gy):
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = deque([(sx, sy)])
    dist = [[0] * W for _ in range(H)]
    dist[sy][sx] = 1
    while queue:
        x, y = queue.popleft()
        for dirs in directions:
            nx = x + dirs[0]
            ny = y + dirs[1]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if maze[ny][nx] == '#':
                continue

            if dist[ny][nx] == 0:
                dist[ny][nx] = dist[y][x] + 1
                queue.append((nx, ny))
            if nx == gx and ny == gy:
                return dist[gy][gx]
    return -1

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt = 0
for i in range(H):
    cnt += maze[i].count('#')
ans = bfs(0, 0, W-1, H-1)
score = H * W - cnt - ans
print(score)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dist = [[-1 for i in range(w)] for j in range(h)]
dist[0][0] = 0
queue = deque([[0, 0]])
while len(queue) != 0:
    now = queue.popleft()
    if now[1] != w-1:
        if dist[now[0]][now[1]+1] == -1 and s[now[0]][now[1]+1] == ".":
            dist[now[0]][now[1]+1] = dist[now[0]][now[1]] + 1
            queue.append([now[0],now[1] + 1])
    if now[0] != h-1:
        if dist[now[0] + 1][now[1]] == -1 and s[now[0]+1][now[1]] == ".":
            dist[now[0]+1][now[1]] = dist[now[0]][now[1]] + 1
            queue.append([now[0] + 1,now[1]])
if dist[h-1][w-1] == -1:
    print(-1)
else:
    length = dist[h-1][w-1] + 1
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans += 1
    ans -= length
    print(ans)