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: Runtime Error

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]
 
def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)
    
    return -1
 
 
whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []
 
for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1
 
a = []
 
for i in range(0,whitecount):
    b = []
    if [p[i][0]+1,p[i][1]] in p:
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if [p[i][0],p[i][1]+1] in p:
        b.append(p.index([p[i][0],p[i][1]+1]))
    if [p[i][0]-1,p[i][1]] in p:
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if [p[i][0],p[i][1]-1] in p:
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)
 
c = bf_search(0,whitecount-1,a)
 
if c == -1:
    print(-1)
else:
    print(whitecount - len(c))
 
 
def list_1d(d,v):
    return [ v for i in range(d)]

def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)
    
    return -1


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1

a = []

for i in range(0,whitecount):
    b = []
    if [p[i][0]+1,p[i][1]] in p:
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if [p[i][0],p[i][1]+1] in p:
        b.append(p.index([p[i][0],p[i][1]+1]))
    if [p[i][0]-1,p[i][1]] in p:
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if [p[i][0],p[i][1]-1] in p:
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)
 
c = bf_search(0,whitecount-1,a)

if c == -1:
    print(-1)
else:
    print(whitecount - len(c))

Submission status: Runtime Error

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]

def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1

a = []

for i in range(0,whitecount):
    b = []
    if p[i][0] < h - 1 and s[p[i][0]+1][p[i][1]] == '.':
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if p[i][1] < w - 1 and s[p[i][0]][p[i][1]+1] == '.':
        b.append(p.index([p[i][0],p[i][1]+1]))
    if p[i][0] > 0 and s[p[i][0]-1][p[i][1]] == '.':
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if p[i][1] > 0 and s[p[i][0]][p[i][1]-1] == '.':
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)


print(whitecount - len(bf_search(0,whitecount - 1,a)))

Submission status: Runtime Error

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]

def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1

a = []

for i in range(0,whitecount):
    b = []
    if p[i][0] < h - 1 and s[p[i][0]+1][p[i][1]] == '.':
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if p[i][1] < w - 1 and s[p[i][0]][p[i][1]+1] == '.':
        b.append(p.index([p[i][0],p[i][1]+1]))
    if p[i][0] > 0 and s[p[i][0]-1][p[i][1]] == '.':
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if p[i][1] > 0 and s[p[i][0]][p[i][1]-1] == '.':
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)


print(whitecount - len(bf_search(0,6,a)))

Submission status: Runtime Error

Solution code:

h,w = (int(i) for i in input().split())
M = [input() for i in range(h)]
N = [[False]*w for i in range(h)]
print(M)
cnt = 0
for i in range(h):
    for j in range(w):
        if M[i][j] == "#":
            cnt += 1
print(cnt)
ans = 0
def dfs(x,y):
    global ans
    if M[x][y] == "#":
        return
    elif N[x][y]:
        return
    elif x == w-1 and y == h-1:
        print(h*w-(ans+1+cnt))
        exit()
    else:
        N[x][y] = True
        ans += 1
        A = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
        for a in A:
            if 0<=a[0]<=w-1 and 0<=a[1]<=h-1:
                dfs(a[0],a[1])

dfs(0,0)
print(-1)

Submission status: Runtime Error

Solution code:
from queue import Queue

H, W = [int(x) for x in input().split()]
realH = H + 2
realW = W + 2
s = ["#" + input() + "#" for x in range(H)]
wall = "#" * (realW)
s.insert(0, wall)
s.append(wall)
dxy = [0, 1, 0, -1, 0]
inf = float("inf")

visited = [[False] * realW for x in range(realH)]
depth = [[inf] * realW for x in range(realH)]
depth[1][1] = 1
q = Queue()
q.put((1,1))

while not q.empty():
    place = q.get()
    if place == (H, W):
        break
    for i in range(4):
        nxt = (place[0] + dxy[i], place[1] + dxy[i+1])
        if s[nxt[0]][nxt[1]] == "." and not visited[nxt[0]][nxt[1]]:
            q.put(nxt)
            depth[nxt[0]][nxt[1]] = depth[place[0]][place[1]] + 1
            visited[nxt[0]][nxt[1]] = True

if depth[H][W] == inf:
    print(-1)
elif:
    print(realH * realW - sum(map(lambda x: x.count("#"), s)) - depth[H][W])

Submission status: Runtime Error

Solution code:
import numpy as np 

#入力
H,W=map(int,input().split())
s = np.array([list(input()) for i in range(H)]) 

# [0][0]からの暫定最短距離。H*Wはどんなsでもありえない大きな値である。
d = np.array([[H*W for wi in range(W)] for hi in range(H)])
d[0][0] = 0

# neighbor を格納しているnparray。
nei = [[[] for wi in range(W)] for hi in range(H)]
for hi in range(H):
	for wi in range(W):
		if hi>=1   : nei[hi][wi].append((hi-1,wi  ))
		if hi<=H-2 : nei[hi][wi].append((hi+1,wi  ))
		if wi>=1   : nei[hi][wi].append((hi  ,wi-1))
		if wi<=W-2 : nei[hi][wi].append((hi  ,wi+1))
nei = np.array(nei)	

# qはqueue。list型。qiは一つずつ増えてゆく変数。
q = [[(0,0),0]]

# 訪問済みを表すflag。
f = np.array([[False for wi in range(W)] for hi in range(H)])

while len(q) > 0:
	c = q[0][0]
	if not f[c]:
		f[c] = True
		if   s[c] == '.':
			#通れる地点の場合
			#上下左右のdの値を更新する。
			for ni in nei[c]:
				if d[ni] > d[c]+1:
					d[ni] = d[c]+1
					q.append([ni,d[ni]])
		elif s[c] == '#':
			#通れない地点の場合（特に何もしない）
			pass
		else :
			#呼ばれないはずの領域
			print("Error in reading s.")
			print("qi       =",qi)
			print("q        =",q)
			print("q[qi]    =",q[qi])
			print("s        =\n",s)	
			print("s[q[qi]] =",s[q[qi]])	
	del q[0]
	q.sort(key=lambda x:x[1])

print(sum([list(list(s)[hi]).count('.') for hi in range(H)])-(d[H-1][W-1]+1) if d[H-1][W-1]<H*W else -1)

Submission status: Runtime Error

Solution code:
import collections
h,w = map(int,input().split())
s=[list(input()) for _ in range(h)]
deq = collections.deque([[0,0,0]])

while deq:
    i,j,k = deq.popleft()
    if not((i in range(h)) and (j in range(w))):
        continue
    if s[i][j] != '.':
        continue
    s[i][j]=k
    if i==h-1 and j == w-1:
        break
    deq.append([i + 1, j, k + 1])
    deq.append([i - 1, j, k + 1])
    deq.append([i, j + 1, k + 1])
    deq.append([i, j - 1, k + 1])
if s[i][j] in '.#':
    print(-1)
else:
    black = sum([y.count('#') for y in s])
    print(h*w-black-s[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import collections
h,w = map(int,input().split())
s=[list(input()) for _ in range(h)]
deq = collections.deque([[0,0,0]])

while deq:
    i,j,k = deq.popleft()
    if not((i in range(h)) and (j in range(w))):
        continue
    if s[i][j] != '.':
        continue
    s[i][j]=k
    if i==h-1 and j == w-1:
        break
    deq.append([i + 1, j, k + 1])
    deq.append([i - 1, j, k + 1])
    deq.append([i, j + 1, k + 1])
    deq.append([i, j - 1, k + 1])
if s[i][j] =='.':
    print(-1)
else:
    black = sum([y.count('#') for y in s])
    print(h*w-black-s[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
H, W = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
def f(q, h):
    if len(q) == 0:
        return float('inf')
    i, j, k = q[0]
    if i == H - 1 and j == W - 1:
        return k
    a = [(u, v)
         for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
         if 0 <= u < H and 0 <= v < W and s[u][v] == '.' and (u, v) not in h]
    _q = q[1:] + [(u, v, k + 1) for u, v in a]
    _h = h | set(a)
    return f(_q, _h)
print(max(-1, sum(t.count('.') for t in s) - f([(0, 0, 0)], {(0, 0)}) - 1))

Submission status: Runtime Error

Solution code:
import numpy as np
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
if np.isinf(adj[start][end]):
    print(-1)
else:
    print(n_aisle - adj[start][end] - 1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
if np.isinf(adj[start][end]):
    print(-1)
else:
    print(n_aisle - adj[start][end] - 1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
if np.isinf(adj[start][end]):
    print(-1)
print(n_aisle - adj[start][end] - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
print(n_aisle - adj[start][end] - 1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
print(n_aisle - adj[start][end] - 1)

Submission status: Runtime Error

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

def check(x,y,c):
    if(x > W-1 or y > H-1):
        return
    if(List[y][x] == '#'):
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

flag = -1
while(len(queue) != 0):
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        flag = 1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
if(flag == 1):
    print(H*W - c - shape)
else:
    print(-1)

Submission status: Runtime Error

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

while(len(queue) != 0):
    x,y = queue[0]
    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: Runtime Error

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

while(len(queue) != 0):
    x,y = queue[0]
    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: Runtime Error

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)
while(len(queue) != 0):
    x,y = queue[0]
    queue.pop(0)
    if(x == H-1 and y == W-1):
        flag = 1
        break
    if(x < H-1):
        if(List[x+1][y] == '.'):
            queue.append((x+1,y))
    if(y < W-1):
        if(List[x][y+1] == '.'):
            queue.append((x,y+1))
if(flag == 1):
    print(H*W - (H-1 + W-1 + 1) - shape)
else:
    print(-1)

Submission status: Runtime Error

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(0)
    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))
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(0)
    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: Runtime Error

Solution code:
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    if passed[curr] > 0:
        return 100000 #passed[curr]
    passed[curr] = 1
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
#passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
if count < 50 * 50:
    print(dotsum - count - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

ef iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    if passed[curr] > 0:
        return 100000 #passed[curr]
    passed[curr] = 1
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
#passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
if count < 50 * 50:
    print(dotsum - count - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    if passed[curr] > 0:
        return 100000 #passed[curr]
    passed[curr] = 1
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
#passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
if count < 100000:
    print(dotsum - count - 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    #if passed[curr] < 100000:
    #    print(passed[curr], count)
    if passed[curr] > 0:
        return 100000 #passed[curr]
    passed[curr] = 1
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
#passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
print(dotsum - count - 1)

Submission status: Runtime Error

Solution code:
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    #if passed[curr] < 100000:
    #    print(passed[curr], count)
    if passed[curr] <= count:
        return 100000
    passed[curr] = count
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
print(dotsum - count - 1)

Submission status: Runtime Error

Solution code:
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return passed[curr]
    
    passed[curr] = min(passed[curr], count)
    if passed[curr] < count:
        return 100000
    
    ret = 100000
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)

    return ret


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.int32)
passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
print(dotsum - count - 1)

Submission status: Runtime Error

Solution code:
def clear_grid(sx, sy, gx, gy, grid):
    distance = [[None for i in range(W)] for j in range(H)]
    
    if grid[0][0] == "#":
        return -1
    
    white_num = sum(i.count(".") for i in grid)
    
    queue = []
    visited = []
    queue.insert(0,(sx,sy))
    visited.insert(0,(sx,sy))
    distance[sx][sy] = 0
    while len(queue)>0:
        x,y = queue.pop()
            
        if x == gx and y == gy:
            return white_num - distance[gx][gy] - 1
        
        for i in range(0,4):
            nx, ny = x + [1,0,-1,0][i], y+[0,1,0,-1][i]
            if(0<=nx and nx<=W-1 and 0<=ny and ny<=H-1 and\
               grid[nx][ny]!="#" and (nx,ny) not in visited):
                queue.insert(0,(nx,ny))
                visited.insert(0,(nx,ny))
                distance[nx][ny] = distance[x][y] + 1
        if len(queue)==0:
            return -1

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

print(clear_grid(0,0,H-1,W-1,given_grid))

Submission status: Runtime Error

Solution code:
def white_count(grid):
    count = 0
    for i in grid:
        for j in i:
            if j == ".":
                count += 1
    return count
        
def clear_grid(sx, sy, gx, gy, grid):
    distance = [[None for i in range(W)] for j in range(H)]
    
    if grid[0][0] == "#":
        return -1
    
    queue = []
    visited = []
    queue.insert(0,(sx,sy))
    visited.insert(0,(sx,sy))
    distance[sx][sy] = 0
    while len(queue)>0:
        x,y = queue.pop()
            
        if x == gx and y == gy:
            return white_count(grid) - distance[gx][gy] - 1
        
        for i in range(0,4):
            nx, ny = x + [1,0,-1,0][i], y+[0,1,0,-1][i]
            if(0<=nx and nx<=W-1 and 0<=ny and ny<=H-1 and\
               grid[nx][ny]!="#" and (nx,ny) not in visited):
                queue.insert(0,(nx,ny))
                visited.insert(0,(nx,ny))
                distance[nx][ny] = distance[x][y] + 1
        if len(queue)==0:
            return -1

H, W = map(lambda x:int(x), input().split())
given_grid = []
for i in range(H):
    given_grid.append(list(input()))

print(clear_grid(0,0,H-1,W-1,given_grid))

Submission status: Runtime Error

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)
    sys.exit()
minDis = M[-1][-1] + 1
numWhite = 0
for line in S:
    numWhite += line.count('.')
print(numWhite-minDis)

Submission status: Runtime Error

Solution code:
#すでに調べているか確認
def check(i, j, check, s):
    if s[i][j] == "#":
        return 0
    else:
        for a in range(len(check)):
            if check[a][0] == i and check[a][1] == j:
                return 0
        return 1

H, W = map(int, input().split())
s = [0] * W
t = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    s[i] = list(input())

#各マス目の大きさが入っている
t[0][0] = 1
#キュー
queue = [[0,0]]
#調べたマスのリスト
checklist = []

z = 1
while(1):
    if not queue:
        z = 0
        break
    #キューから取り出す
    i = queue[0][0]
    j = queue[0][1]
    del queue[0]
    #ゴールか判断する
    if i == H-1 and j == W-1:
        break
    #print('aaaaaaaaa')
    if check(i, j, checklist, s) == 1:
        checklist.append([i, j])
        #print('[{},{}]'.format(i,j))
        if i > 0:
            if check(i-1, j, checklist, s) == 1:
                queue.append([i-1, j])
                t[i-1][j] = t[i][j] + 1
        if j > 0:
            if check(i, j-1, checklist, s) == 1:
                queue.append([i, j-1])
                t[i][j-1] = t[i][j] + 1
        if i < H - 1:
            if check(i+1, j, checklist, s) == 1:
                queue.append([i+1, j])
                t[i+1][j] = t[i][j] + 1
        if j < W - 1:
            if check(i, j+1, checklist, s) == 1:
                queue.append([i, j+1])
                t[i][j+1] = t[i][j] + 1

point = 0

if z == 1:
    for i in range(H):
        for j in range(W):
            if s[i][j] == ".":
                point = point + 1

    print(point - t[H-1][W-1])
else:
    print(-1)