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:
from collections import deque

nNM = []
nNM = input().rstrip().split(' ')

nH = int(nNM[0])
nW = int(nNM[1])
nTmp = [0 for i in range(nW)]

"""
nData = [[0 for i in range(nN)] for j in range(nM)]
nS=[0 for i in range(2)]
nG=[0 for i in range(2)]
"""


graph = {}
kyori = {}
checked = {}





nWallCnt = 0

for i in range(nH):
    nTmp=input()
#    print(nTmp)
    
    for i2 in range(nW):
 
        nPoi=('%d-%d' %(i,i2))
        graph[nPoi] = []
        kyori[nPoi] = float("inf")
        checked[nPoi] = 0
        
        if i==0 and i2==0:
            nStart = ('%d-%d' %(0,0))
            kyori[nPoi] = int (0)
            continue
        elif i==nH - 1 and i2==nW - 1:
            nGoal = ('%d-%d' %(nH - 1, nW - 1))
            continue

        elif nTmp[i2]=='#':
            nWall = ('%d-%d' %(i,i2))
            nWallCnt += 1
            checked[nPoi] = 1

        else:
            if i - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i - 1, i2))

            if i + 1 < nH :
                graph[nPoi].append('%d-%d' %(i + 1 , i2))

            if i2 - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i , i2 - 1))

            if i2 + 1 < nW:
                graph[nPoi].append('%d-%d' %(i , i2 + 1))
        


root_queue = deque()
root_queue += graph[nStart]
nCount = len(graph[nStart])

for i in range(nCount):
    kyori[(graph[nStart][i])] = 1


nFlag = 0


while root_queue:
    nPoi2 = root_queue.popleft()

    if checked[nPoi2] == 0:
        if nPoi2 == nGoal:
            nFlag = 1
            break
        else:
            root_queue += graph[nPoi2]
            for i in range(len(graph[nPoi2])):
                nTmpCount = kyori[nPoi2] + 1
                if kyori[(graph[nPoi2][i])] > nTmpCount:
                    kyori[(graph[nPoi2][i])] = nTmpCount
            checked[nPoi2] = 1


if nFlag == 0:
    print('-1')
else:
    nTmp = kyori[nGoal] + 1
    nTotal = nH * nW
    nAns = nTotal - (nTmp + nWallCnt )
    print(nAns)

Submission status: Wrong Answer

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, v, q):
    if q.empty(): return -1
    k, i, j = q.get()
    if i == len(m) - 1 and j == len(m[i]) - 1: return k
    if i > 1 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
        v.add((i - 1, j))
    if i < len(m) - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
        v.add((i + 1, j))
    if j > 1 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
        v.add((i, j - 1))
    if j < len(m[i]) - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
        v.add((i, j + 1))
    return s(m, v, q)
     
h, w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
v = set((0, 0))
c = s(m, v, q)
if c == -1: print -1
else: print h * w - c - sum([r.count('#') for r in m])

Submission status: Wrong Answer

Solution code:
def fanc():
   s = []
   H,W = list(map(int, input().split()))
   for i in range(H):
      s.append(input())

   b = 0
   for i in range(H):
      for j in range(W):
         if s[i][j] == "#":
            b = b+1

   flag = [[0 for _ in range(W)] for _ in range(H)]
   Q = []
   Q.append((0,0,0))
   flag[0][0] = 1

   while Q != []:
      v = Q.pop(-1)
      if v[0:2] == (H-1,W-1):
         return H*W - b - v[2] -1
      else:
         if v[0] != 0: # up
            if (flag[v[0]-1][v[1]]==0)and(s[v[0]-1][v[1]]=="."):
               Q.append((v[0]-1, v[1],v[2]+1))
               flag[v[0]-1][v[1]] = 1
         if v[0] != H-1: # down
            if (flag[v[0]+1][v[1]]==0)and(s[v[0]+1][v[1]]=="."):
               Q.append((v[0]+1, v[1], v[2]+1))
               flag[v[0]+1][v[1]] = 1
         if v[1] != 0: # left
            if (flag[v[0]][v[1]-1]==0)and(s[v[0]][v[1]-1]=="."):
               Q.append((v[0], v[1]-1, v[2]+1))
               flag[v[0]][v[1]-1] = 1
         if v[1] != W-1: # left
            if (flag[v[0]][v[1]+1]==0)and(s[v[0]][v[1]+1]=="."):
               Q.append((v[0], v[1]+1, v[2]+1))
               flag[v[0]][v[1]+1] = 1
   return -1

print(fanc())

Submission status: Wrong Answer

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

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    visited = [[False] * w for _ in range(h)]
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or visited[y][x] == True or s[y][x] == '#':
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        visited[y][x] = True
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d if dy != dx])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nblacks = sum(si.count('#') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    visited = [[False] * w for _ in range(h)]
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or visited[y][x] == True or s[y][x] == '#':
            continue
        elif y == h and x == w:
            print((h + 1) * (w + 1) - nblacks - nsteps)
            break
        visited[y][x] = True
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d if dy != dx])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
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)]
d=[ float("inf") for i in range(H*W) ]

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

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				d[i]=min(d[i],d[v]+1)


dfs(0)

if V[H*W-1] is None:
	print -1
else:
	print H*W-(d[H*W-1]+1)-sum(c)

Submission status: Wrong Answer

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,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
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)]
d=[ float("inf") for i in range(H*W) ]

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

	while len(q)!=0:
		v=q.pop()
		V[v]=1
		for i in nl[v]:
			if V[i] is None:
				q.append(i)
				d[i]=min(d[i],d[v]+1)


dfs(0)

if V[H*W-1] is None:
	print -1
else:
	print H*W-(d[H*W-1]+1)-sum(c)

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(d[-1])

Submission status: Wrong Answer

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

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nblacks = sum(si.count('#') for si in s)

    que = deque([(0, 0, 1)])
    dys = (1, 0, -1)
    dxs = (1, 0, -1)
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y >= h or x < 0 or x >= w or s[y][x] == '#':
            continue
        elif y == h - 1 and x == w - 1:
            print(h * w - nblacks - nsteps)
            break

        for dy in dxs:
            for dx in dys:
                if dy != dx:
                    que.append((y + dy, x + dx, nsteps + 1))
    else:
        print('-1')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
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)

if V[H*W-1] is None:
	print -1
else:
	print len( filter(lambda x:x is None, V) ) - sum(c)

Submission status: Wrong Answer

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,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
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: Wrong Answer

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

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

q = deque([(0, 0, 0)])
used = {(0, 0)}
res = None

while q:
    i, j, cost = q.popleft()
    if i == w - 1 and j == h - 1:
        res = cost
        break
    for k in range(4):
        if not (0 <= i + dx[k] < w):
            continue
        if not (0 <= j + dy[k] < h):
            continue

        if s[j + dy[k]][i + dx[k]] == '#':
            continue
        if (i + dx[k], j + dy[k]) in used:
            continue

        used.add((i + dx[k], j + dy[k]))
        q.append((i + dx[k], j + dy[k], cost + 1))

if res:
    ans = h * w - cost - 1
    for j in range(h):
        print(s[j][:].count('#'))
        ans -= s[j][:].count('#')
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H, W = (int(i) for i in input().split())
e = [[i for i in input().split()] for i in range(H)]
keiro = H + W - 1
count = 0
for i in range(len(e)):
  count += e[i][0].count('#')
print(H * W - count - keiro)

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 = 2
w = 2
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 or a[0][0] == "#": # goalが見つからない 
  print(-1)
else:
  ans = white - flag
  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 = 2
w = 2
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 and a[0][0] == "#": # goalが見つからない 
  print(-1)
else:
  ans = white - flag
  print(ans)

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
if distance[hw[0]-1][hw[1]-1] == -1:
    print(-1)
else:
    print(black - distance[hw[0]-1][hw[1]-1] - 1)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
s=[]
dst=[]
INF=1e8
for i in range(H):
    s.append(input())
    dst.append([INF for i in range(W)])

gx=W-1
gy=H-1
que=[]
que.append([0,0])
dst[0][0]=0
x=[-1,1,0,0]
y=[0,0,-1,1]

goalFlag=False
while len(que)>0:
    p=que.pop(0)
    if p[0]==gx and p[1]==gy: 
        goalFlag=True
        break
    for (dx,dy) in zip(x,y):
        nextx=p[0]+dx
        nexty=p[1]+dy
        if H>nexty>=0 and W>nextx>=0 and s[nexty][nextx]=='.' and dst[nexty][nextx]==INF:
            que.append([nextx,nexty])
            dst[nexty][nextx]=dst[p[1]][p[0]]+1
print(s)
print(dst)
if goalFlag:
    count=0 
    for h in range(H):
        for w in range(W):
            if h==w==0 or (h==gy and w==gx):
                continue
            elif s[h][w]=='.':
                count+=1
    print(count-dst[gy][gx]+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>10000000000):
                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
import scipy as sp
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 sp.isinf(score):
    print(-1)
    exit(0)
else:
    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: Wrong Answer

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)

print(-1)