Problem:


Score: 400 points

Problem statement

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

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

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

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

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

Constraints

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

209



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


Sample output:
2

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
grid = []
for i in range(h):
  grid += input().split()

# count '.'
dots = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == '.':
      dots += 1

# search shortest path
costs = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
  for j in range(w):
    if i == 0:
      if j != 0:
        if costs[i][j - 1] == -1 or grid[i][j] == '#':
          costs[i][j] = -1
        else:
          costs[i][j] = costs[i][j - 1] + 1
      else:
        costs[i][j] = 1
    else:
      if j == 0:
        if costs[i - 1][j] == -1 or grid[i][j] == '#':
          costs[i][j] = -1
        else:
          costs[i][j] = costs[i - 1][j] + 1
      else:
        if grid[i][j] == '#':
          costs[i][j] = -1
        else:
          if costs[i - 1][j] == -1:
            if costs[i][j - 1] == -1:
              costs[i][j] = -1
            else:
              costs[i][j] = costs[i][j - 1] + 1
          elif costs[i][j - 1] == -1:
            costs[i][j] = costs[i - 1][j] + 1
          else:
            if costs[i - 1][j] < costs[i][j - 1]:
              costs[i][j] = costs[i - 1][j] + 1
            else:
              costs[i][j] = costs[i][j - 1] + 1

#print(dots, costs)
print(dots - costs[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
import heapq

def change(i):
    if i == ".":
        return 256
    return -1

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

maze = []

for _ in range(h):
    maze.append([change(i) for i in input()])

B = 0
for _ in maze:
    B += _.count(-1)

l = []

maze[0][0] = 1
heapq.heappush(l, (1, 0, 0))
while len(l) > 0:
    S, H, W = heapq.heappop(l)
    if (H, W) == (h-1, w-1):
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if maze[H][W]+1 < maze[y][W]:
                maze[y][W] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-y+w-W,y, W))
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if maze[H][W]+1 < maze[H][x]:
                maze[H][x] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-H+w-x, H, x))

if maze[-1][-1] == -1:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
import functools
import itertools
import math

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = []
    unvisited = [(1,1)]
    cost[1][1] = 1
    while unvisited:
        now = unvisited[0]
        unvisited = unvisited[1:]
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]+1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    print(white)
    print(step)
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import functools
import itertools
import math

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = []
    unvisited = [(1,1)]
    cost[1][1] = 1
    while unvisited:
        now = unvisited[0]
        unvisited = unvisited[1:]
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]-1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    print(white - step)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def change(i):
    if i == ".":
        return 256
    return -1
 
h, w = map(int, input().split())
 
maze = []
 
for _ in range(h):
    maze.append([change(i) for i in input()])
 
B = 0
for _ in maze:
    B += _.count(-1)
 
l = []
 
l.append([0,0])
maze[0][0] = 1
while len(l) > 0:
    H, W = l[0]
    if H == h and W == w:
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if maze[H][W] < maze[y][W]:
                maze[y][W] = maze[H][W]+1
                l.append([y,W])
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if maze[H][W] < maze[H][x]:
                maze[H][x] = maze[H][W]+1
                l.append([H,x])
    l.pop(0)
 
if maze[-1][-1] == 0:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Submission status: Wrong Answer

Solution code:
def change(i):
    if i == ".":
        return 512
    return -1

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

maze = []

for _ in range(h):
    maze.append(list(map(change, input())))

B = 0
for _ in maze:
    B += _.count(-1)

l = []

maze[0][0] = 1
l.append([0,0, maze[0][0]])
while len(l) > 0:
    H, W, S = l[0]
    if H == h and W == w:
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if S < maze[y][W]:
                maze[y][W] = S+1
                l.append([y,W, maze[y][W]])
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if S < maze[H][x]:
                maze[H][x] = S+1
                l.append([H,x, maze[H][x]])
    l.pop(0)
    l.sort(key=lambda x:x[2])

if maze[-1][-1] == 0:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Submission status: Wrong Answer

Solution code:
def change(i):
    if i == ".":
        return 256
    return -1

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

maze = []

for _ in range(h):
    maze.append(list(map(change, input())))

B = 0
for _ in maze:
    B += _.count(-1)

l = []

l.append([0,0])
maze[0][0] = 1
while len(l) > 0:
    H, W = l[0]
    if H == h and W == w:
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if maze[H][W] < maze[y][W]:
                maze[y][W] = maze[H][W]+1
                l.append([y,W])
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if maze[H][W] < maze[H][x]:
                maze[H][x] = maze[H][W]+1
                l.append([H,x])
    l.pop(0)

if maze[-1][-1] == 0:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
#@document_it
from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function
###########################

#@document_it
#O(1)のはず
def nb(i,j,H,W):
    ans = []
    a = i+1
    b = i-1
    c = j+1
    d = j-1
    if a >= 0 and a <= H-1:
        ans.append((a,j))
    if b >= 0 and b <= H-1:
        ans.append((b,j))
    if c >= 0 and c <= W-1:
        ans.append((i,c))
    if d >= 0 and d <= W-1:
        ans.append((i,d))
    return ans
        

def e():
    #入力データ整理
    dist={}
    white = {}
    wtotal = 0
    H,W = map(int,input().split())
    for i in range(H):
        row = input()
        for j in range(W):
            dist[(i,j)] = -1
            if row[j] == '.':
                white[(i,j)] = True
                wtotal += 1
            else:
                white[(i,j)] = False
    #リンク作成
    #tuple -> [tuple]
    #リンクの数は最大でも頂点の4倍なのでO(HW)
    link = {}
    for i in range(H):
        for j in range(W):
            link[(i,j)] = []
            if not white[(i,j)]:
                continue
            else:
                nlist = nb(i,j,H,W)
                for p in nlist:
                    if white[p]:
                        link[(i,j)].append(p)
    
    q = deque()
    dist[(0,0)] = 1
    q.append((0,0))
    while q:
        v = q.popleft()
        for w in link[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + 1
                q.append(w)
                #print(w,dist[w])
    if dist[(H-1,W-1)] != -1:
        ans = wtotal - dist[(H-1,W-1)]
    else:
        ans = -1
    print(wtotal)
    print(dist[(H-1,W-1)])
                    
    print(ans)

###########################
if __name__ == '__main__':
    e()

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
from operator import mul

# 整数Nを桁ごとのリストにする
# l = [int(x) for x in list(str(N))]

# リストliから重複を削除したリストli_uniqを作成
#li_uniq = []
#for i in li:
#    if x not in li_uniq:
#        li_uniq.append(x)

# 複数行のinput - list版
#list = [list(map(int, input().split())) for i in range(N)]
# 複数行のinput - dictionary版
# key = a, value = b
#for i in range(N):
#    a, b = map(int, input().split())
#    dict[a] = b


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

# 最短距離を初期化
INF = 100000000000
distance = [[INF for i in range(W)] for j in range(H)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]

def bfs(sh, sw, gh, gw, maze):
    # 迷路の大きさ
    field_height = len(maze)
    field_width = len(maze[0])

    queue = []
    # キューにスタート地点を追加
    queue.insert(0, (sh, sw))
    # スタート地点からスタート地点までの距離はゼロ
    distance[sh][sw] = 0
    # キューから要素がなくなる＝探索が終わる
    while len(queue):
        h, w = queue.pop()
        # ゴールに到着で終了
        if h == gh and w == gw:
            break
        for i in range(4):
            # ゴールに到着しなければ1つ移動
            nh, nw = h + dh[i], w + dw[i]
            if (0 <= nh and nh < field_height and 0 <= nw and nw < field_width and maze[nh][nw] != '#' and distance[nh][nw] == INF):
                queue.insert(0, (nh, nw))
                distance[nh][nw] = distance[h][w] + 1
    return distance[gh][gw]

# 黒マスに変えられない白マス数＝最短経路長＋1（出発店＝白マス）
shortest_path = bfs(0,0,H-1,W-1,S) + 1

# 白マスの全数
n_w = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            n_w += 1

if shortest_path == INF:
    print(-1)
else:
    print(n_w - shortest_path)

Submission status: Wrong Answer

Solution code:
def func():
   H,W = list(map(int, input().split()))
   s = []
   for i in range(H):
      s.append(input())
   b = 0
   for i in range(H):
      for j in range(W):
         if s[i][j] == "#":
            b = b + 1

   conf = [[0 for _ in range(W)] for _ in range(H)]
   cost = [[False for _ in range(W)] for _ in range(H)]
   conf[0][0] = 1
   cost[0][0] = 0
   
   Q = [(0,0)]
   node_count = []
   while Q != []:
      node = Q.pop(0)
      if node[0] != 0:
         if (s[node[0]-1][node[1]]==".")and(conf[node[0]-1][node[1]]==0):
               if (cost[node[0]-1][node[1]]==False)or(cost[node[0]-1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]-1][node[1]] = new_cost
                  node_count.append([new_cost, node[0]-1, node[1]])
      if node[0] != H-1:
         if (s[node[0]+1][node[1]]==".")and(conf[node[0]+1][node[1]]==0):
               if (cost[node[0]+1][node[1]]==False)or(cost[node[0]+1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]+1][node[1]] = new_cost
                  node_count.append([new_cost, node[0]+1, node[1]])
      if node[1] != 0:
         if (s[node[0]][node[1]-1]==".")and(conf[node[0]][node[1]-1]==0):
               if (cost[node[0]-1][node[1]]==False)or(cost[node[0]-1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]][node[1]-1] = new_cost
                  node_count.append([new_cost, node[0], node[1]-1])
      if node[1] != W-1:
         if (s[node[0]][node[1]+1]==".")and(conf[node[0]][node[1]+1]==0):
               if (cost[node[0]][node[1]+1]==False)or(cost[node[0]][node[1]+1]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]][node[1]+1] = new_cost
                  node_count.append([new_cost, node[0], node[1]+1])

      if node_count != []:
         node_count.sort()
         node_conf = node_count.pop(0)
         conf[node_conf[1]][node_conf[2]] = 1
         Q.append((node_conf[1], node_conf[2]))
         if conf[H-1][W-1] == 1:
            return H*W - (b + cost[H-1][W-1] +1)

   return -1

print(func())

Submission status: Wrong Answer

Solution code:
def func():
   H,W = list(map(int, input().split()))
   s = []
   for i in range(H):
      s.append(input())
   b = 0
   for i in range(H):
      for j in range(W):
         if s[i][j] == "#":
            b = b + 1

   conf = [[0 for _ in range(W)] for _ in range(H)]
   cost = [[False for _ in range(W)] for _ in range(H)]
   conf[0][0] = 1
   cost[0][0] = 0
   
   Q = [(0,0)]
   node_count = []
   while Q != []:
      node = Q.pop(0)
      if node[0] != 0:
         if (s[node[0]-1][node[1]]==".")and(conf[node[0]-1][node[1]]==0):
               if (cost[node[0]-1][node[1]]==False)or(cost[node[0]-1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]-1][node[1]] = new_cost
                  Q.append((node[0]-1, node[1]))
                  node_count.append([new_cost, node[0]-1, node[1]])
      if node[0] != H-1:
         if (s[node[0]+1][node[1]]==".")and(conf[node[0]+1][node[1]]==0):
               if (cost[node[0]+1][node[1]]==False)or(cost[node[0]+1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]+1][node[1]] = new_cost
                  Q.append((node[0]+1, node[1]))
                  node_count.append([new_cost, node[0]+1, node[1]])
      if node[1] != 0:
         if (s[node[0]][node[1]-1]==".")and(conf[node[0]][node[1]-1]==0):
               if (cost[node[0]-1][node[1]]==False)or(cost[node[0]-1][node[1]]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]][node[1]-1] = new_cost
                  Q.append((node[0], node[1]-1))
                  node_count.append([new_cost, node[0], node[1]-1])
      if node[1] != W-1:
         if (s[node[0]][node[1]+1]==".")and(conf[node[0]][node[1]+1]==0):
               if (cost[node[0]][node[1]+1]==False)or(cost[node[0]][node[1]+1]>cost[node[0]][node[1]]+1):
                  new_cost = cost[node[0]][node[1]]+1
                  cost[node[0]][node[1]+1] = new_cost
                  Q.append((node[0], node[1]+1))
                  node_count.append([new_cost, node[0], node[1]+1])

      if node_count != []:
         node_count.sort()
         node_conf = node_count.pop(0)
         conf[node_conf[1]][node_conf[2]] = 1
         if conf[H-1][W-1] == 1:
            return H*W - (b + cost[H-1][W-1] +1)

   return -1

print(func())

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
cnt = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        cnt+=1
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
ans = cnt - dp[H-1][W-1]
if(ans < 0): 
    print(0)
elif(dp[H-1][W-1] < 0): 
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
cnt = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        cnt+=1
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
if(dp[H-1][W-1] < 0): 
    print(-1)
else:
    print(cnt - dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
count=0
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0)):
            continue
        cnt+=1
if(dp[H-1][W-1] < 0): 
    print(-1)
else:
    print(cnt - dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split()) 
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            cnt+=1
if(dp[H-1][W-1] not in dic or dp[H-1][W-1] < 0):                                                                                                                     
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split()) 
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            cnt+=1
if(dp[H-1][W-1] not in dic or dp[H-1][W-1] >=0):
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            cnt+=1
if(dp[H-1][W-1] not in dic or dic[dp[H-1][W-1]] !=1):
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0) or (i,j) == (H-1,W-1)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            cnt+=1
if(dp[H-1][W-1] < 0): 
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
if(dp[H-1][W-1] < 0): 
    print(-1)
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0) or (i,j) == (H-1,W-1)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
            grid[i][j] ="+"
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            grid[i][j] ="+"
            cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
if(dp[H-1][W-1] < 0): 
    print(-1)
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0) or (i,j) == (H-1,W-1)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
            grid[i][j] ="+"
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            grid[i][j] ="+"
            cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
lst = []
for _ in range(H):
    lst.append(input())

A = []
whites = 0

for i in range(H):
    row_i = []
    for j in range(W):
        if lst[i][j] == '.':
            whites += 1
            tmp = []
            if i != 0:
                if lst[i-1][j] == '.':
                    tmp.append((i-1, j))
            if j != 0:
                if lst[i][j-1] == '.':
                    tmp.append((i, j-1))
            if i != H-1:
                if lst[i+1][j] == '.':
                    tmp.append((i+1, j))
            if j != W-1:
                if lst[i][j+1] == '.':
                    tmp.append((i, j+1))
            row_i.append(tmp)
        else:
            row_i.append([])
    A.append(row_i)

Q = [(0, 0, 0)]
visited = []

while len(Q) != 0:
    x, y, path_length = Q.pop(0)
    if (x,y) == (H-1, W-1):
        print(whites - path_length - 1)
        break
    if (x,y) not in visited:
        visited.append((x,y))
        Q += [(i, j, path_length + 1) for (i, j) in A[x][y]]