Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Wrong Answer

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

import sys
import numpy as np

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

map2d = np.zeros((h,w))

n = 0
for i in range(0,h):
    a = input()
    m = 0
    for j in a:
        if j == ".":#白いとこ
            map2d[n,m] = 0
            m += 1
        else:
            map2d[n,m] = 1
            m += 1
    n += 1

#たどりつけない
if map2d[0,1] == 1 and map2d[1,0] == 1:
    print("-1")
    sys.exit()
elif map2d[h-2,w-1] == 1 and map2d[h-1,w-2] == 1:
    print("-1")
    sys.exit()

    
def W_locate(h_num,w_now):#何列目？　Wで今どこにいるか
    for i in range(w_now,w):
        if map2d[h_num,i] == 0:
            w_now = i#横の現在地
        else:
            break
    return w_now
    
num = W_locate(0,0)
for i in range(1,h):
    num = W_locate(i,num)


print(np.sum(map2d))

Submission status: Wrong Answer

Solution code:
print("209")

Submission status: Wrong Answer

Solution code:
import copy
hw = list(map(int, input().split()))
s = []
for i in range(hw[0]):
    s.append(list(input()))
distance = copy.deepcopy(s)
for i in range(hw[0]):
    for j in range(hw[1]):
        distance[i][j] = -1
distance[0][0] = 0
for k in range(2500):
    for i in range(hw[0]):
        for j in range(hw[1]):
            try:
                if s[i-1][j] == "." and s[i][j] == "." and distance[i-1][j] == k and distance[i][j] == -1:
                    distance[i][j] = k + 1
            except:
                pass
            try:
                if s[i+1][j] == "." and s[i][j] == "." and distance[i+1][j] == k and distance[i][j] == -1:
                    distance[i][j] = k + 1
            except:
                pass
            try:
                if s[i][j-1] == "." and s[i][j] == "." and distance[i][j-1] == k and distance[i][j] == -1:
                    distance[i][j] = k + 1
            except:
                pass
            try:
                if s[i][j+1] == "." and s[i][j] == "." and distance[i][j+1] == k and distance[i][j] == -1:
                    distance[i][j] = k + 1
            except:
                pass
black = 0
for i in range(hw[0]):
    for j in range(hw[1]):
        if s[i][j] == ".":
            black = black + 1
print(black - distance[hw[0]-1][hw[1]-1] - 1)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
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 = [1300] * 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 = 1300 # 最小の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])

if num_of_white - distance[node_num - 1] - 1 > 0:
    print(num_of_white - distance[node_num - 1] - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
maze=[["" for i in range(W)] for j in range(H)]
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="#"):
            bla+=1
            maze[i][j]="#"
        else:
            whi+=1
            maze[i][j]="."

def clear_maze(sx,sy,gx,gy,maze,W,H):
    INF=100000000
    distance=[[INF for i in range(W)] for j in range(H)]
    
    def bfs():
        testx=[1,0,-1,0]
        testy=[0,1,0,-1]
        queue=[]
        
        queue.insert(0,(sy,sx))
        
        distance[sy][sx]=0
        count=0
        while len(queue):
            if(count>100000000):
                return -1
            count+=1
            x,y=queue.pop()
            
            if(x==gx and y==gy):
                break
            
            for i in range(0,4):
                nx,ny=x+testx[i],y+testy[i]
                
                if(0<=nx and nx<W and 0<=ny and ny<H):
                    if(maze[ny][nx]!="#"):
                        if(distance[ny][nx]==INF):
                            queue.insert(0,(nx,ny))
                            distance[ny][nx]=distance[y][x]+1
        return distance[gy][gx]
        
    return bfs()

area=W*H
step=clear_maze(0,0,W-1,H-1,maze,W,H)
if(step==-1):
    print(-1)
elif(maze[0][0]=="#"):
    print(-1)
elif(maze[H-1][W-1]=="#"):
    print(-1)
else:
    score=area-step-1-bla
    print(score)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter
H, W = map(int, input().split())
s = np.array([[x for x in input()] for h in range(H)])
counter = Counter()
kns = [0,0]
goal = [H-1, W-1]
visited = np.zeros_like(s, dtype=bool)
forward_count = 0
back_count = 0
can_goal = True

while kns != goal:
    visited[kns[0], kns[1]] = True
    if kns[0] < H-1 and s[kns[0] + 1, kns[1]] == '.' and visited[kns[0] + 1, kns[1]] == False:
        kns[0] += 1
        forward_count += 1
    elif kns[1] < W-1 and s[kns[0], kns[1] + 1] == '.' and visited[kns[0], kns[1] + 1] == False:
        kns[1] += 1
        forward_count += 1
    elif kns[0] > 0 and s[kns[0] - 1, kns[1]] == '.' and visited[kns[0] - 1, kns[1]] == False:
        kns[0] -= 1
        back_count += 1
    elif kns[1] > 0 and s[kns[0], kns[1] - 1] == '.' and visited[kns[0], kns[1] - 1] == False:
        kns[1] -= 1
        back_count += 1
    else:
        can_goal = False
        break

for row in s:
    for x in row:
        counter[x] += 1

if can_goal:
    print(counter['.']-((back_count + forward_count + 1)))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys,collections;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def debug_print(maze):
    for xx in maze:
        for yy in xx:
            print(yy,end="")
        print("\n",end="")

def clear_maze(sx, sy, gx, gy, maze):
#    debug_print(maze)
    INF = 100000000
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    def bfs():
        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(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][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]
    return bfs()

H,W = Is()
maze = []
for _ in range(H):
    maze.append(list(S()))
sx, sy = 0, 0 # スタート地点の座標
gx, gy = H-1, W-1 # ゴール地点の座標
a = clear_maze(sx, sy, gx, gy, maze)
for i in range(H):
    a += maze[i].count("#")
print(H*W-a-1)

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
maze=[["" for i in range(W)] for j in range(H)]
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="#"):
            bla+=1
            maze[i][j]="#"
        else:
            whi+=1
            maze[i][j]="."

def clear_maze(sx,sy,gx,gy,maze,W,H):
    INF=100000000
    distance=[[INF for i in range(W)] for j in range(H)]
    
    def bfs():
        testx=[1,0,-1,0]
        testy=[0,1,0,-1]
        queue=[]
        
        queue.insert(0,(sy,sx))
        
        distance[sy][sx]=0
        count=0
        while len(queue):
            if(count>10000000):
                return -1
            count+=1
            x,y=queue.pop()
            
            if(x==gx and y==gy):
                break
            
            for i in range(0,4):
                nx,ny=x+testx[i],y+testy[i]
                
                if(0<=nx and nx<W and 0<=ny and ny<H):
                    if(maze[ny][nx]!="#"):
                        if(distance[ny][nx]==INF):
                            queue.insert(0,(nx,ny))
                            distance[ny][nx]=distance[y][x]+1
        return distance[gy][gx]
        
    return bfs()

area=W*H
step=clear_maze(0,0,W-1,H-1,maze,W,H)
if(step==-1):
    print(-1)
else:
    score=area-step-1-bla
    print(score)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
maze=[["" for i in range(W)] for j in range(H)]
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="#"):
            bla+=1
            maze[i][j]="#"
        else:
            whi+=1
            maze[i][j]="."

def clear_maze(sx,sy,gx,gy,maze,W,H):
    INF=100000000
    distance=[[INF for i in range(W)] for j in range(H)]
    
    def bfs():
        testx=[1,0,-1,0]
        testy=[0,1,0,-1]
        queue=[]
        
        queue.insert(0,(sy,sx))
        
        distance[sy][sx]=0
        count=0
        while len(queue):
            if(count>1000000):
                return -1
            count+=1
            x,y=queue.pop()
            
            if(x==gx and y==gy):
                break
            
            for i in range(0,4):
                nx,ny=x+testx[i],y+testy[i]
                
                if(0<=nx and nx<W and 0<=ny and ny<H):
                    if(maze[ny][nx]!="#"):
                        if(distance[ny][nx]==INF):
                            queue.insert(0,(nx,ny))
                            distance[ny][nx]=distance[y][x]+1
        return distance[gy][gx]
        
    return bfs()

area=W*H
step=clear_maze(0,0,W-1,H-1,maze,W,H)
if(step==-1):
    print(-1)
else:
    score=area-step-1-bla
    print(score)

Submission status: Wrong Answer

Solution code:
def d_grid_epainting(H, W, S):
    INF = float('inf')
    foo = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                foo+=1

    def bfs():
        # 原点は(0,0)とする
        queue = []
        queue.insert(0, (0, 0))
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[0][0] = 0
        while len(queue):
            i, j = queue.pop()
            if i == H - 1 and j == W - 1:
                # ゴール座標と一致するなら
                break
            for k in range(4):
                nh, nw = i + [1, 0, -1, 0][k], j + \
                    [0, 1, 0, -1][k]  # (i,j)の右、上、左、下
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#' and dist[nh][nw] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (nh, nw))  # 次に探索する座標
                    dist[nh][nw] = dist[i][j] + 1
        return dist[H - 1][W - 1]

    tmp = bfs()
    ans = foo-1-tmp
    return ans

H,W = [int(i) for i in input().split()]
S = [input().strip() for j in range(H)]
print(d_grid_epainting(H, W, S))

Submission status: Wrong Answer

Solution code:
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 = [2500] * 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 = 2500 # 最小の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])

if num_of_white - distance[node_num - 1] - 1 > 0:
    print(num_of_white - distance[node_num - 1] - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H, W = (int(i) for i in input().split())
S = []
for i in range(H):
	row = input()
	S.append([(0 if row[j]=="." else 1) for j in range(W)])

D = [[10000 for j in range(W)] for i in range(H)]
R = [[False for j in range(W)] for i in range(H)]

N_black = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == 1:
			D[i][j] == -1
			R[i][j] == True
			N_black += 1

def update(i0, j0, i1, j1):
	global D
	center = D[i0][j0]
	adj = D[i1][j1]
	r = R[i1][j1]
	if adj != -1 and r == False and center + 1 < adj:
		D[i1][j1] = center + 1


def check_around(i ,j):
	# UP
	if i != 0:
		update(i, j, i-1, j)
	# LEFT
	if j != 0:
		update(i, j, i, j-1)
	# DOWN
	if i != H-1:
		update(i, j, i+1, j)
	# RIGHT
	if j != W-1:
		update(i, j, i, j+1)

def minimum_point():
	global H, W
	m = 10001
	ni = 0
	nj = 0
	for i in range(H):
		for j in range(W):
			d = D[i][j]
			if d != -1 and R[i][j] == False and d < m:
				m = d
				ni = i
				nj = j
	return (ni, nj)


D[0][0] = 1
R[0][0] = True

pi = 0
pj = 0

for idx in range(W*H):
	check_around(pi, pj)
	pi, pj = minimum_point()
	R[pi][pj] = True
	# print(pi, pj)

if D[H-1][W-1] == 10000:
	print(-1)
else:
	print(W*H-D[H-1][W-1]-N_black)

Submission status: Wrong Answer

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, h, w, d, q):
    if q.empty(): return d[h - 1][w - 1]
    k, i, j = q.get()
    if i > 1 and m[i - 1][j] == '.' and k + 1 < d[i - 1][j]:
        d[i - 1][j] = k + 1
        q.put((k + 1, i - 1, j))
    if i < h - 1 and m[i + 1][j] == '.' and k + 1 < d[i + 1][j]:
        d[i + 1][j] = k + 1
        q.put((k + 1, i + 1, j))
    if j > 1 and m[i][j - 1] == '.' and k + 1 < d[i][j - 1]:
        d[i][j - 1] = k + 1
        q.put((k + 1, i, j - 1))
    if j < w - 1 and m[i][j + 1] == '.' and k + 1 < d[i][j + 1]:
        d[i][j + 1] = k + 1
        q.put((k + 1, i, j + 1))
    return s(m, h, w, d, q)

h, w = map(int, raw_input().split())
m = [raw_input()[:w] for _ in range(h)]
q = Queue.PriorityQueue()
d = [None] * h
for i in range(h):
    d[i] = [1000000] * w
d[0][0] = 1
for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            q.put((d[i][j], i, j))
c = s(m, h, w, d, q)
if c == 1000000: print -1
else:
    a = 0
    for row in m:
        a += row.count('#')
    print h * w - c - a

Submission status: Wrong Answer

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

    # for i in range(h):
    #     print(maze[i])

    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)]
    hist[0][0] = 1


    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+[0,1,0,-1][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
            # print("x,y", x,y)
            # print("nx,ny", nx,ny)

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

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

solve()

Submission status: Wrong Answer

Solution code:
H, W = (int(i) for i in input().split())
S = []
for i in range(H):
	row = input()
	S.append([(0 if row[j]=="." else 1) for j in range(W)])

D = [[10000 for j in range(W)] for i in range(H)]
R = [[False for j in range(W)] for i in range(H)]

N_black = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == 1:
			D[i][j] == -1
			R[i][j] == True
			N_black += 1

def update(i0, j0, i1, j1):
	global D
	center = D[i0][j0]
	adj = D[i1][j1]
	r = R[i1][j1]
	if adj != -1 and r == False and center + 1 < adj:
		D[i1][j1] = center + 1


def check_around(i ,j):
	# UP
	if i != 0:
		update(i, j, i-1, j)
	# LEFT
	if j != 0:
		update(i, j, i, j-1)
	# DOWN
	if i != H-1:
		update(i, j, i+1, j)
	# RIGHT
	if j != W-1:
		update(i, j, i, j+1)

def minimum_point():
	global H, W
	m = 10000
	ni = 0
	nj = 0
	for i in range(H):
		for j in range(W):
			d = D[i][j]
			if d != -1 and R[i][j] == False and d < m:
				m = d
				ni = i
				nj = j
	return (ni, nj)


D[0][0] = 1
R[0][0] = True

pi = 0
pj = 0

for idx in range(W*H):
	check_around(pi, pj)
	pi, pj = minimum_point()
	R[pi][pj] = True
	# print(pi, pj)

if D[H-1][W-1] == 10000:
	print(-1)
else:
	print(W*H-D[H-1][W-1]-N_black)