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 numpy as np #1.11.0
#import matplotlib as plt #1.5.1
import copy 
import math

class Pqueue: #優先度付きqueue
  def __init__(self, buff = []):
    self.buff = buff[:]
    for n in reversed(range(int(len(self.buff) / 2))):
      _downheap(self.buff, n)

  def enqueue(self, data): #データの追加
    self.buff.append(data)
    _upheap(self.buff, len(self.buff) - 1)

  def dequeue(self): #最小値を取り出す
    if len(self.buff) == 0:
      raise IndexError
    value = self.buff[0]
    last = self.buff.pop()
    if len(self.buff) > 0: #ヒープの再構築
      self.buff[0] = last
      _downheap(self.buff, 0)
    return value

  def min_value(self): #最小値を求める
    if len(self.buff) == 0:
      raise IndexError
    return self.buff[0]

  def isEmpty(self):
    return len(self.buff) == 0

def _downheap(buff, n):
  size = len(buff)
  while True:
    c = 2 * n + 1
    if c >= size:
      break
    if c + 1 < size:
      if buff[c] > buff[c + 1]:
        c += 1
    if buff[n] <= buff[c]:
      break
    temp = buff[n]
    buff[n] = buff[c]
    buff[c] = temp
    n = c

def _upheap(buff, n):
  while True:
    p = int((n - 1) / 2)
    if p < 0 or buff[p] <= buff[n]:
      break
    temp = buff[n]
    buff[n] = buff[p]
    buff[p] = temp
    n = p

OPEN = 1
CLOSE = 0

# 状態
class State: 
  def __init__(self, row, col, p_row, p_col, g_r, g_c, move, kind = OPEN):
    self.row = row
    self.col = col 
    self.p_row = p_row #一手前
    self.p_col = p_col #一手前
    self.g_r = g_r #goal
    self.g_c = g_c #goal
    self.move = move #手数
    self.cost = move + huristic(row, col, g_r, g_c)
    self.kind = kind #OPEN or CLOSE
  
  def __lt__(x, y):
    return x.cost < y.cost
  def __le__(x, y):
    return x.cost <= y.cost
  def __gt__(x, y):
    return x.cost > y.cost
  def __ge__(x, y):
    return x.cost >= y.cost

  #def __cmp__(x, y):
  #  return x.cost - y.cost

def huristic(row, col, g_r, g_c):
  h = g_r - row + g_c - col
  return h

def hash(row, col):
  ans = []
  ans.append(row)
  ans.append(col)
  return ans
############## A*探索 ################
h, w = list(map(int, input().split())) # 整数

a = []
for i in range(h):
    b = input()
    a.append(b)
"""
h = 3
w = 3
a = ['..#', '#..', '...']
"""

white = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == ".":
      white += 1

flag = 0
Start = State(0, 0, None, None, h, w, 0, kind=OPEN)
pq = Pqueue()
pq.enqueue(Start)
table = {} 
#局面記憶するハッシュtable
#table[tuple(hash(row, col))] = State 
table[tuple(hash(0,0))] = Start


while pq.isEmpty() == False:
  now_state = pq.dequeue() # f(=g+h)が最小の状態を考える
  if now_state.kind == OPEN: #CLOSEの場合はwhileの次へ
    for x in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
      if (0 <= now_state.row + x[0] < h) and (0 <= now_state.col + x[1] < w) and (a[now_state.row + x[0]][now_state.col + x[1]] == "."):
        n_r = now_state.row + x[0]
        n_c = now_state.col + x[1]
        key = tuple(hash(n_r, n_c)) #ハッシュ
        if key in table: #以前出てきた場面と同じ場面がある
          pre_appear_state = table[key] #以前出てきた状態
          if pre_appear_state.move > now_state.move + 1: # hは同じなのでgで比較
            if pre_appear_state.kind == OPEN: 
              pre_appear_state.kind = CLOSE #元々を廃棄して
              pre_appear_state = State(n_r, n_c, now_state.row, now_state.col, h, w, now_state.move + 1) #書き換え
              table[key] = pre_appear_state #更新
            else:
              pre_appear_state.p_row = now_state.row
              pre_appear_state.p_col = now_state.col
              pre_appear_state.cost = pre_appear_state.cost - pre_appear_state.move + now_state.move + 1
              pre_appear_state.move = now_state.move + 1
              pre_appear_state.kind = OPEN
            pq.enqueue(pre_appear_state)
        else: #以前出てきていない
          next_state = State(n_r, n_c, now_state.row, now_state.col, h, w, now_state.move + 1)
          if n_r == h - 1 and n_c == w - 1: #GOAL
            flag = next_state.move + 1
            break
            """
            answer_move_count = 0
            ans = []
            a = next_state
            while a.prev != None: 
              ans.append(a.board)
              a = a.prev
              answer_move_count += 1
            ans.append(start)
            for i in range(answer_move_count + 1):
              print(ans[answer_move_count - i])
            return
            """
          pq.enqueue(next_state)
          table[key] = next_state
      now_state.kind = CLOSE

if flag == 0: # goalが見つからない 
  print(-1)
else:
  ans = white - flag
  print(ans)

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)

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['.']-(H + W - 1 + (back_count - (forward_count - H - W + 2))))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

h, w = [int(i) for i in input().split()]
maze = []
c = 0
for i in range(h):
    l = list(input().strip())
    maze.append(l)
    counter = Counter(l)
    c += counter['#']


def clear_maze(sx, sy, gx, gy, maze):
    INF = 100000000

    distance = [[INF for i in range(gy)] for j in range(gx)]

    def bfs():
        queue = []

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

        distance[sx][sy] = 0

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

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

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

                
                if (0 <= nx < gx) and (0 <= ny < gy):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.insert(0, (nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        
        return distance[gx-1][gy-1]

    return bfs()


try:
  print(w * h - clear_maze(0, 0, h, w, maze)-1 - c)
except:
  print('-1')

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

            if hist[ny][nx] > 1:
                break

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

solve()

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
from collections import defaultdict
G = defaultdict(list)

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret
 
def dijkstra(G, n, start):
    d = [float('inf')] * n
    d[start] = 0
    Q = set(range(n))
    preQ = None
    while len(Q) != 0:
        preQ = Q
        u = mind(Q, d)
        Q = Q - set([u])
        for v in G[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] + 1
        if Q == preQ:
            break
    return d
s = []

i2num = {}
count = 0
start = 0

for i in range(h):
    r = input()
    s.append([r[j] for j in range(w)])
    count += s[i].count('#')
num=-1
for i in range(h):
    r = s[i]
    for j in range(w):
        if r[j] != '1':
            num += 1
            i2num[(i,j)] = num
        if r[j] == 's':
            start = num
            r[j] = '0'
        elif r[j] == 'g':
            goal = num
            r[j] = '0'
G = defaultdict(list)
r = c = 1
for r in range(h):
    for c in range(w):
        t = s[r][c]
        if t == '#': continue
        num = i2num[(r,c)]
        if r - 1 >= 0 and s[r - 1][c] == '.':
            G[num].append(i2num[(r - 1, c)])
        if r + 1 < h and s[r+1][c] == '.':
            G[num].append(i2num[(r + 1, c)])
        if c - 1 >= 0 and s[r][c - 1] == '.':
            G[num].append(i2num[(r, c - 1)])
        if c + 1 < w and s[r][c + 1] == '.':
            G[num].append(i2num[(r, c + 1)])

d = dijkstra(G, h*w, start)
if d[-1] == float('inf'):
    print('-1')
else:
    print(h*w-(h+w-1)-count)

Submission status: Wrong Answer

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

inf = 10 ** 15

board = [[inf] * w for j in range(h)]
board[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [ 0, 0,-1, 1]

for i in range(w):
    for j in range(h):
        for k in range(4):
            if not (0 <= i + dx[k] < w):
                continue
            if not (0 <= j + dy[k] < h):
                continue

            if s[j][i] == '#':
                continue
            if s[j + dy[k]][i + dx[k]] == '#':
                continue
                
            board[j + dy[k]][i + dx[k]] = \
                min(board[j][i] + 1, board[j + dy[k]][i + dx[k]])

if board[j][i] >= inf:
    print(-1)
    exit()

dis = board[h - 1][w - 1] + 1
ans = h * w - dis
for j in range(h):
    ans -= s[j][:].count('#')

print(ans)

Submission status: Wrong Answer

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

inf = 10 ** 15

board = [[inf] * w for j in range(h)]
board[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [ 0, 0,-1, 1]

for i in range(w):
    for j in range(h):
        for k in range(4):
            if not (0 <= i + dx[k] < w):
                continue
            if not (0 <= j + dy[k] < h):
                continue

            if s[j][i] == '#':
                continue
            if s[j + dy[k]][i + dx[k]] == '#':
                continue
                
            board[j + dy[k]][i + dx[k]] = \
                min(board[j][i] + 1, board[j + dy[k]][i + dx[k]])

for j in range(h):
    print(board[j][:])

if board[j][i] >= inf:
    print(-1)
    exit()

dis = board[h - 1][w - 1] + 1
ans = h * w - dis
for j in range(h):
    ans -= s[j][:].count('#')

print(ans)

Submission status: Wrong Answer

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

black = 0
for si in s:
  for sij in si:
    if sij == '#':
      black += 1

cnt = 0
d = []
for i in range(h):
  d.append([])
  for j in range(w):
    d[-1].append(10 ** 9)

d[0][0] = 1
q = [(0, 0)]
for k in range(h * w):
  p = q.pop()
  i = p[0]
  j = p[1]
  dis = d[i][j]

  if i + 1 < h:
    if s[i + 1][j] == '.':
      if dis + 1 < d[i + 1][j]:
        d[i + 1][j] = dis + 1
        q.append((i + 1, j))
  if j + 1 < w:
    if s[i][j + 1] == '.':
      if dis + 1 < d[i][j + 1]:
        d[i][j + 1] = dis + 1
        q.append((i, j + 1))
  if i - 1 >= 0:
    if s[i - 1][j] == '.':
      if dis + 1 < d[i - 1][j]:
        d[i - 1][j] = dis + 1
        q.append((i - 1, j))
  if j - 1 >= 0:
    if s[i][j - 1] == '.':
      if dis + 1 < d[i][j - 1]:
        d[i][j - 1] = dis + 1
        q.append((i, j - 1))

  if len(q) <= 0:
    break

cnt = d[h - 1][w - 1]
if cnt != 10 ** 9:
  res = h * w - black - cnt
  print(res)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
print("-1")

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)
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
    elif kns[1] < W-1 and s[kns[0], kns[1] + 1] == '.' and visited[kns[0], kns[1] + 1] == False:
        kns[1] += 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['.']-(H + W + back_count - 1))
else:
    print(-1)

Submission status: Wrong Answer

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

inf = 10 ** 15

board = [[inf] * w for j in range(h)]
board[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [ 0, 0,-1, 1]

for i in range(w):
    for j in range(h):
        for k in range(4):
            if not (0 <= i + dx[k] < w):
                continue
            if not (0 <= j + dy[k] < h):
                continue

            if s[j][i] == '#':
                continue
            board[j + dy[k]][i + dx[k]] = \
                min(board[j][i] + 1, board[j + dy[k]][i + dx[k]])

if board[j][i] >= inf:
    print(-1)
    exit()

dis = board[h - 1][w - 1] + 1
ans = h * w - dis
for j in range(h):
    ans -= s[j][:].count('#')

print(ans)

Submission status: Wrong Answer

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

import numpy as np #1.11.0
#import matplotlib as plt #1.5.1
import copy 
import math

class Pqueue: #優先度付きqueue
  def __init__(self, buff = []):
    self.buff = buff[:]
    for n in reversed(range(int(len(self.buff) / 2))):
      _downheap(self.buff, n)

  def enqueue(self, data): #データの追加
    self.buff.append(data)
    _upheap(self.buff, len(self.buff) - 1)

  def dequeue(self): #最小値を取り出す
    if len(self.buff) == 0:
      raise IndexError
    value = self.buff[0]
    last = self.buff.pop()
    if len(self.buff) > 0: #ヒープの再構築
      self.buff[0] = last
      _downheap(self.buff, 0)
    return value

  def min_value(self): #最小値を求める
    if len(self.buff) == 0:
      raise IndexError
    return self.buff[0]

  def isEmpty(self):
    return len(self.buff) == 0

def _downheap(buff, n):
  size = len(buff)
  while True:
    c = 2 * n + 1
    if c >= size:
      break
    if c + 1 < size:
      if buff[c] > buff[c + 1]:
        c += 1
    if buff[n] <= buff[c]:
      break
    temp = buff[n]
    buff[n] = buff[c]
    buff[c] = temp
    n = c

def _upheap(buff, n):
  while True:
    p = int((n - 1) / 2)
    if p < 0 or buff[p] <= buff[n]:
      break
    temp = buff[n]
    buff[n] = buff[p]
    buff[p] = temp
    n = p

OPEN = 1
CLOSE = 0

# 状態
class State: 
  def __init__(self, row, col, p_row, p_col, g_r, g_c, move, kind = OPEN):
    self.row = row
    self.col = col 
    self.p_row = p_row #一手前
    self.p_col = p_col #一手前
    self.g_r = g_r #goal
    self.g_c = g_c #goal
    self.move = move #手数
    self.cost = move + huristic(row, col, g_r, g_c)
    self.kind = kind #OPEN or CLOSE
  
  def __lt__(x, y):
    return x.cost < y.cost
  def __le__(x, y):
    return x.cost <= y.cost
  def __gt__(x, y):
    return x.cost > y.cost
  def __ge__(x, y):
    return x.cost >= y.cost

  #def __cmp__(x, y):
  #  return x.cost - y.cost

def huristic(row, col, g_r, g_c):
  h = g_r - row + g_c - col
  return h

def hash(row, col):
  ans = []
  ans.append(row)
  ans.append(col)
  return ans
############## A*探索 ################
h, w = list(map(int, input().split())) # 整数

a = []
for i in range(h):
    b = input()
    a.append(b)
"""
h = 3
w = 3
a = ['..#', '#..', '...']
"""

white = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == ".":
      white += 1

flag = 0
Start = State(0, 0, None, None, h, w, 0, kind=OPEN)
pq = Pqueue()
pq.enqueue(Start)
table = {} 
#局面記憶するハッシュtable
#table[tuple(hash(row, col))] = State 
table[tuple(hash(0,0))] = Start


while pq.isEmpty() == False:
  now_state = pq.dequeue() # f(=g+h)が最小の状態を考える
  if now_state.kind == OPEN: #CLOSEの場合はwhileの次へ
    for x in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
      if (0 <= now_state.row + x[0] < h) and (0 <= now_state.col + x[1] < w) and (a[now_state.row + x[0]][now_state.col + x[1]] == "."):
        n_r = now_state.row + x[0]
        n_c = now_state.col + x[1]
        key = tuple(hash(n_r, n_c)) #ハッシュ
        if key in table: #以前出てきた場面と同じ場面がある
          pre_appear_state = table[key] #以前出てきた状態
          if pre_appear_state.move > now_state.move + 1: # hは同じなのでgで比較
            if pre_appear_state.kind == OPEN: 
              pre_appear_state.kind = CLOSE #元々を廃棄して
              pre_appear_state = State(n_r, n_c, now_state.row, now_state.col, h, w, now_state.move + 1) #書き換え
              table[key] = pre_appear_state #更新
            else:
              pre_appear_state.prev = now_state
              pre_appear_state.cost = pre_appear_state.cost - pre_appear_state.move + now_state.move + 1
              pre_appear_state.move = now_state.move + 1
              pre_appear_state.kind = OPEN
            pq.enqueue(pre_appear_state)
        else: #以前出てきていない
          next_state = State(n_r, n_c, now_state.row, now_state.col, h, w, now_state.move + 1)
          if n_r == h - 1 and n_c == w - 1: #GOAL
            flag = next_state.move + 1
            break
            """
            answer_move_count = 0
            ans = []
            a = next_state
            while a.prev != None: 
              ans.append(a.board)
              a = a.prev
              answer_move_count += 1
            ans.append(start)
            for i in range(answer_move_count + 1):
              print(ans[answer_move_count - i])
            return
            """
          pq.enqueue(next_state)
          table[key] = next_state
      now_state.kind = CLOSE

if flag == 0: # goalが見つからない 
  print(-1)
else:
  ans = white - flag
  print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def solve(posi):
    INF = 100000000000
    d = np.zeros((H, W))
    for i in range(H):
        for j in range(W):
            d[i][j] = INF
    que = [posi]
    d[posi[0],posi[1]] = 0

    move = np.array([[1,0], [-1,0], [0,1], [0,-1]])
    while len(que):
        p = que.pop(0)
        if np.allclose(posi, np.array([H-1,W-1])):
            break

        for dir in move:
            new_p = p + dir
            if 0 <= new_p[0] and new_p[0] < H and 0 <= new_p[1] and new_p[1] < W:
                if d[new_p[0],new_p[1]] == INF and maze[new_p[0]][new_p[1]] != '#':
                    que.append(new_p)
                    d[new_p[0],new_p[1]] = d[p[0], p[1]] + 1

    if d[H-1][W-1] == INF:
        return -1
    return d[H-1][W-1]

if __name__=='__main__':
    H, W  = map(int, input().split(' '))
    maze = []
    for i in range(H):
        maze.append(list(input()))
    counter = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                counter += 1

    posi = np.array([0,0])
    print(int(counter - solve(posi) - 1))

Submission status: Wrong Answer

Solution code:
import sys
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


sys.setrecursionlimit(10000)

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

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

inf = 10 ** 15

board = [[inf] * w for j in range(h)]
board[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [ 0, 0,-1, 1]

for i in range(w):
    for j in range(h):
        if s[j][i] == '#':
            board[j][i] = inf

for i in range(w):
    for j in range(h):
        for k in range(4):
            if not (0 <= i + dx[k] < w):
                continue
            if not (0 <= j + dy[k] < h):
                continue

            board[j + dy[k]][i + dx[k]] = \
                min(board[j][i] + 1, board[j + dy[k]][i + dx[k]])

if board[j][i] >= inf:
    print(-1)
    exit()

dis = board[h - 1][w - 1] + 1
ans = h * w - dis
for j in range(h):
    ans -= s[j][:].count('#')

print(ans)