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 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(W):
        for j in range(H):
            if s[i][j] == ".":
                point = point + 1

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

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
            else:
                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

    checklist.append([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(W):
        for j in range(H):
            if s[i][j] == '.':
                point = point + 1

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

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
            else:
                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

    checklist.append([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(W):
        for j in range(H):
            if s[i][j] == '.':
                point = point + 1

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

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
            else:
                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 = []

while(1):
    if not queue:
        print('------------')
        break
    #キューから取り出す
    i = queue[0][0]
    j = queue[0][1]
    del queue[0]
    #ゴールか判断する
    if i == H-1 and j == W-1:
        break

    checklist.append([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
for i in range(W):
    for j in range(H):
        if s[i][j] == '.':
            point = point + 1

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

Submission status: Runtime Error

Solution code:
H, W = tuple(map(int, input().split(' ')))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

def get_arounds(x, y, max_x, max_y):
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y, arounds))

def find_path(point, path, ignore, H, W):
    x = point[0]
    y = point[1]
    arounds = get_arounds(x, y, H, W)
    targets = list(filter(lambda x: not x in ignore, arounds))

    if len(targets) == 0:
        return [(False, path, ignore)]
    else:
        return [(True, path + [target], ignore + arounds)
                for target in targets]


ignore = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            ignore.append((i, j))

paths = [(True, [(0, 0)], ignore)]
s_path = []
while any([p[0] for p in paths]):
    print('.', endl='')
    next_paths = []
    for p in filter(lambda p: p[0], paths):
        if p[1][-1] == (H - 1, W - 1):
            s_path = p[1]
            break

        next_paths.extend(find_path(p[1][-1], p[1], p[2], H, W))
    paths = next_paths

if len(s_path) == 0:
    print(-1)
else:
    print(H * W - len(s_path) - len(ignore))

Submission status: Runtime Error

Solution code:
def main():
    H, W = [int(x) for x in input().strip().split()]
    tables = []
    white_count = 0
    for i in range(H):
        rows = [str(x) for x in list(input().strip())]
        white_count += rows.count(".")
        tables.append(rows)

    next_cells = [(0, 0, 1)]
    while(next_cells):
        _next_cells = []
        for next_cell in next_cells:
            y, x, step = next_cell
            if y == H-1 and x == W-1: #Goal
                tables[y][x] = str(min(step+1, int(tables[y][x])))
                continue

            for cond, ys, xs in [(y != 0,y-1,x),(y != H-1,y+1,x),(x != 0,y,x-1),(x != W-1,y,x+1)]
                if cond: # up OK
                    if tables[ys][xs] != "#": # move OK
                        if tables[ys][xs] != ".": # 既に通った
                            if step+1 < int(tables[ys][xs]):
                                tables[ys][xs] = str(step+1)
                                _next_cells.append((ys, xs, step+1))
                        else: # 初めて通る
                            tables[ys][xs] = str(step+1)
                            _next_cells.append((ys, xs, step+1))
            # end for
        # end for
        next_cells = list(set(_next_cells)) # 重複カット
    # end while
    if tables[H-1][W-1] == ".":
        return -1
    return white_count - int(tables[H-1][W-1])
    
if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
d = [0, 1, 0, -1]
def f(x, y, n, m):
    if m[x][y] == "#":
        return
    if type(m[x][y]) == type(int()) and m[x][y] <= n:
        return
    if m[x][y] == ".":
        m[x][y] = n
        for i in xrange(4):
            f(x+d[i], y+d[i+1&3], n+1, m)

h, w = map(int, raw_input().split())
m = list()
m.append(["#" for _ in xrange(w+2)])
for _ in xrange(h):
    m.append(["#"]+list(raw_input())+["#"])
m.append(["#" for _ in xrange(w+2)])
dat = len(filter(lambda x:x==".", [i for j in m for i in j]))
f(1, 1, 1, m)
try:
    print dat-m[h][w]
except:
    print -1
for i in m:
    for j in i:
        try:
            print "%2d" % j,
        except:
            print " %s" % j,
    print

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split(' '))
matrix = [input() for _ in range(h)]

graph = {}
cnt = -1
for i in range(h):
    for j in range(w):
        cnt += 1
        temp = []
        if matrix[i][j] == '.':
            if i != 0:
                if matrix[i - 1][j] == '.':
                    temp.append(cnt - w)
            if j != 0:
                if matrix[i][j - 1] == '.':
                    temp.append(cnt - 1)
            if i != h - 1:
                if matrix[i + 1][j] == '.':
                    temp.append(cnt + w)            
            if j != w - 1:
                if matrix[i][j + 1] == '.':
                    temp.append(cnt + 1)
        
            if len(temp) > 0:
                graph[cnt] = sorted(temp, reverse=True)

                
def dfs(graph, start, goal):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label == goal:
            visited.append(label)
            return visited
        
        if label not in visited:
            visited.append(label)
            stack = graph[label] + stack
            
    return visited


if (h*w-1) in dfs(graph, 0, h*w-1):
    print(len(graph.keys()) - len(dfs(graph, 0, h*w-1)))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
d = [0, 1, 0, -1]
def f(x, y, n, m):
    if m[x][y] == "#" or m[x][y] == " ":
        return
    if m[x][y] == "." or m[x][y] > n:
        m[x][y] = n
        for i in xrange(4):
            f(x+d[i], y+d[i+1&3], n+1, m)

h, w = map(int, raw_input().split())
m = list()
m.append([" " for _ in xrange(w+2)])
for _ in xrange(h):
    m.append([" "]+list(raw_input())+[" "])
m.append([" " for _ in xrange(w+2)])
dat = len(filter(lambda x:x==".", [i for j in m for i in j]))
f(1, 1, 1, m)
try:
    print dat-m[h][w]
except:
    print -1

Submission status: Runtime Error

Solution code:
d = [0, 1, 0, -1]
def f(x, y, n, m):
    if m[x][y] == "#" or m[x][y] == " ":
        return
    if m[x][y] == "." or m[x][y] > n:
        m[x][y] = n
        for i in xrange(4):
            f(x+d[i], y+d[i+1&3], n+1, m)

h, w = map(int, raw_input().split())
m = list()
m.append([" " for _ in xrange(w+2)])
for _ in xrange(h):
    m.append([" "]+list(raw_input())+[" "])
m.append([" " for _ in xrange(w+2)])
dat = len(filter(lambda x:x==".", [i for j in m for i in j]))
f(1, 1, 1, m)
print dat-m[h][w]

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import queue
H, W = list(map(int, input().split()))
S = list()
S.append(input() for i in range(H))
dist = [[3000 for j in range(W)] for i in range(H)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = queue.Queue()
dist[0][0] = 0
q.put([0, 0])
while q.empty() == False:
    x, y = q.get()
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H :
            if S[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1 :
                dist[ny][nx] = dist[y][x] + 1
                q.put([nx, ny])
cnt = 0
for i in range(H) :
    for j in range(W) :
        if S[i][j] == '.' :
            cnt += 1
print(-1 if dist[H-1][W-1] == 3000 else cnt - dist[H-1][W-1] - 1)

Submission status: Runtime Error

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

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

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

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


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

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

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

def bfs(sx, sy, gx, gy, maze):
    # 迷路の大きさ
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    
    queue = []
    # キューにスタート地点を追加
    queue.insert(0, (sx, sy))
    # スタート地点からスタート地点までの距離はゼロ
    distance[sx][sy] = 0
    # キューから要素がなくなる＝探索が終わる
    while len(queue):
        x, y = queue.pop()
        # ゴールに到着で終了
        if x == gx and y == gy:
            break
        for i in range(4):
            # ゴールに到着しなければ1つ移動
            nx, ny = x + dx[i], y + dy[i]
            if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                queue.insert(0, (nx, ny))
                distance[nx][ny] = distance[x][y] + 1
    return distance[gx][gy]

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

# 白マスの数
n_w = 0

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

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

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
m = [map((lambda x: 0 if x == '#' else 1),list(input())) for i in range(h)]
white = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,raw_input().split())
c=[]
for i in range(H):
	s=list(raw_input())
	for j in s:
		if j=="#":
			c.append(1)
		else:
			c.append(0)


nl=[ [] for i in range(H*W)]

p0=[-1,1,3]
p1=[-3,1,3]
p2=[-3,-1,3]
p3=[-3,-1,1]
p4=[-3,-1,1,3]
for i in range(H*W):
	if c[i]==0:
		if i==0:
			if c[i+1]==0:nl[i].append(i+1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W-1:
			if c[i-1]==0:nl[i].append(i-1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W*(H-1):
			if c[i-W]==0:nl[i].append(i-W)
			if c[i+1]==0:nl[i].append(i+1)		
		elif i==W*H-1:
			if c[i-W]==0:nl[i].append(i-W)
			if c[i-1]==0:nl[i].append(i-1)
		elif i<W-1:
			for j in p0:
				if c[i+j]==0:nl[i].append(i+j)			
		elif i%W==0:
			for j in p1:
				if c[i+j]==0:nl[i].append(i+j)	
		elif i%W==W-1:
			for j in p2:
				if c[i+j]==0:nl[i].append(i+j)
		elif i>W*(H-1):
			for j in p3:
				if c[i+j]==0:nl[i].append(i+j)
		else:
			for j in p4:
				if c[i+j]==0:nl[i].append(i+j)
				

V=[ None for i in range(H*W)]

def dfs(start):
	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		V[v]=1
		if H*W-1 in nl[v]:
			V[H*W-1]=1
			return

		for i in nl[v]:
			if V[i] is None:
				q.append(i)

dfs(0)
print len( filter(lambda x:x is None, V) ) - sum(c)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
checked = [[h * w + 1 for _ in range(w)] for _ in range(h)]
num_sharp = 0
for r in maze:
    num_sharp += r.count("#")


def search(x, y, count):
    if not (0 <= x < h) or not (0 <= y < w) or maze[x][y] == "#" or checked[x][y] <= count:
        return False
    else:
        checked[x][y] = count
        return search(x + 1, y, count + 1) or search(x, y + 1, count + 1) or search(
            x - 1, y, count + 1) or search(x, y - 1, count + 1)


search(0, 0, 1)
if checked[h-1][w-1] <= h * w:
    print(h * w - checked[h-1][w-1] - num_sharp)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
checked = [[h * w + 1 for _ in range(w)] for _ in range(h)]
num_sharp = 0
for r in maze:
    num_sharp += r.count("#")


def search(x, y, count):
    if not (0 <= x < h) or not (0 <= y < w) or maze[x][y] == "#" or checked[x][y] <= count:
        return False
    else:
        checked[x][y] = count
        return search(x + 1, y, count + 1) or search(x, y + 1, count + 1) or search(
            x - 1, y, count + 1) or search(x, y - 1, count + 1)


search(0, 0, 1)
if checked[-1][-1] <= h * w:
    print(h * w - checked[-1][-1] - num_sharp)
else:
    print(-1)

Submission status: Runtime Error

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

h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
checked = [[h * w + 1 for _ in range(w)] for _ in range(h)]
num_sharp = 0
for r in maze:
    num_sharp += r.count("#")


def search(x, y, count):
    if x < 0 or h <= x or y < 0 or w <= y or maze[x][y] == "#" or checked[x][y] < count:
        return False
    else:
        checked[x][y] = count
        return search(x + 1, y, count + 1) or search(x, y + 1, count + 1) or search(
            x - 1, y, count + 1) or search(x, y - 1, count + 1)


search(0, 0, 1)
if checked[-1][-1] <= h * w:
    print(h * w - checked[-1][-1] - num_sharp)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split(" "))
s = [list(input()) for _ in range(0, H)]

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
if (H-1, W-1) in d:
	print("".join(map(lambda x: "".join(x), s)).count(".") - d[(H-1, W-1)])
else:
	print(-1)

Submission status: Runtime Error

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

s = [list(input()) for _ in range(0, H)]

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d and c >= d[(i, j)]:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
print(-1)

Submission status: Runtime Error

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

cnt = 0
G = {}
for i in range(H):
    for j in range(W):
        temp = []
        if matrix[i][j] == '.':
            if i != 0:
                if matrix[i - 1][j] == '.':
                    temp.append(cnt - W)
            if j != 0:
                if matrix[i][j - 1] == '.':
                    temp.append(cnt - 1)
            if i != H - 1:
                if matrix[i + 1][j] == '.':
                    temp.append(cnt + W)            
            if j != W - 1:
                if matrix[i][j + 1] == '.':
                    temp.append(cnt + 1)
                    
        G[cnt] = temp
        cnt += 1

        
def dfs(graph, start, end):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)

            
            return visited
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
            
    if end in visited:
        return True
    else:
        return False

    
if dfs(G, 0, (H * W - 1)):
    cnt = 0
    for i in range(W):
        for j in range(H):
            if matrix[i][j] == '.':
                cnt += 1

    print(cnt - (H + W - 1))
    
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem D

if __name__ == '__main__':
    height, width = map(int, input().split(" "))
    s = [map(str, input().split(",")) for i in range(width)]

    total_count = height * width
    white_count_min = (height - 1) + width
    current_black_count = s.count("#")

    result = total_count - current_black_count - white_count_min

    if result > 0:
        print(result)
    else:
        print(-1)

Submission status: Runtime Error

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

h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
checked = [[h * w + 1 for _ in range(w)] for _ in range(h)]
num_sharp = 0
for r in maze:
    for c in r:
        if c == "#":
            num_sharp += 1


def search(x, y, count):
    # if x == h - 1 and y == w - 1:
    # checked[x][y] = count - 1
    # return True
    # elif x < 0 or h <= x or y < 0 or w <= y or maze[x][y] == "#" or checked[x][y] < count:
    if x < 0 or h <= x or y < 0 or w <= y or maze[x][y] == "#" or checked[x][y] < count:
        return False
    else:
        checked[x][y] = count
        return search(x + 1, y, count + 1) or search(x, y + 1, count + 1) or search(
            x - 1, y, count + 1) or search(x, y - 1, count + 1)


search(0, 0, 1)
if checked[-1][-1] <= h * w:
    print(h * w - checked[-1][-1] - num_sharp)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
# import time


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

d = np.ones((H * W, H * W), dtype=int) * H * W
for i in range(H * W):
    d[i][i] = 0
# start = time.time()
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            for idx, jdx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                if 0 <= i + idx < H and 0 <= j + jdx < W and s[i + idx][j + jdx] == ".":
                    d[i * H + j][(i + idx) * H + j + jdx] = d[(i + idx) * H + j + jdx][i * H + j] = 1
# print(time.time() - start)

for k in range(H * W):
    # d = np.array([[d[i][j] if d[i][j] <= d[i][k] + d[k][j] else d[i][k] + d[k][j] for j in range(H * W)] for i in range(H * W)], dtype=int)
    d = [[d[i][j] if d[i][j] <= d[i][k] + d[k][j] else d[i][k] + d[k][j] for j in range(H * W)] for i in range(H * W)]
    # d = [[min(d[i][j], d[i][k] + d[k][j]) for j in range(H * W)] for i in range(H * W)]
    # for i in range(H * W):
    #     d[i] = [min(d[i][j], d[i][k] + d[k][j]) for j in range(H * W)]
    #     # for j in range(H * W):
    #     #     d[i][j] = min(d[i][j], d[i][k] + d[k][j])
# print(d)
# print(time.time() - start)
result = d[0][H * W - 1]
if result == H * W:
    print(-1)
else:
    count = 0
    for h in range(H):
        count += s[h].count("#")
    print(int(result - count))

Submission status: Runtime Error

Solution code:
H, W = (int(_) for _ in input().split())
s = [list(input()) for h in range(H)]

def Haba(q, x, y, move):
        s[x][y]= "#"
        if x == H - 1 and y == W - 1:
            return True
        for i in range(4):
            if 0 <= x + dx[i] and x + dx[i] < H and 0 <= y + dy[i] and y + dy[i] < W and s[x+dx[i]][y+dy[i]] == '.':
                move += 1
                q.append([x + dx[i], y + dy[i], move])
        return False

count = 0
for x in range(H):
    for y in range(W):
        if s[x][y] == '.':
            count += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q = []
q.append([0, 0, 0])
x = 0
y = 0
move = 0
ans = True
while(True):
    if len(q) == 0:
        ans = False
        break
    x, y, move = q.pop(0)
    if(Haba(q, x, y, move)) :
        break
if ans:
    print(count -move - 1)
else
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse.csgraph as sg

H, W = [int(a) for a in input().split()]
ss = []
for _ in range(H):
    ss.append(input())

g = np.zeros((H*W,H*W))

v_edges = [((i,j), (i,j+1)) for i in range(H) for j in range(W-1) if ss[i][j] == "." and ss[i][j+1] == "."]
h_edges = [((i,j), (i+1,j)) for i in range(H-1) for j in range(W) if ss[i][j] == "." and ss[i+1][j] == "."]

for (si,sj), (di,dj) in v_edges + h_edges:
    g[si*W+sj][di*W+dj] = 1
    g[di*W+dj][si*W+sj] = 1

r = sg.dijkstra(g)
score = r[0,H*W-1]

if np.isinf(score):
    print(-1)
    exit(1)

#print(r)
#print(ss) 

ss_ = "".join(ss)
num = len([0 for c in ss_ if c == '.'])
#print(num)
#print(score)
print("%d" % (num - (score+1)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from IPython import embed
H, W = [int(s) for s in input().split(" ")]

maze = [list(input()) for _ in range(H)]

distance = [[float("inf") for i in range(W)] for j in range(H)]

def bfs():
    queue = []
    sx = 0
    sy = 0
    gx = H-1
    gy = W-1

    queue.insert(0, (sx, sy))

    distance[sx][sy] = 0

    while len(queue):
        x, y = queue.pop()

        if x == gx and y == gy:
            break

        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            
            if (0 <= nx < H and 0 <= ny < W):
                if maze[nx][ny] != '#' and distance[nx][ny] == float("inf"):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

    return distance[gx][gy]

d = bfs()
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            cnt += 1
if  d == float("inf"):
    print(-1)
else:
    print(cnt - d - 1)

Submission status: Runtime Error

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

s = [list(input()) for _ in range(0, H)]

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d and c >= d[(i, j)]:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
if (H-1, W-1) in d:
	print("".join(map(lambda x: "".join(x), s)).count(".") - d[(H-1, W-1)])
else:
	print(-1)