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

#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:
h, w = map(int, input().split())
arr = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    arr[i] = list(input())

def isWay(x, y):
    if x >= 0 and x < h and y >= 0 and y < w and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(h):
    for j in range(w):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
print(numWay - arr[h-1][w-1])

Submission status: Runtime Error

Solution code:
#
H, W = list(map(int, input().split()))
M = []
for i in range(H):
    M.append(list(input().rstrip()))

#
def walk(pos, steps=0):
    x, y = pos
    #print(pos, M)

    #
    if M[y][x]=='.' or steps<M[y][x]:
        M[y][x] = steps
    else:
        #print('A')
        return

    # up
    if y>0 and M[y-1][x]!='#':
        walk((x, y-1), steps+1)
    # down
    if y<H-1 and M[y+1][x]!='#':
        walk((x, y+1), steps+1)
    # left
    if x>0 and M[y][x-1]!='#':
        walk((x-1, y), steps+1)
    # right
    if x<W-1 and M[y][x+1]!='#':
        walk((x+1, y), steps+1)
    #print('B')

#
walk((W-1, H-1))
#print(M)
#exit()

#
if M[0][0]=='.':
    print(-1)
else:
    blocks = sum([m.count('#') for m in M])
    print(H*W - blocks - M[0][0] - 1)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import numpy as np

white = "."
black = "#"
w, h = list(map(int, input().split()))
map = np.zeros([w, h])
s = []
for i in range(h):
    try:
        while True:
            s.append(input())
    except EOFError:
        pass
for i in range(h):
    for j in range(w):
        if s[j] == white:
            map[j, i] += 1
can = False
for i in range(w):
    sm1 = np.sum(map[0:i+1, 0])
    for j in range(w-i):
        sm2 = 0
        if(j > 0):
            sm2 += np.sum(map[i+1:i+1+j, 1])-1
        if(i+j+1 < w-1):
            sm2 += np.sum(map[i+1+j:w, 2])-1
        if sm1+sm2 == w+h-1:
            can = True
if can == True:
    mx = int(np.sum(map)-(w+h-1))
    print(mx)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
import copy
res=[114514]
def search(x,y,count,map,rireki):
  if x==h-1 and y==w-1:
    if count<res[0]:
      res[0]=count+1
      return
  rireki.append([x,y])
  if x-1>=0:
    if [x-1,y] not in rireki and map[x-1][y]==0:
      search(x-1,y,count+1,map,rireki)
  if y-1>=0:
    if [x,y-1] not in rireki and map[x][y-1]==0:
      search(x,y-1,count+1,map,rireki)
  if x+1<=len(map)-1:
    if [x+1,y] not in rireki and map[x+1][y]==0:
      search(x+1,y,count+1,map,rireki)
  if y+1<=len(map[0])-1:
    if [x,y+1] not in rireki and map[x][y+1]==0:
      search(x,y+1,count+1,map,rireki)
  return

h,w=map(int,input().split())
map=[]
white=0
for i in range(h):
  map.append([])
  for j in input():
    if j=='.':
      map[i].append(0)
      white+=1
    elif j=='#':
      map[i].append(1)
rireki=[]
search(0,0,0,map,rireki)
print(white-res[0])

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, x):
	x += 1
	if (i, j) not in d or x < d[(i, j)]:
		d[(i, j)] = x
		if i-1 >= 0 and s[i-1][j] == '.':
			walk(i-1, j, x)
		if j-1 >= 0 and s[i][j-1] == '.':
			walk(i, j-1, x)
		if i+1 < H and s[i+1][j] == '.':
			walk(i+1, j, x)
		if j+1 < W and s[i][j+1] == '.':
			walk(i, j+1, x)

walk(0, 0, 0)
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())
arr = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    arr[i] = list(input())

def isWay(x, y):
    if x >= 0 and x < w and y >= 0 and y < h and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(w):
    for j in range(h):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
print(numWay - arr[w-1][h-1])

Submission status: Runtime Error

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

def isWay(x, y):
    if x >= 0 and x < w and y >= 0 and y < h and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(h):
    for j in range(w):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
print(numWay - arr[w-1][h-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, x):
	x += 1
	if (i, j) not in d or x < d[(i, j)]:
		d[(i, j)] = x
		if i-1 > 0 and s[i-1][j] == '.':
			walk(i-1, j, x)
		if j-1 > W and s[i][j-1] == '.':
			walk(i, j-1, x)
		if i+1 < H and s[i+1][j] == '.':
			walk(i+1, j, x)
		if j+1 < W and s[i][j+1] == '.':
			walk(i, j+1, x)

walk(0, 0, 0)
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:
def solve():
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(map(int, input().split())))

    nwall = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                nwall += 1

    q = []
    q.insert(0, (0,0))
    hist = [[0 for i in range(w)] for j in range(h)]


    while(len(q) > 0):
        x, y = q.pop()

        if x == w-1 and y == h-1:
            break

        for i in range(0, 4):
            nx, ny = x+[1,0,-1,0][i], y+[1,0,-1,0][i]

            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if maze[ny][nx] == '#':
                continue
            if hist[ny][nx] == 1:
                continue

            q.insert(0, (nx,ny))
            hist[nx][ny] = hist[x][y] + 1

    print(h*w - nwall - hist[h-1][w-1])

solve()

Submission status: Runtime Error

Solution code:
def dfs(s, h, w, i, j, root, ans):
    if i == h - 1 and j == w - 1:
        ans.append(root)
    if i - 1 >= 0 and s[i - 1][j] != '#':
        tmp = []
        tmp += s
        tmp[i - 1][j] = '#'
        dfs(tmp, h, w, i - 1, j, root + 1, ans)

    if i + 1 <= h - 1 and s[i + 1][j] != '#':
        tmp = []
        tmp += s
        tmp[i + 1][j] = '#'
        dfs(tmp, h, w, i + 1, j, root + 1, ans)
    if j - 1 >= 0 and s[i][j - 1] != '#':
        tmp = []
        tmp += s
        tmp[i][j - 1] = '#'
        dfs(tmp, h, w, i, j - 1, root + 1, ans)
    if j + 1 <= w - 1 and s[i][j + 1] != '#':
        tmp = []
        tmp += s
        tmp[i][j + 1] = '#'
        dfs(tmp, h, w, i, j + 1, root + 1, ans)

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

s = []
for i in range(h):
    s.append(list(raw_input()))

ct = 0

for i in range(h):
    for ss in s[i]:
        if ss == '.':
            ct += 1

ans = []

dfs(s, h, w, 0, 0, 1, ans)

print ct - max(ans)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import numpy as np

white = "."
black = "#"
w, h = list(map(int, input().split()))
map = np.zeros([w, h])
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == white:
            map[j, i] += 1
sm = 0
can = False
for i in range(w):
    sm += np.sum(map[0:i+1, 0])
    for j in range(w-i):
        if(j > 0):
            sm += np.sum(map[i+1:i+1+j, 1])-1
        if(i+j+1 < w-1):
            sm += np.sum(map[i+j+1:w, 2])-1
        if sm == w+h-1:
            can = True
if can == True:
    mx = int(np.sum(map)-(w+h-1))
    print(mx)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
R,C=map(int,input().split())
sx,sy=1,1
gx,gy=R,C
count=0
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
for i in range(R):
	for j in range(C):
		if(mp[i][j]=='#'):
			count+=1
ans=[[3000 for i in range(C)] for j in range(R)]
ans[sx-1][sy-1]=0
start=[sx-1,sy-1]
goal=[gx-1,gy-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]==".":
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return

print(R*C-bfs(mp,start,goal)-1-count)

Submission status: Runtime Error

Solution code:
from copy import deepcopy


def search_goal(i, j, list_s, H, W):
    if i == W - 1 and j == H - 1:
        return 1

    result = []
    list_s[j][i] = False

    if i > 0 and list_s[j][i - 1]:
        result += [search_goal(i - 1, j, list_s, H, W) + 1]
    if j > 0 and list_s[j - 1][i]:
        result += [search_goal(i, j - 1, list_s, H, W) + 1]
    if i < W - 1 and list_s[j][i + 1]:
        result += [search_goal(i + 1, j, list_s, H, W) + 1]
    if j < H - 1 and list_s[j + 1][i]:
        result += [search_goal(i, j + 1, list_s, H, W) + 1]

    return min(result) if result != [] else 2501


H, W = list(map(int, input().split()))

list_s = []
f = lambda s: s == '.'

for i in range(H):
    list_s += [list(map(f, input()))]

origin_list_s = deepcopy(list_s)
answer = search_goal(0, 0, list_s, H, W)
if answer > 2500:
    print(-1)
else:
    count_white = 0
    for i in range(H):
        count_white += sum(1 for b in origin_list_s[i] if b)
    print(count_white - answer)

Submission status: Runtime Error

Solution code:
import math

H, W = map(int, input().split())

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

num_of_white = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            s[i][j] = 0     # 白なら 0
            num_of_white += 1
        else:
            s[i][j] = 1     # 黒なら 1

route_list = [[0 for i in range(H*W)] for j in range(H*W)]


def numel(a):
    return W * a[0] + a[1]


def route_add(i1, j1, i2, j2):
    route_list[numel([i1, j1])][numel([i2, j2])] = 1


for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j - 1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j + 1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
        elif i == H-1:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
        else:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)
            else:
                if s[i][j] == s[i][j-1] == 0:
                    route_add(i, j, i, j-1)
                if s[i][j] == s[i-1][j] == 0:
                    route_add(i, j, i-1, j)
                if s[i][j] == s[i][j+1] == 0:
                    route_add(i, j, i, j+1)
                if s[i][j] == s[i+1][j] == 0:
                    route_add(i, j, i+1, j)

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = math.inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]:
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示

# print("-----経路-----")
# previous_node = node_num - 1
# while previous_node != -1:
#     if previous_node !=0:
#         print(str(previous_node + 1) + " <- ", end='')
#     else:
#         print(str(previous_node + 1))
#     previous_node = previous_nodes[previous_node]
#
# print("-----距離-----")
# print(distance[node_num - 1])

print(num_of_white - distance[node_num - 1] - 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
R,C=map(int,input().split())
sx,sy=1,1
gx,gy=R,C
count=0
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
for i in range(R):
	for j in range(C):
		if(mp[i][j]=='#'):
			count+=1
ans=[[3000 for i in range(C)] for j in range(R)]
ans[sx-1][sy-1]=0
start=[sx-1,sy-1]
goal=[gx-1,gy-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]==".":
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return

print(R*C-bfs(mp,start,goal)-1-count)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import numpy as np

white = "."
black = "#"
w, h = list(map(int, input().split()))
map = np.zeros([w, h])
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == white:
            map[j][i] += 1
sm = 0
can = False
for i in range(w):
    sm += np.sum(map[0:i+1][0])
    for j in range(w-i):
        sm += np.sum(map[i+1:i+1+j][1])-1
        sm += np.sum(map[i+1+j:w-1][2])-1
        if sm == w+h-1:
            can = True
if can == True:
    mx = np.sum(map)-(w+h-1)
    print(mx)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
Field = [list(input()) for i in range(H)]

que = deque()
que.append([0, 0])
Field[0][0] = 0

while que:
    now = que.popleft()
    if now == [H-1, W-1]:
        break

    if now[0]+1 <= H -1:
        if Field[now[0]+1][now[1]] == ".":
            Field[now[0]+1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]+1, now[1]])

    if now[0]-1 >= 0:
        if Field[now[0]-1][now[1]] == ".":
            Field[now[0]-1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]-1, now[1]])

    if now[1] + 1 <= W -1:
        if Field[now[0]][now[1]+1] == ".":
            Field[now[0]][now[1]+1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]+1])

    if now[1] -1 >= 0:
        if Field[now[0]][now[1]-1] == ".":
            Field[now[0]][now[1]-1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]-1])

Z = int(Field[H-1][W-1])

sharp_cnt = 0
for f in Field:
    sharp_cnt += f.count("#")

print(H*W - sharp_cnt - Z - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
import networkx as nx

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

ss = np.array(ss)

g = nx.Graph()
g.add_nodes_from([("%d_%d" % (i,j), {'color':ss[i][j]}) for i in range(H) for j in range(W)])
g.add_edges_from([("%d_%d" % (i,j), "%d_%d" % (i,j+1), {'weight':1}) for i in range(H) for j in range(W-1)])
g.add_edges_from([("%d_%d" % (i,j), "%d_%d" % (i+1,j), {'weight':1}) for i in range(H-1) for j in range(W)])

#print(g.nodes(data=True))
#print(g.edges(data=True))


if nx.algorithms.shortest_paths.generic.has_path(g, source="0_0", target="%d_%d" % (H-1,W-1)) == False:
    print(-1)
else:
    path = nx.algorithms.shortest_paths.generic.shortest_path(g, source="0_0", target="%d_%d" % (H-1,W-1), weight='weight')
    ss_ = "".join(ss)
    num = len([0 for c in ss_ if c == '.'])
    #print(num)
    #print(path)
    print(num - len(path))

Submission status: Runtime Error

Solution code:
#coding:utf-8
import numpy as np

white = "."
black = "#"
w, h = list(map(int, input().split()))
map = np.zeros([w, h])
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == white:
            map[j][i]++
sm = 0
can = False
for i in range(w):
    sm += np.sum(map[0:i+1][0])
    for j in range(w-i):
        sm += np.sum(map[i+1:i+1+j][1])-1
        sm += np.sum(map[i+1+j:w-1][2])-1
        if sm == w+h-1:
            can = True
if can == True:
    mx = np.sum(map)-(w+h-1)
    print(mx)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import pprint

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(list(map(int, input())))
    return li

""" input template
S = input()
N = int(input())
L = list(map(int, input().split()))
a, b = list(map(int, input().split()))
SL = list(input())
"""

# --------------------------------------------

def main():
    delta_x = [-1, 0, 0, 1]
    delta_y = [0, -1, 1, 0]

    H, W = list(map(int, input().split()))

    S = []
    for _ in range(H):
        S.append(list(input()))

    S[0][0] = 0

    reached = [[0, 0]]
    move = 1

    while len(reached) != 0:
        new_reached = []

        for r in reached:
            for dx, dy in zip(delta_x, delta_y):
                new_y = r[0] + dy
                new_x = r[1] + dx

                if not (0 <= new_y < H):
                    continue

                if not(0 <= new_x < W):
                    continue

                if S[new_y][new_x] == ".":
                    S[new_y][new_x] = move
                    new_reached.append([new_y, new_x])

        move += 1
        reached = new_reached

    if S[-1][-1] == "." or S[-1][-1] == "#":
        print(-1)


    i = H-1
    j = W-1
    while True:
        current = S[i][j]

        if current == 0:
            break
        S[i][j] = "#"


        for dx, dy in zip(delta_x, delta_y):
            new_y = i + dy
            new_x = j + dx

            if not (0 <= new_y < H):
                continue

            if not(0 <= new_x < W):
                continue

            if S[new_y][new_x] == current - 1:
                i = new_y
                j = new_x
                break

    S[0][0] = "#"

    point = 0
    for row in S:
        for cell in row:
            if isinstance(cell, int) or cell == ".":
                point += 1

    print(point)





main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import pprint

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(list(map(int, input())))
    return li

""" input template
S = input()
N = int(input())
L = list(map(int, input().split()))
a, b = list(map(int, input().split()))
SL = list(input())
"""

# --------------------------------------------

def main():
    delta_x = [-1, 0, 0, 1]
    delta_y = [0, -1, 1, 0]

    H, W = list(map(int, input().split()))

    S = []
    for _ in range(H):
        S.append(list(input()))

    S[0][0] = 0

    reached = [[0, 0]]
    move = 1

    while len(reached) != 0:
        new_reached = []

        for r in reached:
            for dx, dy in zip(delta_x, delta_y):
                new_y = r[0] + dy
                new_x = r[1] + dx

                if not (0 <= new_y < H):
                    continue

                if not(0 <= new_x < W):
                    continue

                if S[new_y][new_x] == ".":
                    S[new_y][new_x] = move
                    new_reached.append([new_y, new_x])

        move += 1
        reached = new_reached


    i = H-1
    j = W-1
    while True:
        current = S[i][j]

        if current == 0:
            break
        S[i][j] = "#"


        for dx, dy in zip(delta_x, delta_y):
            new_y = i + dy
            new_x = j + dx

            if not (0 <= new_y < H):
                continue

            if not(0 <= new_x < W):
                continue

            if S[new_y][new_x] == current - 1:
                i = new_y
                j = new_x
                break

    S[0][0] = "#"

    point = 0
    for row in S:
        for cell in row:
            if isinstance(cell, int) or cell == ".":
                point += 1

    print(point)





main()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = [list('#' * (w + 2))]
dot = 0
for i in range(h):
    s.append(['#'] + list(input()) + ['#'])
    dot += s[-1].count('.')
s.append(list('#' * (w + 2)))


def walk(y, x, l):
    for i in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        dy = y + i[0]
        dx = x + i[1]
        if s[dy][dx] == '.':
            s[dy][dx] = l + 1
            walk(dy, dx, l + 1)
        elif s[dy][dx] != '#':
            if s[dy][dx] > l+1:
                s[dy][dx] = l + 1
                walk(dy, dx, l + 1)

s[1][1] = 1
walk(1, 1, 1)
if s[h][w] == '.':
    print(-1)
else:
    print(dot - s[h][w])

Submission status: Runtime Error

Solution code:
# D

import networkx as nx

H, W = map(int, input().split())

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

num_of_white = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            s[i][j] = 0     # 白なら 0
            num_of_white += 1
        else:
            s[i][j] = 1     # 黒なら 1


def numel(a):
    return W * a[0] + a[1]


G = nx.Graph()
for i in range(H):
    for j in range(W):
        G.add_node(numel([i, j]))

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))
            else:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
        elif i == H-1:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
            else:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
        else:
            if j == 0:
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))
            elif j == W-1:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))
            else:
                if s[i][j] == s[i][j-1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j-1]))
                if s[i][j] == s[i-1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i-1, j]))
                if s[i][j] == s[i][j+1] == 0:
                    G.add_edge(numel([i, j]), numel([i, j+1]))
                if s[i][j] == s[i+1][j] == 0:
                    G.add_edge(numel([i, j]), numel([i+1, j]))

path_length = len(nx.shortest_path(G, source=numel([0, 0]), target=numel([H-1, W-1])))
print(num_of_white - path_length)