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 = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
visited = set()
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if ((y + dy, x + dx) in visited and (dy < 0 or dy < 0)) or y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
visited = set()
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if (y + dy, x + dx) in visited and (dy < 0 or dy < 0):
            break
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
visited = set()
while len(queue) > 0:
    y, x = queue.pop()
    if (y, x) in visited:
        continue
    visited.add((y, x))
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 0 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[0 for i in range(W)] for j in range(H)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
visited = set()
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if (y + dy, x + dx) in visited:
            continue
        if not maze[y + dy][x + dx]:
            distances[y + dy][x + dx] = distances[y][x] + 1
            queue.append((y + dy, x + dx))
            if y + dy == H - 1 and x + dx == W - 1:
                queue = []
                break

if distances[H - 1][W - 1] == 0 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[-1 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
visited = set()
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if (y + dy, x + dx) in visited:
            continue
        if not maze[y + dy][x + dx]:
            distances[y + dy][x + dx] = distances[y][x] + 1
            queue.append((y + dy, x + dx))
            if y + dy == H - 1 and x + dx == W - 1:
                queue = []
                break

if distances[H - 1][W - 1] == -1:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[-1 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = []
queue.append((0, 0))
visited = set((0, 0))
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if (y + dy, x + dx) in visited:
            continue
        if not maze[y + dy][x + dx]:
            distances[y + dy][x + dx] = distances[y][x] + 1
            queue.append((y + dy, x + dx))
            if y + dy == H - 1 and x + dx == W - 1:
                queue = []
                break

if distances[H - 1][W - 1] == -1:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[-1 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = []
queue.append((0, 0))
visited = set((0, 0))
while len(queue) > 0:
    y, x = queue.pop()
    visited.add((y, x))
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if (y + dy, x + dx) in visited:
            continue
        if not maze[y + dy][x + dx]:
            distances[y + dy][x + dx] = distances[y][x] + 1
            queue.append((y + dy, x + dx))
            if y + dy == H - 1 and x + dx == W - 1:
                queue = []

if distances[H - 1][W - 1] == -1:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Wrong Answer

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

que=deque([(0,0,1)])
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x+1,y,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
List = []
queue = [(0,0)]
shape = 0
for i in range(H):
    x = input()
    shape += x.count('#')
    List.append(x)

def check(x,y):
    if(x > W-1 or y > H-1):
        return
    if(List[y][x] == '#'):
        return
    queue.append((x,y))
flag = -1
while(len(queue) != 0):
    x,y = queue[0]
    if x==W-1 and y==H-1:
        flag = 1
        break
    queue.pop(0)
    check(x+1,y)
    check(x, y+1)
if(flag == 1):
    print(H*W - (H-1 + W-1 + 1) - shape)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import time
from collections import deque
now=time.time()
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
    if time.time()-now > 1.5:
        print(-1)
        exit()
print(f if f==-1 else(h*w-f-bcount))

Submission status: Wrong Answer

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

que=[[0,0,1]]
used=[[0,0]]
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or [x,y] in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop()
    if x==w-1 and y==h-1:
        f=c
    used.append([x,y])
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Wrong Answer

Solution code:
import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '#':
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))
#print(dotsum)
#print(count)
if count > 0:
    print(dotsum - count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '#':
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))
print(dotsum)
print(count)
if count > 0:
    print(dotsum - count)
else:
    print(-1)

Submission status: Wrong Answer

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

start = (0, 0, 0)
q = [start]
white = 0
isGoal = False
n = 0                             # 処理回数

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            white += 1            # game開始前の白マスの数をカウント

while(len(q)):
    i, j, d = q.pop(0)
    if i < 0 or i >= h or j < 0 or j >= w \
       or s[i][j] == '#':
        continue                  # これ以降の処理はとばす
    elif i == h - 1 and j == w - 1:
        isGoal = True
        break
    for ni, nj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        q.append((i+ni, j+nj, n+1))

print(white-d-1 if isGoal else -1)

Submission status: Wrong Answer

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

start = (0, 0, 0)
q = [start]
white = 0
isGoal = False
n = 0                             # 処理回数
    
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            white += 1            # game開始前の白マスの数をカウント

while(len(q)):
    i, j, d = q.pop(0)
    if i < 0 or i >= h or j < 0 or j >= w \
       or s[i][j] == '#':
        continue                  # これ以降の処理はとばす
    elif i == h - 1 and j == w - 1:
        isGoal = True
        break
    for ni, nj in [(1, 0), (0, 1)]:
        q.append((i+ni, j+nj, n+1))

print(white-d-1 if isGoal else -1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(' '))
S = [input() for i in range(H)]
M = [[10000]*W for i in range(H)]
M[0][0] = 0
for k in range(H*W):
    for i in range(H):
        for j in range(W):
            if M[i][j] == k:
                if i > 0 and M[i-1][j] > k+1 and S[i-1][j] == '.':
                    M[i-1][j] = k+1
                if i < H-1 and M[i+1][j] > k+1 and S[i+1][j] == '.':
                    M[i+1][j] = k+1
                if j > 0 and M[i][j-1] > k+1 and S[i][j-1] == '.':
                    M[i][j-1] = k+1
                if j < W-1 and M[i][j+1] > k+1 and S[i][j+1] == '.':
                    M[i][j+1] = k+1
if M[-1][-1] == 10000:
    print(-1)
minDis = M[-1][-1] + 1
numWhite = 0
for line in S:
    numWhite += line.count('.')
print(numWhite-minDis)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
M = [["." for i in range(W)] for j in range(H)]
S = [input() for i in range(H)]

start = (0, 0, 0)
queue = [start]
white = 0

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

while(len(queue)):
    i, j, d = queue.pop(0)
    if i < 0 or i >= H or j < 0 or j >= W or M[i][j] == "#":
        continue
    elif i == H - 1 and j == W - 1:
        break
    M[i][j] = "#"
    for ni, nj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        queue.append((i+ni, j+nj, d+1))

print(white-d-1)

Submission status: Wrong Answer

Solution code:
import numpy as np

temp = input()
H,W = temp.split()
H = int(H)
W = int(W)
pref = np.zeros((H,W))
for i in range(H):
    row = input()
    for j in range(W):
        if row[j] == ".":
            pref[i][j] = 1
        else:
            pref[i][j] = 0
totalw = np.count_nonzero(pref)

a = np.zeros((H,W))     

quere = []
quere.append(0)
while quere != []:
    locas = quere[0]
    tempscore = (H+1)*(W+1)
    if locas % W > 0 :
        left = locas - 1
        if a[(left // W)][(left % W)] == 0 and pref[(left // W)][(left % W)] == 1:
            if left not in quere:
                quere.append(left)
        elif a[(left // W)][(left % W)] > 0:
            tempscore = min(tempscore,a[(left // W)][(left % W)])
    if locas % W < W-1:
        right = locas + 1
        if a[(right // W)][(right % W)] == 0 and pref[(right // W)][(right % W)] == 1:
            if right not in quere:
                quere.append(right)
        elif a[(right // W)][(right % W)] > 0:
            tempscore = min(tempscore,a[(right // W)][(right % W)])
    if locas // W > 0 :
        up = locas - W
        if a[(up // W)][(up % W)] == 0 and pref[(up // W)][(up % W)] == 1:
            if up not in quere:
                quere.append(up)
        elif a[(up // W)][(up % W)] > 0:
            tempscore = min(tempscore,a[(up // W)][(up % W)])
    if (locas // W) < (H - 1):
        down = locas + W
        if a[(down // W)][(down % W)] == 0 and pref[(down // W)][(down % W)] == 1:
            if down not in quere:
                quere.append(down)
        elif a[(down // W)][(down % W)] > 0:
            tempscore = min(tempscore,a[(down // W)][(down % W)])
    
    if locas == 0:tempscore=0
    
    a[(locas // W)][(locas % W)] = tempscore + 1
    quere.pop(0)
    

leng = a[H-1][W-1]

score = totalw-leng
print(int(score))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
h, w = map(int, raw_input().split())
# 文字列の入力
s = [raw_input() for i in range(h)]

accessible = [(0,0)]
accessible_now = [(0,0)]
n_black = sum([ss.count('#') for ss in s]) 

stroke = 1
while True:
  stroke += 1
  accessible_next = [] 
  for loc in accessible_now:
    for step in [(1,0),(0,1),(-1,0),(0,-1)]:
      loc_next = (loc[0]+step[0],loc[1]+step[1])
      if loc_next == (h-1,w-1):
        print h*w-n_black-stroke 
        exit(0)
      if ((-1 in loc_next) or (loc_next[0]==h) or (loc_next[1]==w)):
        continue
      if loc_next in accessible:
        continue
      if s[loc_next[0]][loc_next[1]] == '#':
        continue
      accessible.append(loc_next)
      accessible_next.append(loc_next)
    #print accessible_next
    if(len(accessible_next)==0):
      print -1
      exit(0) 
    accessible_now = accessible_next

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

class Node :
    def __init__(self, x, y, frm, h, cost) :
        self.x = x
        self.y = y
        self.frm = frm
        self.h = h
        self.cost = cost

    def __lt__(self, other) :
        return self.h < other.h

    def __le__(self, other) :
        return self.h <= other.h

def main() :
    H, W = map(int, input().split())
    s = []
    white = 0
    for i in range(H) :
        line = input()
        s.append(line)
        for c in line :
            if c == '.' :
                white += 1
    q = []
    heappush(q, Node(0, 0, -1, H+W-2, 0))

    while len(q) != 0 :
        now = heappop(q)
        frm = now.frm
        x = now.x
        y = now.y
        h = now.h
        cost = now.cost
        if h == 0 :
            print(white-1-cost)
            return

        if frm != 0 and y != 0 and s[y-1][x] == '.' :
            heappush(q, Node(x, y-1, 3, h+1, cost+1))
        if frm != 1 and x != 0 and s[y][x-1] == '.' :
            heappush(q, Node(x-1, y, 2, h+1, cost+1))
        if frm != 2 and x != W-1 and s[y][x+1] == '.' :
            heappush(q, Node(x+1, y, 1, h-1, cost+1))
        if frm != 3 and y != H-1 and s[y+1][x] == '.' :
            heappush(q, Node(x, y+1, 0, h-1, cost+1))

    print(-1)

main()

Submission status: Wrong Answer

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node.point)
  next_nodes = looking_node.get_next_nodes()
  if ID>=10000:
    break
  for n in next_nodes:
    ID+=1
    if not(n.point in checked):
      heapq.heappush(q,(distance(n.point)+len(n.operation),ID,n))
print(-1)

Submission status: Wrong Answer

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node.point)
  next_nodes = looking_node.get_next_nodes()
  for n in next_nodes:
    ID+=1
    if not(n.point in checked):
      heapq.heappush(q,(distance(n.point),ID,n))
print(-1)

Submission status: Wrong Answer

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node)
  next_nodes = looking_node.get_next_nodes()
  for n in next_nodes:
    ID+=1
    if not(n in checked):
      heapq.heappush(q,(distance(n.point),ID,n))
print(-1)

Submission status: Wrong Answer

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node)
  next_nodes = looking_node.get_next_nodes()
  for n in next_nodes:
    ID+=1
    if not(n in checked):
      heapq.heappush(q,(distance(n.point),ID,n))

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 = 10000000000000
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)