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(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
visit =[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
        return 0
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0, 1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
visit =[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
        return 0
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0, 1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
visit =[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0, 1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
visit =[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        visit[x][y] = 1
        global dist
        if n < dist:
            dist = n
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0, 1)
if not visit[H-1][W-1]:
    print(-1)
else:
    print(white - dist)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

def main():
    H, W = [int(e) for e in input().split()]
    S = [0 for _ in range(H)]
    for i in range(H):
        S[i] = list(input())

    dp = [[0 for _ in range(W)] for _ in range(H)]
    w = 0
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if S[i][j] == ".":
                w += 1
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1

    res = w - dp[H-1][W-1]
    print(res if dp[H-1][W-1] != 0 else -1)


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

def main():
    H, W = [int(e) for e in input().split()]
    S = [0 for _ in range(H)]
    for i in range(H):
        S[i] = list(input())

    dp = [[0 for _ in range(W)] for _ in range(H)]
    w = 0
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if S[i][j] == ".":
                w += 1
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1

    print(w - dp[H-1][W-1])


main()

Submission status: Wrong Answer

Solution code:
R,C = map(int,input().split())

maze = []
for i in range(R):
    maze.append(input())

def bfs(sx,sy,gx,gy):
    queue = []
    queue.append([sx,sy])

    visited = [ [ float("inf") for i in range(C)] for j in range(R)]
    visited[sx][sy] = 0

    while queue:
        p = queue.pop(0)

        if gx == p[0] and gy == p[1]:
            break

        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = p[0] + d[0]
            ny = p[1] + d[1]

            if 0 <= nx and 0 <= ny and nx < R and ny < C and maze[nx][ny] == "." and visited[nx][ny] == float("inf"):
                queue.append([nx,ny])
                visited[nx][ny] = visited[p[0]][p[1]] + 1
    return visited[gx][gy]

k = bfs(0,0,R-1,C-1)
c = 0
for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            c += 1
print(c - k - 1)

Submission status: Wrong Answer

Solution code:


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    start = (0, 0)

    now_data = set()
    now_data.add(start)
    next_data = set()
    pre_data = set()
    pre_data.add(start)

    move_tada = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while len(now_data) > 0:
        for now_x, now_y in now_data:
            for add_x, add_y in move_tada:
                move_x, move_y = now_x + add_x, now_y + add_y
                if 0 <= move_x < high and 0 <= move_y < width:
                    if data[move_x][move_y] == '.' and (move_x, move_y) not in pre_data:
                        ok_data = (move_x, move_y)
                        pre_data.add(ok_data)
                        next_data.add(ok_data)
        now_data = next_data
        next_data = set()

    if (high - 1, width - 1) in pre_data:
        white_data = 0
        for i in range(high):
            white_data += data[i].count('.')
        print(white_data - high - width + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
check = [[False]*W for _ in range(H)]
ans = [[0]*W for _ in range(H)]

q = deque()
q.append([0,0])
check[0][0] = True

while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if not check[next_i][next_j] and l[next_i][next_j] != '#':
                q.append([next_i,next_j])
                check[next_i][next_j] = True
                ans[next_i][next_j] = ans[i][j]+1

cnt = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '.':
            cnt += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
check = [[False]*W for _ in range(H)]
ans = [[0]*W for _ in range(H)]

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

while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if not check[next_i][next_j] and l[next_i][next_j] != '#':
                q.append([next_i,next_j])
                check[next_i][next_j] = True
                ans[next_i][next_j] = ans[i][j]+1

cnt = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '.':
            cnt += 1

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
inf=10**3
T=[[] for _ in range(h+2)]
T[0]=["#" for _ in range(w+2)]
T[h+1]=["#" for _ in range(w+2)]
for i in range(h):
  T[i+1]=["#"]+[inf if _!="#" else "#" for _ in input()]+["#"]
count=0
for t in T:
  count+=t.count("#")
count-=(2*(h+2)+2*w)
T[1][1]=0
Chk=[[1,1]]
while len(Chk)>0:
  c=Chk.pop(0)
  x,y=c[0],c[1]
  if T[x-1][y]!="#" and T[x-1][y]>T[x][y]+1:
    T[x-1][y]=T[x][y]+1
    Chk.append([x-1,y])
  if T[x][y-1]!="#" and T[x][y-1]>T[x][y]+1:
    T[x][y-1]=T[x][y]+1
    Chk.append([x,y-1])
  if T[x+1][y]!="#" and T[x+1][y]>T[x][y]+1:
    T[x+1][y]=T[x][y]+1
    Chk.append([x+1,y])
  if T[x][y+1]!="#" and T[x][y+1]>T[x][y]+1:
    T[x][y+1]=T[x][y]+1
    Chk.append([x,y+1])
print(h*w-count-T[h][w]-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = [input() for x in range(h)]
idou = ([1,0],[0,1],[-1,0],[0,-1])
min_step = [[0 for x in range(w)] for i in range(h)]
next_node = [(0,0)]
past_node = []
min_step[next_node[0][0]][next_node[0][1]] = 1
while next_node:
    for a in idou:
        hei = next_node[0][0] + a[0]
        wei = next_node[0][1] + a[1]
        try:
            if (maze[hei][wei] == "#")|(hei<0)|(wei<0)|(hei>=h)|(wei>=w)|((hei,wei) in past_node):
                continue
            else:
                past_node.append((hei,wei))
                if min_step[hei][wei] != 0:
                    continue
                else:
                    min_step[hei][wei] = min_step[next_node[0][0]][next_node[0][1]]+1
                next_node.append((hei,wei))
        except IndexError:
            continue
    next_node.pop(0)
dupulicate_val = []
count = 0
if min_step[h-1][w-1] == 0:
  print(-1)
else:
  for x in min_step:
    for y in x:
        if (y in dupulicate_val)&(y != 0):
            count += 1
        dupulicate_val.append(y)
  print(count)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = [input() for x in range(h)]
idou = ([1,0],[0,1],[-1,0],[0,-1])
min_step = [[0 for x in range(w)] for i in range(h)]
next_node = [(0,0)]
past_node = []
min_step[next_node[0][0]][next_node[0][1]] = 1
while next_node:
    for a in idou:
        hei = next_node[0][0] + a[0]
        wei = next_node[0][1] + a[1]
        try:
            if (maze[hei][wei] == "#")|(hei<0)|(wei<0)|(hei>=h)|(wei>=w)|((hei,wei) in past_node):
                continue
            else:
                past_node.append((hei,wei))
                if min_step[hei][wei] != 0:
                    continue
                else:
                    min_step[hei][wei] = min_step[next_node[0][0]][next_node[0][1]]+1
                next_node.append((hei,wei))
        except IndexError:
            continue
    next_node.pop(0)
dupulicate_val = []
count = 0
for x in min_step:
    for y in x:
        if (y in dupulicate_val)&(y != 0):
            count += 1
        dupulicate_val.append(y)
print(count)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s =[input() for i in range(h)]
from collections import defaultdict,deque
q =deque()
checked = {}
checked[(0,0)] =1
dd = ((0,1),(1,0),(-1,0),(0,-1))
q.append((1,0,0))
flag =False
while q:
    cnt ,i, j =q.popleft()
    for di,dj in dd:
        if i + di == h - 1 and j + dj == w - 1:
            cnt +=1
            flag = True
            break
        else:
            if 0 <= i + di <= h-1 and 0 <= j + dj <= w-1 and (i + di, j + dj) not in checked:
                checked[(i +di,j+ dj)] = 1
                if s[i + di][j + dj] == '.':
                    q.append((cnt + 1,i + di ,j + dj))
if flag:
    b = sum([s.count('#') for s in s])
    print(w * h - cnt- b)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W = [ int(it) for it in input().split() ]
x = np.array([ [0 if v == "." else 1 for v in input() ] for i in range(H)]).astype(np.int32)
Close = np.zeros(x.shape).astype(np.int32)
fcost = np.zeros(x.shape).astype(np.int32)


gx,gy=(x.shape[0]-1,x.shape[1]-1  )

Open=[(0,0,gx+gy)]
dw=[[0,1],[0,-1],[1,0],[-1,0]]

FLAG_END = False
for i in range(10000000):
    if ( len(Open)==0):
        print (-1)
        break
    Open.sort(key=lambda x:-x[2])
    nx,ny,_= Open.pop()
    Close[nx,ny]=1
    for dx,dy in dw:
        mx,my=nx+dx,ny+dy
        if ( 0<=mx and mx<x.shape[0] and  0<=my and my<x.shape[1] ):
            if ( Close[mx,my] == 0 and x[mx,my]==0 ):
                fcost[mx,my]=fcost[nx,ny]+1
                Open.append( (mx,my,abs(mx-gx)+abs(my-gy)+fcost[mx,my])  )   
                if (mx==gx and my==gy):
                    FLAG_END = True
    if (FLAG_END):
        break
if (FLAG_END):
    print (x.shape[0]*x.shape[1]-np.sum(x)-fcost[gx,gy]-1 )

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

current_list = [(0, 0)]
count = 1
judge = False
while len(current_list) > 0:
    count += 1
    next_list = []
    for y,x in current_list:
        if x == W-1 and y == H-1:
            judge = True
            break
        for i,j in ((1,0),(0,1)):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    current_list = list(set(next_list))
    if judge:
        break
else:
    count = -1
if count > 0:
    print(H*W-pre-count+1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

current_list = [(0, 0)]
count = 1
 
while C[H-1][W-1] == '.' or count <= 3000:
    count += 1
    next_list = []
    for y,x in current_list:
        for i,j in ((1,0),(0,1)):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    current_list = list(set(next_list))
if count >= 3000:
    print(-1)
else:
    print(H*W-pre-count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
# from pprint import pprint
# import statistics
import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()

h, w = MI()
s = [IS() for _ in range(h)]
q = deque()
x_diff = [-1, 0, 1, 0]
y_diff = [0, 1, 0, -1]
require = [[0 for i in range(w)] for j in range(h)]
check = [[0 for i in range(w)] for j in range(h)]

all_grid = h * w
sharp_count = 0
for i in range(h):
    sharp_count += s[i].count('#')

q.append([0, 0])
check[0][0] = 1

while len(q) != 0:
    tmp_y, tmp_x = q.popleft()
    for i in range(4):
        next_y = tmp_y + y_diff[i]
        next_x = tmp_x + x_diff[i]
        if ( 0 <= next_x <= w-1
            and 0 <= next_y <= h-1
            and check[next_y][next_x] == 0
            and s[next_y][next_x] != '#'):
                check[next_y][next_x] = 1
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])

hosuu = require[h-1][w-1]
# print(hosuu)
# require = [[str(require[j][i]).zfill(2) for i in range(w)] for j in range(h)]
# pprint(require, width=400)
print(all_grid - sharp_count - hosuu -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
field = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
black = 0
for l in field:
    black += l.count("#")
q = deque([])
q.append([0, 0])
visited[0][0] = 1
is_goal = False

while q:
    y, x = q.popleft()
    wave = visited[y][x]


    def enque(y, x):
        global ans
        global is_goal
        if 0 <= y < H and 0 <= x < W:
            if visited[y][x] == 0:
                visited[y][x] = wave + 1
                q.append([y, x])
            if y == H-1 and x == W-1:
                ans = H*W - visited[y][x] - black
                is_goal = True

    enque(y+1, x)
    enque(y, x+1)
    enque(y, x-1)
    enque(y-1, x)

if is_goal:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from queue import Queue


def main():
    H, W = map(int, input().split())

    white = 0

    grid = [[-1 for _ in range(W + 2)]]
    for _ in range(H):
        line = input()
        white += line.count(".")
        grid.append([-1] + [-1 if char == "#" else -2 for char in line] + [-1])
    grid.append([-1 for _ in range(W + 2)])

    grid[1][1] = 0

    tosearch = Queue()
    tosearch.put((1, 1))

    movement = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while not tosearch.empty():
        y, x = tosearch.get()

        if (y, x) == (H, W):
            break

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.put((ny, nx))
    else:
        print(-1)
        
    print(white - (grid[H][W] + 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from queue import Queue


def main():
    H, W = map(int, input().split())

    white = 0

    grid = [[-1 for _ in range(W + 2)]]
    for _ in range(H):
        line = input()
        white += line.count(".")
        grid.append([-1] + [-1 if char == "#" else -2 for char in line] + [-1])
    grid.append([-1 for _ in range(W + 2)])

    grid[1][1] = 0

    tosearch = Queue()
    tosearch.put((1, 1))

    movement = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while not tosearch.empty():
        y, x = tosearch.get()

        if (y, x) == (H, W):
            break

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.put((ny, nx))

    print(white - (grid[H][W] + 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from queue import Queue


def main():
    H, W = map(int, input().split())

    black = 0

    grid = [[-1 for _ in range(W + 2)]]
    for _ in range(H):
        line = input()
        black += line.count("#")
        grid.append([-1] + [-1 if char == "#" else -2 for char in line] + [-1])
    grid.append([-1 for _ in range(W + 2)])

    grid[1][1] = 0

    tosearch = Queue()
    tosearch.put((1, 1))

    movement = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while not tosearch.empty():
        y, x = tosearch.get()

        if (y, x) == (H, W):
            break

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.put((ny, nx))

    print(H * W - (grid[H][W] + 1) - black)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

H,W=map(int,input().split())
G=[list() for i in range(H*W)]
s=[]
for j in range(H):
    s.extend(input())

for i in range(H):
    for j in range(W):
        if(j<W-1 and s[W*i+j]=="."and  s[W*i+j+1]=="."):
            G[W*i+j].append(edge(W*i+j+1,1))
        if(i<H-1 and s[W*i+j]=="." and s[W*i+j+W]=="."):
            G[W*i+j].append(edge(W*i+j+W,1))
    

def dijkstra(o):
    d=[float('inf') for i in range(H*W)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(H*W)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev


ans=set()
for i in range(1):
    tmp=dijkstra(i)[0]
    if(tmp[H*W-1]==float('inf')):
        print(-1)
    else:
        #-1:start
        print(H*W-s.count('#')-1-tmp[H*W-1])

Submission status: Wrong Answer

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

H,W=map(int,input().split())
G=[list() for i in range(H*W)]
s=[]
for j in range(H):
    s.extend(input())

for i in range(H):
    for j in range(W):
        if(j<W-1 and s[W*i+j]=="."and  s[W*i+j+1]=="."):
            G[W*i+j].append(edge(W*i+j+1,1))
        if(i<H-1 and s[W*i+j]=="." and s[W*i+j+W]=="."):
            G[W*i+j].append(edge(W*i+j+W,1))
    

def dijkstra(o):
    d=[float('inf') for i in range(H*W)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(H*W)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev


ans=set()
for i in range(1):
    tmp=dijkstra(i)[0]
    if(tmp[H*W-1]==float('inf')):
        print(-1)
    else:
        #-1:start
        print(s.count('.')-1-tmp[H*W-1])

Submission status: Wrong Answer

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

H,W=map(int,input().split())
G=[list() for i in range(H*W)]
s=[]
for j in range(H):
    s.extend(input())

for i in range(H):
    for j in range(W):
        if(j<W-1 and s[W*i+j+1]=="."):
            G[W*i+j].append(edge(W*i+j+1,1))
        if(i<H-1 and s[W*i+j+W]=="."):
            G[W*i+j].append(edge(W*i+j+W,1))
    

def dijkstra(o):
    d=[float('inf') for i in range(H*W)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(H*W)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev


ans=set()
for i in range(1):
    tmp=dijkstra(i)[1]
    if(len(tmp[H*W-1])==0):
        print(-1)
    else:
        #-1:start
        print(s.count('.')-1-len(tmp[H*W-1]))

Submission status: Wrong Answer

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print ('-1')
else:
    print (count - a - 1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        px = q.get()
        py = q.get()
        if px == H-1 and py == W-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print ('-1')
else:
    print (count - a - 1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        px = q.get()
        py = q.get()
        if px == H-1 and py == W-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)