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:
H,W = map(int, input().split())
S = [input() for i in range(H)]
queue = [(0,0,1)]
done ={(0,0)}
count = sum(row.count("#") for row in S)

def bfs(x,y,c):
    if(x<0 or y<0 or x>-W or y>=H or S[y][x]=="#"):
        return
    
    if(x,y) in done:
        return
    
    queue.append((x,y,c+1))
    done.add((x,y))

dx = [1,-1,0,0]
dy = [0,0,1,-1] 
flag= -1
while queue:
    x,y,c = queue.pop(0)
    if x==W-1 and y==H-1:
        flag=1
        break
    for i in range(4):
        bfs(x+dx[i],y+dy[i],c)

print(flag if flag == -1 else (H*W-count-c))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    visit[y][x]=True
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H):
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    visit[y][x]=True
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        break
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H):
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[None] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([None] * (W + 2))
s.append(["#"] * (W + 2))
D.append([None] * (W + 2))
# print(s)
# print(white_num)


def search(i, j):  # (i,j)からの最短経路長を求める再帰関数
    #print("({},{})".format(i, j))
    if i == H and j == W:
        return 0
    if s[i][j] == "#":
        return inf
    if D[i][j] is not None:
        return D[i][j]
    D[i][j] = min(search(i, j + 1), search(i + 1, j)) + 1
    return D[i][j]


white_min = search(1, 1) + 1
if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W = map(int,input().split())
H += -1
W += -1
import sys
ma = [[c for c in l.strip()] for l in sys.stdin]
ya = []
for s in ma:
  ya.extend(s)
count = ya.count(".")
ma = np.array(ma,"U10")
ma[0][0] = 1
que = []
que.append([0,0])
while len(que) > 0:
  y,x = que.pop(0)
  if y == H and x == W:
    break
  score = ma[y][x]
  try:
    if y != 0:
      y1 = ma[y-1][x] 
  except:
    pass
  try:
    y2 = ma[y+1][x]
  except:
    pass
  try:
    if x != 0:
      x1 = ma[y][x-1]
  except:
    pass
  try:
    x2 = ma[y][x+1] 
  except:
    pass
  try:
    if y1 == ".":
      ma[y-1][x] = str(int(score) + 1)
      que.append([y-1, x])
  except:
    pass
  try:
    if y2 == ".":
      ma[y+1][x] = str(int(score) + 1)
      que.append([y+1, x])
  except:
    pass
  try:
    if x1 == ".":
      ma[y][x-1] = str(int(score) + 1)
      que.append([y, x-1])
  except:
    pass
  try:
    if x2 == ".":
      ma[y][x+1] = str(int(score) + 1)
      que.append([y, x+1])
  except:
    pass
if ma[H][W] == ".":
  print(-1)
else:
  ten = int(ma[H][W])
  print(count - ten)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import chain
H, W = map(int, input().split(' '))
Maze = [list(input()) for _ in range(H)]
White = list(chain.from_iterable(Maze)).count('.')
Maze[0][0] = 1
q = deque([])
current = [0, 0]
q.append(current)

dir_x = [1, -1, 0, 0]
dir_y = [0, 0, 1, -1]
while len(q) > 0:
    now_y, now_x = q.popleft()
    print(now_y, now_x)
    if now_y == H-1 and now_x == W-1 : break
    for (dx, dy) in zip(dir_x, dir_y):
        if 0 <= now_y + dy <= H-1 and 0 <= now_x + dx <= W-1 and Maze[now_y + dy][now_x + dx] == '.':
            Maze[now_y + dy][now_x + dx] = Maze[now_y][now_x] + 1
            q.append([now_y + dy, now_x + dx])


if Maze[H-1][W-1] == '.': print(-1)
else: print(White - Maze[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
masu = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
INF = 100000
cood = (0, 0)
d = [[INF for _ in range(w)] for _ in range(h)]
d[0][0] = 0

black_num = 0
for i in range(h):
    black_num += masu[i].count('#')

que = queue.Queue()
que.put((0, 0))
while not que.empty():
    cood = que.get()
    if cood[0] == h-1 and cood[1] == w-1:
        break
    for i in range(4):
        ncood = (cood[0] + dy[i], cood[1] + dx[i])
        if 0 <= ncood[0] and ncood[0] < h and 0 <= ncood[1] and ncood[1] < w and masu[ncood[0]][ncood[1]] != '#' and d[ncood[0]][ncood[1]] == INF:
            que.put(ncood)
            d[ncood[0]][ncood[1]] = d[cood[0]][cood[1]] + 1


print(h*w - d[h-1][w-1] - 1 - black_num)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
s=[]
for i in range(H):
    s.append(input().strip())
dist=[[float("inf")]*W for i in range(H)]
Q=[]
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            Q.append((i,j))
dist[0][0]=0
Q=sorted(Q,key=lambda x: dist[x[0]][x[1]])
while len(Q) > 0:
    pt=Q.pop(0)
    if pt==(H-1,W-1):
        break
    dpt = dist[pt[0]][pt[1]]
    for nbr in [(pt[0]-1,pt[1]),(pt[0],pt[1]-1),(pt[0]+1,pt[1]),(pt[0],pt[1]+1)]:
        if nbr in Q:
            dist[nbr[0]][nbr[1]] = min(dist[nbr[0]][nbr[1]],dpt+1)
#全体-黒マスー最短路
print(max(H*W-sum(i.count("#") for i in s)-dist[-1][-1]-1,-1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
a=deque()
while (q != a):
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

if Dis[H-1][W-1]:
    print(-1)
else:
    print(Shiro-Dis[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            whitecount += 1

a = 0
b = 0

while not(a == h - 1 and b == w - 1):
    if a < h - 1 and s[a+1][b] == '.':
        a += 1
    elif b < w - 1 and s[a][b+1] == '.':
        b += 1
    else:
        break

if not(a == h - 1 and b == w - 1):
    print(-1)
else:
    print(whitecount-h-w+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
INF = 500000000000
sys.setrecursionlimit(2147483647)

def bfs(posit):
    y,x = posit
    n = [(y - 1, x), (y  + 1, x), (y, x - 1), (y, x + 1)]
    for ny, nx in n:
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "#":
            temp = dist[ny][nx]
            dist[ny][nx] = min(temp, dist[y][x] + 1)
            if temp != dist[ny][nx]:
                route.append((ny, nx))
            if (ny, nx) == (H - 1, W - 1):
                return
    if len(route) > 0:
        bfs(route.popleft())

H,W = [int(i) for i in input().split()]
s = []
route = deque()
black = 0
for i in range(H):
    po = list(input())
    black += po.count("#")
    s.append(po)
dist = [[INF for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
bfs((0, 0))
if dist[H - 1][W - 1]:
    print(H * W - black - dist[H - 1][W - 1] - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = [[0, 0, 0]]
distances = [[float('inf') for i in range(W)] for j in range(H)]
distances[0][0] = 0
ans = H * W
black = 0
for ss in s:
    black += ss.count('#')
while len(queue) > 0:
    #n = queue.pop()
    n = queue[0]
    queue = queue[:0]
    for d in dic:               
        nx = n[0] + d[0]
        ny = n[1] + d[1]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue 
        if nx == W-1 and ny == H-1:
            ans = min(distances[n[1]][n[0]] + 1, ans)
            print(-1 if ans == H*W else H*W - (ans+1) - black)
            exit()
        elif s[ny][nx] == "." and distances[ny][nx] > distances[n[1]][n[0]] + 1:
            distances[ny][nx] = distances[n[1]][n[0]] + 1
            queue.append([nx, ny])
print(-1 if ans == H*W else H*W - (ans+1) - black)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = [[0, 0, 0]]
distances = [[H*W for i in range(W)] for j in range(H)]
distances[0][0] = 0
ans = H * W
black = 0
for ss in s:
    black += ss.count('#')
while len(queue) > 0:
    n = queue[0]
    queue = queue[:0]
    for d in dic:               
        nx = n[0] + d[0]
        ny = n[1] + d[1]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue 
        if nx == W-1 and ny == H-1:
            ans = min(distances[n[1]][n[0]] + 1, ans)
        elif s[ny][nx] == "." and distances[ny][nx] == H*W:
            distances[ny][nx] = distances[n[1]][n[0]] + 1
            queue.append([nx, ny])
print(-1 if ans == H*W else H*W - (ans+1) - black)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = [[0, 0, 0]]
distances = [[float('inf') for i in range(W)] for j in range(H)]
distances[0][0] = 0
ans = H * W
black = 0
for ss in s:
    black += ss.count('#')
while len(queue) > 0:
    n = queue.pop()
    for d in dic:               
        nx = n[0] + d[0]
        ny = n[1] + d[1]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue 
        if nx == W-1 and ny == H-1:
            ans = min(distances[n[1]][n[0]] + 1, ans)
        elif s[ny][nx] == "." and distances[ny][nx] > distances[n[1]][n[0]] + 1:
            distances[ny][nx] = distances[n[1]][n[0]] + 1
            queue.append([nx, ny])
print(H * W - (ans + 1) - black )
#print(ans)

Submission status: Wrong Answer

Solution code:
#abc088d

H,W=map(int,raw_input().split())
maze=[]
for i in xrange(H):
 maze.append(list(raw_input()))
d=[[-1 for i in xrange(W+1)] for j in xrange(H+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
 q=[]
 q.insert(0,(0,0))
 d[sx][sy]=0
 while len(q):
  x,y=q.pop()
  if x==gx and y==gy:
   break
  for i in xrange(4):
   nx,ny=x+dx[i],y+dy[i]
   if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='#' and d[nx][ny]==-1:
    q.insert(0,(nx,ny))
    d[nx][ny]=d[x][y]+1
 return d[gx][gy]
sx,sy=0,0
gx,gy=H-1,W-1

def cntsharp():
 cnt=0
 for i in xrange(H):
  cnt+=maze[i].count('#')
 return cnt
print H*W-(bfs()+cntsharp())-1

Submission status: Wrong Answer

Solution code:
data = input("")
h = int(data.split(" ")[0])
w = int(data.split(" ")[1])
s = ["0"]*h
count = 0
for i in range(h):
    s[i] = input("")
    for j in range(w):
        if s[i][j] == ".":
            count += 1

move_x = [1, -1, 0, 0]
move_y = [0, 0, 1, -1]
map_passed = [[-1 for j in range(w)] for i in range(h)]

queue_x = []
queue_y = []
queue_x.append(0)
queue_y.append(0)
map_passed[0][0] = 1
while len(queue_x) != 0:
    x = queue_x.pop()
    y = queue_y.pop()
    for i in range(4):
        nextX = x + move_x[i]
        nextY = y + move_y[i]

        if (nextX >= 0) and (nextX < w) and (nextY >= 0) and (nextY < h):
            if not(nextX == w-1 and nextY == h-1) and map_passed[nextY][nextX] == -1 and s[nextY][nextX] == ".":
                map_passed[nextY][nextX] = map_passed[y][x] + 1
                queue_x.append(nextX)
                queue_y.append(nextY)
if map_passed[h-1][w-2]>map_passed[h-2][w-1]:
    ans = map_passed[h-2][w-1]+1
else:
    ans = map_passed[h-1][w-2]+1
print(count - ans)

Submission status: Wrong Answer

Solution code:
import copy
h,w = (int(i) for i in input().split())
x = [input() for i in range(h)]
cf,list1,num = [[0,0]],[[0,0]],1
while [h-1,w-1] not in cf and len(list1) != 0:
	list2 = []
	for j in list1:
		list3 = [[j[0]+1,j[1]],[j[0]-1,j[1]],[j[0],j[1]+1],[j[0],j[1]-1]]
		for j2 in list3:
			if (-1<j2[0]<h) and (-1<j2[1]<w) and (j2 not in cf) and (x[j2[0]][j2[1]]=="."):
				cf.append(j2)
				list2.append(j2)
	num += 1
	list1 = copy.deepcopy(list2)
num2 = 0
for k in x: num2 += k.count(".")
print(num2-num)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

S = np.zeros((H,W))

for h in range(H):
    sh = list(input())

    for w in range(W):
        if sh[w] == '.': S[h,w] = 0
        elif sh[w] == '#': S[h,w] = 1

C = S.copy()
C = np.append(C, np.ones((H,1)), axis=1)
C = np.append(C, np.ones((1,W+1)), axis=0)

#print(C)

i,j = 0,0

Cp = np.ones_like(C)

for t in range(1145141919):
    for h in range(H):
        for w in range(W):
            if C[h,w] == 0:
                #if C[h,np.min([W-1,w+1])] == 1 and C[np.min([H-1,h+1]),w] == 1: C[h,w] = 1
                if C[h,w+1] == 1 and C[h+1,w] == 1: C[h,w] = 1
                if (h,w) == (H-1,W-1): C[h,w] = 0
        
    #print(C)
                
    if np.allclose(C,Cp): break

    Cp = C.copy()

#print(C)

if C[0,0] == 1: print(-1)
else:
    ans = (H-1)*(W-1) - np.sum(S)
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

S = np.zeros((H,W))

for h in range(H):
    sh = list(input())

    for w in range(W):
        if sh[w] == '.': S[h,w] = 0
        elif sh[w] == '#': S[h,w] = 1

C = S.copy()

i,j = 0,0

Cp = np.ones_like(C)

for t in range(114514):
    for h in range(H):
        for w in range(W):
            if C[h,w] == 0:
                if C[h,np.min([W-1,w+1])] == 1 and C[np.min([H-1,h+1]),w] == 1: C[h,w] = 1
                elif (h,w) == (H-1,W-1): C[h,w] = 0 
                
    #print(C)
                
    if np.allclose(C,Cp): break

    Cp = C.copy()

if C[0,0] == 1: print(-1)
else:
    ans = (H-1)*(W-1) - np.sum(S)
    print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, raw_input().split())
maze = [raw_input() for _ in xrange(h)]
visited = [[False] * w for _ in xrange(h)]
que = deque([(0, 0)])  # prepare for bfs.
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
flag = False
while que:
    x, y = que.popleft()
    if (x, y) == (h - 1, w - 1):
        flag = True
        break
    for i in xrange(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < h and 0 <= ny < w:
            if not visited[nx][ny] and maze[nx][ny] == '.':
                que.append((nx, ny))
                visited[nx][ny] = True
print h * w - h - w + 1 - sum([_.count('#') for _ in maze]) if flag else -1

Submission status: Wrong Answer

Solution code:
a=map(int, raw_input().split())
lis=[]
for i in range(a[0]):
    b=list(raw_input())
    lis.append(b)

pro=[]
cou=0
for i in range(a[0]):
    pre=[]
    for j in range(a[1]):
        if lis[i][j]=="#":
            cou+=1
        pre.append(2501)
    pro.append(pre)

while True:
    ch=0
    for i in range(a[0]):
        for j in range(a[1]):
            if lis[i][j]==".":
                if i==0:
                    if j==0:
                        pro[i][j]=1
                    elif j==a[1]-1:
                        u = 2501
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = 2501
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                elif i==a[0]-1:
                    if j==0:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = 2501
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                else:
                    if j==0:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j+ 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
    if ch==0:
        break
if pro[a[0]-1][a[1]-1]==-1:
    print -1
else:
    print a[0]*a[1]-cou-pro[a[0]-1][a[1]-1]

Submission status: Wrong Answer

Solution code:
a=map(int, raw_input().split())
lis=[]
for i in range(a[0]):
    b=list(raw_input())
    lis.append(b)

pro=[]
cou=0
for i in range(a[0]):
    pre=[]
    for j in range(a[1]):
        if lis[i][j]=="#":
            cou+=1
        pre.append(2501)
    pro.append(pre)

while True:
    ch=0
    for i in range(a[0]):
        for j in range(a[1]):
            if lis[i][j]==".":
                if i==0:
                    if j==0:
                        pro[i][j]=1
                    elif j==a[1]-1:
                        u = 2501
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = 2501
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                elif i==a[0]-1:
                    if j==0:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = 2501
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                else:
                    if j==0:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j+ 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
    if ch==0:
        break


print a[0]*a[1]-cou-pro[a[0]-1][a[1]-1]

Submission status: Wrong Answer

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

# AtCoder Beginner Contest
# Problem D

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

    total_count = height * width
    white_count_min = (height - 1) + width

    current_black_count = 0

    for i in range(len(s)):
        current_black_count += ','.join(list(s[i])).count('#')

    result = total_count - (current_black_count + white_count_min)

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

Submission status: Wrong Answer

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

# AtCoder Beginner Contest
# Problem D

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

    total_count = height * width
    white_count_min = (height - 1) + width

    current_black_count = 0

    for i in range(len(s)):
        current_black_count += ','.join(list(s[i])).count('#')

    result = total_count - (current_black_count + white_count_min)

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

Submission status: Wrong Answer

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

# AtCoder Beginner Contest
# Problem D

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

    total_count = height * width
    white_count_min = (height - 1) + width

    current_black_count = 0

    for i in range(len(s)):
        current_black_count += ','.join(list(s[i])).count('#')

    result = total_count - (current_black_count + white_count_min)

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

Submission status: Wrong Answer

Solution code:
import sys

H, W = [int(x) for x in input().split()]

grid = [[c for c in input()] for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
dist = [[0 for i in range(W)] for j in range(H)]

# 白の数
nw = sum([line.count('.') for line in grid])

# 最短ルートの探索(幅優先探索)
start = (0, 0)
goal = (H - 1, W - 1)

visited[start[0]][start[1]] = True
dist[start[0]][start[1]] = 1
queue = [start]
while len(queue) > 0:
    v = queue[0]
    queue.remove(v)

    if v == goal:
        print(nw - dist[v[0]][v[1]])
        sys.exit()
    else:
        if (v[0] > 0 and not visited[v[0] - 1][v[1]]
                and not grid[v[0] - 1][v[1]] == '.'):
            queue.append((v[0] - 1, v[1]))
            visited[v[0] - 1][v[1]] = True
            dist[v[0] - 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[0] < H - 1 and not visited[v[0] + 1][v[1]]
                and not grid[v[0] + 1][v[1]] == '.'):
            queue.append((v[0] + 1, v[1]))
            visited[v[0] + 1][v[1]] = True
            dist[v[0] + 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[1] > 0 and not visited[v[0]][v[1] - 1]
                and not grid[v[0]][v[1] - 1] == '.'):
            queue.append((v[0], v[1] - 1))
            visited[v[0]][v[1] - 1] = True
            dist[v[0]][v[1] - 1] = dist[v[0]][v[1]] + 1

        if (v[1] < W - 1 and not visited[v[0]][v[1] + 1]
                and not grid[v[0]][v[1] + 1] == '.'):
            queue.append((v[0], v[1] + 1))
            visited[v[0]][v[1] + 1] = True
            dist[v[0]][v[1] + 1] = dist[v[0]][v[1]] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
import sys

H, W = [int(x) for x in input().split()]

grid = [[c for c in input()] for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
dist = [[0 for i in range(W)] for j in range(H)]

# 白の数
nw = sum([line.count('.') for line in grid])

# 最短ルートの探索(幅優先探索)
start = (0, 0)
goal = (H-1, W-1)

visited[start[0]][start[1]] = True
dist[start[0]][start[1]] = 1
queue = [start]
while len(queue) > 0:
    v = queue[0]
    queue.remove(v)

    if v == goal:
        print(nw - dist[v[0]][v[1]])
        sys.exit()
    else:
        if v[0] > 0 and not visited[v[0]-1][v[1]]:
            queue.append((v[0]-1, v[1]))
            visited[v[0]-1][v[1]] = True
            dist[v[0]-1][v[1]] = dist[v[0]][v[1]] + 1

        if v[0] < H - 1 and not visited[v[0]+1][v[1]]:
            queue.append((v[0]+1, v[1]))
            visited[v[0]+1][v[1]] = True
            dist[v[0]+1][v[1]] = dist[v[0]][v[1]] + 1

        if v[1] > 0 and not visited[v[0]][v[1]-1]:
            queue.append((v[0], v[1]-1))
            visited[v[0]][v[1]-1] = True
            dist[v[0]][v[1]-1] = dist[v[0]][v[1]] + 1

        if v[1] < W - 1 and not visited[v[0]][v[1]+1]:
            queue.append((v[0], v[1]+1))
            visited[v[0]][v[1]+1] = True
            dist[v[0]][v[1]+1] = dist[v[0]][v[1]] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = set((0, 0))
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if maze[y + dy][x + dx] == '.':
            if (y + dy, x + dx) not in visited:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))
                visited.add((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)