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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

H,W = II()
s = [list(map(str, input())) for _ in range(H)]

w_count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            w_count += 1


v = (0,0)
check_visited = [[False]*W for _ in range(H)]
check_visited[v[0]][v[1]] = True
S = [v]
flag = False
while S:
    v1 = S.pop()
    if v1[0]==H-1 and v1[1]==W-1:
        flag = True
        break
    if v1[0]-1>=0:
        if check_visited[v1[0]-1][v1[1]] == False and s[v1[0]-1][v1[1]] == '.':
            check_visited[v1[0]-1][v1[1]] = True
            S.append((v1[0]-1,v1[1]))
    if v1[0]+1<=H-1:
        if check_visited[v1[0]+1][v1[1]] == False and s[v1[0]+1][v1[1]] == '.':
            check_visited[v1[0]+1][v1[1]] = True
            S.append((v1[0]+1,v1[1]))
    if v1[1]-1>=0:
        if check_visited[v1[0]][v1[1]-1] == False and s[v1[0]][v1[1]-1] == '.':
            check_visited[v1[0]][v1[1]-1] = True
            S.append((v1[0],v1[1]-1))
    if v1[1]+1<=W-1:
        if check_visited[v1[0]][v1[1]+1] == False and s[v1[0]][v1[1]+1] == '.':
            check_visited[v1[0]][v1[1]+1] = True
            S.append((v1[0],v1[1]+1))

if flag:
    print(w_count-(H+W-1))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
wnum=0
field=[input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]=='.':
            wnum+=1
# スタートからゴールまでの最短経路をBFSで求め、wnumからその分を引けば、最大スコアが得られる。
dist=[[-1]*W for _ in range(H)]
dist[0][0]=0
que=deque()
que.append([0,0])
while que:
    s_h,s_w=que.popleft()
    if s_h!=0:
        if field[s_h-1][s_w] =='.' and dist[s_h-1][s_w]==-1:
            que.append([s_h-1,s_w])
            dist[s_h-1][s_w]=dist[s_h][s_w]+1
    if s_h!=H-1:
        if field[s_h+1][s_w] =='.' and dist[s_h+1][s_w]==-1:
            que.append([s_h+1,s_w])
            dist[s_h+1][s_w]=dist[s_h][s_w]+1
    if s_w!=0:
        if field[s_h][s_w-1] =='.' and dist[s_h][s_w-1]==-1:
            que.append([s_h,s_w-1])
            dist[s_h][s_w-1]=dist[s_h][s_w]+1
    if s_w!=W-1:
        if field[s_h][s_w+1] =='.' and dist[s_h-1][s_w]==-1:
            que.append([s_h,s_w+1])
            dist[s_h][s_w+1]=dist[s_h][s_w]+1       

if dist[H-1][W-1]==-1:
    print(-1)
else:
    print(wnum-dist[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
wnum=0
field=[input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]=='.':
            wnum+=1
# スタートからゴールまでの最短経路をBFSで求め、wnumからその分を引けば、最大スコアが得られる。
dist=[[-1]*W for _ in range(H)]
dist[0][0]=0
que=deque()
que.append([0,0])
while que:
    s_h,s_w=que.popleft()
    if s_h!=0:
        if field[s_h-1][s_w] =='.' and dist[s_h-1][s_w]==-1:
            que.append([s_h-1,s_w])
            dist[s_h-1][s_w]=dist[s_h][s_w]+1
    if s_h!=H-1:
        if field[s_h+1][s_w] =='.' and dist[s_h+1][s_w]==-1:
            que.append([s_h+1,s_w])
            dist[s_h+1][s_w]=dist[s_h][s_w]+1
    if s_w!=0:
        if field[s_h][s_w-1] =='.' and dist[s_h][s_w-1]==-1:
            que.append([s_h,s_w-1])
            dist[s_h][s_w-1]=dist[s_h][s_w]+1
    if s_w!=W-1:
        if field[s_h][s_w+1] =='.' and dist[s_h-1][s_w]==-1:
            que.append([s_h,s_w+1])
            dist[s_h][s_w+1]=dist[s_h][s_w]+1
    
            
    #書く文章は長くなるが、if分岐させた方がfor文で回すよりも早い
    """for dh,dw in [[-1,0],[1,0],[0,-1],[0,1]]:
        nh=s_h+dh
        nw=s_w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:continue
        if field[nh][nw]=='#':continue
        if dist[nh][nw]!=-1:continue
        dist[nh][nw]=dist[s_h][s_w]+1
        que.append([nh,nw])
    """

if dist[H-1][W-1]==-1:
    print(-1)
else:
    print(wnum-(dist[H-1][W-1]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
field=[list(input()) for _ in range(H)]
judge_list=deque()
for h in range(H):
    for w in range(W):
        if field[h][w]=='.':
            judge_list.append([h,w])
judge_list.pop()
judge_list.popleft()
#print(judge_list)
dh=[1,0,-1,0]
dw=[0,-1,0,1]
counts=[]
# ここまででjudge_list完成、bit全探索を行っていく。
N=len(judge_list)
for i in range(2**N):
    change_count=0
    # 探索候補"スタック"と探索済みリストを作成する。
    seen=[]
    visited=[[False]*W for _ in range(H)]
    for j in range(N):
        if i>>j&1:
            c_h,c_w=judge_list[N-j-1]
            field[c_h][c_w]='#'
            change_count+=1
    #ここで出来上がった全ての場合に対してDFSを行い、行き着くのかどうかを調べる。
    # 探索スタート地点を探索候補"スタック"に格納する
    seen.append([0,0])
    while (len(seen)!=0):
        start_h,start_w=seen.pop()
        visited[start_h][start_w]=True
        for i in range(4):
            nh=start_h+dh[i]
            nw=start_w+dw[i]
            if nh<0 or nh>=H or nw<0 or nw>=W:continue
            if field[nh][nw]=='#':continue
            if visited[nh][nw]==True:continue
            seen.append([nh,nw])
    if visited[H-1][W-1]==True:
        counts.append(change_count)
if len(counts)==0:
    print('-1')
else:
    print(max(counts))

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
S = tuple(input().rstrip() for _ in range(H))
a=0
d=[(1,0),(-1,0),(0,1),(0,-1)]
lity=[[0 for i in range(W)] for j in range(H)]
lity[0][0]=1
def roop()->None:
  p=[(0,0)]
  while p:
    x,y=p.pop(0)
    for dx,dy in d:
      if 0<=x+dx<H and 0<=y+dy<W and S[x+dx][y+dy]=='.' and lity[x+dx][y+dy]==0:
        p.append((x+dx,y+dy))
        lity[x+dx][y+dy]=lity[x][y]+1
roop()
white=sum(t.count(".") for t in S)
x=lity[-1][-1]
print(lity)
print(x)
ans = white - x
if 0<x:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

a = [[False]*(w+2)]
for y in _in[1:]:
    a.append([False] + [x!='#' for x in y.strip()] + [False])
a.append([False]*(w+2))

ans = 0
for x in a:
    ans += sum(x)

s = deque()
s.append((1,1))

while s:
    ns = deque()
    for i, j in s:
        if i==h and j==w:
            break
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans -= 1

if i==h and j==w:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

a = [[False]*(w+2)]
for y in _in[1:]:
    a.append([False] + [x!='#' for x in y.strip()] + [False])
a.append([False]*(w+2))

ans = 0
for x in a:
    ans += sum(x)

s = deque()
s.append((1,1))

while s:
    ns = deque()
    for i, j in s:
        if i==h and j==w:
            break
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans -= 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]
ans = count + 1
already, queue = set(), [[1, 1, 1]]
while len(queue) > 0:
    q = queue.pop(0)
    if q[0] == W and q[1] == H:
        ans = q[2]
        break
    elif q[0] + H*q[1] in already:
        continue
    else:
        already.add(q[0] + H*q[1])

    for a in around:
        nextx, nexty = q[0] + a[0], q[1] + a[1]
        if s[nexty][nextx] == '.':
            queue.append([nextx, nexty, q[2] + 1])

print(count - ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]
ans = 10**5
already, queue = set(), [[1, 1, 1]]
while len(queue) > 0:
    q = queue.pop(0)
    if q[0] == W and q[1] == H:
        ans = q[2]
        break
    elif q[0] + H*q[1] in already:
        continue
    else:
        already.add(q[0] + H*q[1])

    for a in around:
        nextx, nexty = q[0] + a[0], q[1] + a[1]
        if s[nexty][nextx] == '.':
            queue.append([nextx, nexty, q[2] + 1])

if ans == 10**5:
    print(-1)
else:
    print(count - ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('#')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]
ans = 10**5
already, queue = set(), [[1, 1, 1]]
while len(queue) > 0:
    q = queue.pop(0)
    if q[0] == W and q[1] == H:
        ans = q[2]
        break
    elif q[0] + H*q[1] in already:
        continue
    else:
        already.add(q[0] + H*q[1])

    for a in around:
        nextx, nexty = q[0] + a[0], q[1] + a[1]
        if s[nexty][nextx] == '.':
            queue.append([nextx, nexty, q[2] + 1])

if ans == 10**5:
    print(-1)
else:
    print(H * W - count - ans)

Submission status: Wrong Answer

Solution code:
import collections
h, w = map(int, input().split())
queue = collections.deque()
maze = [list(input()) for _ in range(h)]

origin = 0
for i in maze:
    origin += i.count('#')
# print(origin)

ans = 9999999


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return 999999999
    if (maze[y][x] == '#'):
        return 999999999
    if (y == h - 1 and x == w - 1):
        return cnt
    maze[y][x] = '#'
    queue.append([y + 1, x, cnt + 1])
    queue.append([y - 1, x, cnt + 1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x-1, cnt+1])
    return 999999999


queue.append([0, 0, 0])
while (len(queue) > 0):
    l = queue.popleft()
    ans = min(ans, bfs(l[0], l[1], l[2]))

# print(ans)
print(h*w-origin-ans-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
m = []
for x in range(h):
  s = input()
  l = []
  for c in s:
    if c == '#':
      l.append(1)
    else:
      l.append(0)
  m.append(l)

d = [[-1 for i in range(w)] for j in range(h)]
d[0][0] = 0
next_org = [[0,0]]

while True:
  if d[h-1][w-1] != -1:
    break
  if len(next_org) == 0:
    break
  nex_org = []
  for org in next_org:
    for i in (-1, 0, 1):
      for j in (-1, 0, 1):
        x = org[0] + i
        y = org[1] + j
        if (i+j)%2 != 1 or x < 0 or y < 0 or x >= h or y >= w or m[x][y] :
          continue
        if d[x][y] == -1 or d[org[0]][org[1]] + 1 < d[x][y]:
          d[x][y] = d[org[0]][org[1]] + 1
          nex_org.append([x,y])
  next_org = nex_org  
min_d = d[h-1][w-1]

sum_masu = h*w
black_masu = sum([len([i for i in m[j] if i == 1]) for j in range(h)])
print(sum_masu-black_masu-min_d-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

inf = 10**5
h, w = map(int, input().split())
wall = 0
grid = []
for _ in range(h):
    inp = input()
    wall += inp.count("#")
    grid.append(list(inp))
grid = np.array(grid)
cost = np.ones(grid.shape, dtype=int)*inf

que = deque()
d = ((0, 1), (1, 0), (0, -1), (-1, 0))

que.append((0, 0))
cost[0][0] = 1
while que:
    x, y = que.pop()
    for dx, dy in d:
        nx = dx+x
        ny = dy+y
        if 0<=nx and nx<w and 0<=ny and ny<h and grid[ny][nx]!="#" and cost[ny][nx]==inf:
            que.append((nx, ny))
            cost[ny][nx] = cost[y][x] + 1

if cost[h-1][w-1] >= inf :
    ans = -1
else:
    ans = h*w - wall - cost[h-1][w-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

inf = 10**5
h, w = map(int, input().split())
wall = 0
grid = []
for _ in range(h):
    inp = input()
    wall += inp.count("#")
    grid.append(list(inp))
grid = np.array(grid)
cost = np.ones(grid.shape, dtype=int)*inf

que = deque()
d = ((0, 1), (1, 0), (-1, 0), (0, -1))

que.append((0, 0))
cost[0][0] = 0
while que:
    x, y = que.pop()
    for dx, dy in d:
        nx = dx+x
        ny = dy+y
        if 0<=nx and nx<w and 0<=ny and ny<h and grid[ny][nx]!="#" and cost[ny][nx]==inf:
            que.append((nx, ny))
            cost[ny][nx] = cost[y][x] + 1

if cost[-1][-1] >= inf :
    ans = -1
else:
    ans = h*w - wall - cost[-1][-1] -1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
inf = 10**5
h, w = map(int, input().split())
wall = 0
grid = []
for _ in range(h):
    inp = input()
    wall += inp.count("#")
    grid.append([1 if i == "." else inf for i in inp])
grid = np.array(grid)
cost = np.ones(grid.shape, dtype=int)*inf

todo = [(0, 0)]     #cost, node
heapq.heapify(todo)
seen = np.zeros(grid.shape, dtype=int)

d = ((1, 0),
     (0, 1),
     (-1, 0),
     (0, -1))

while todo:
    c, n = heapq.heappop(todo)
    ny = n//w
    nx = n%w
    seen[ny][nx] = 1
    cost[ny][nx] = c

    for dx, dy in d:
        x, y =dx+nx, dy+ny
        if 0 <= x and x < w and 0 <= y and y < h and seen[y][x] == 0:
            cn = (min(cost[y][x], c+grid[y][x]), x+w*y)
            heapq.heappush(todo, cn)

ans = h*w - (cost[h-1][w-1]+1) - wall
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

maze = [0 for i in range(h)]
maze2 = [[10**5 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    li = []
    for j in s:
        li.append(j)
    maze[i] = li
 
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            cnt += 1

que = queue.Queue()
maze2[0][0] = 1
que.put([0,0])

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

while not que.empty():
    q = que.get()
    a = q[0]
    b = q[1]
    
    for i in range(4):
        c = a+dx[i]
        d = b+dy[i]
       
        
        if ((0<=c) and (c<h) and (0<=d) and (d<w) and (maze2[c][d]==100000) and (maze[c][d]=='.')):
            maze2[c][d] = maze2[a][b]+1
            que.put([c,d])
            

ans = maze2[h-1][w-1]

print(h*w - ans - cnt)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[]
cnt=0
s.append("#"*(w+2))
for i in range(h):
	x=input()
	s.append("#"+x+"#")
	cnt+=x.count(".")
s.append("#"*(w+2))
ans=[[10**7 for i in range(w+2)] for j in range(h+2)]
ans[1][1]=0
for i in range(1,h+1):
	for j in range(1,w+1):
		if ans[i][j]!=10**7 and s[i][j]==".":
			if ans[i+1][j]==10**7 and s[i+1][j]==".":
				ans[i+1][j]=ans[i][j]+1
			if ans[i-1][j]==10**7 and s[i-1][j]==".":
				ans[i-1][j]=ans[i][j]+1
			if ans[i][j+1]==10**7 and s[i][j+1]==".":
				ans[i][j+1]=ans[i][j]+1
			if ans[i][j-1]==10**7 and s[i][j-1]==".":
				ans[i][j-1]=ans[i][j]+1

y=ans[h][w]
if y==10**7:
	print(-1)
else:
	print(cnt-y-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[]
cnt=0
s.append("#"*(w+2))
for i in range(h):
	x=input()
	s.append("#"+x+"#")
	cnt+=x.count(".")
s.append("#"*(w+2))
ans=[[10**7 for i in range(w+2)] for j in range(h+2)]
ans[1][1]=0
for i in range(1,h+1):
	for j in range(1,w+1):
		if ans[i][j]!=10**7 and s[i][j]==".":
			if ans[i+1][j]>ans[i][j] and s[i+1][j]==".":
				ans[i+1][j]=ans[i][j]+1
			if ans[i-1][j]>ans[i][j] and s[i-1][j]==".":
				ans[i-1][j]=ans[i][j]+1
			if ans[i][j+1]>ans[i][j] and s[i][j+1]==".":
				ans[i][j+1]=ans[i][j]+1
			if ans[i][j-1]>ans[i][j] and s[i][j-1]==".":
				ans[i][j-1]=ans[i][j]+1

y=ans[h][w]
if y==10**7:
	print(-1)
else:
	print(cnt-y-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[]
cnt=0
s.append("#"*(w+2))
for i in range(h):
	x=input()
	s.append("#"+x+"#")
	cnt+=x.count(".")
s.append("#"*(w+2))
ans=[[10**7 for i in range(w+2)] for j in range(h+2)]
ans[1][1]=0
for i in range(1,h+1):
	for j in range(1,w+1):
		if ans[i][j]!=10**7:
			if ans[i+1][j]>ans[i][j] and s[i+1][j]==".":
				ans[i+1][j]=ans[i][j]+1
			if ans[i-1][j]>ans[i][j] and s[i-1][j]==".":
				ans[i-1][j]=ans[i][j]+1
			if ans[i][j+1]>ans[i][j] and s[i][j+1]==".":
				ans[i][j+1]=ans[i][j]+1
			if ans[i][j-1]>ans[i][j] and s[i][j-1]==".":
				ans[i][j-1]=ans[i][j]+1
y=ans[h][w]
if y==10**7:
	print(-1)
else:
	print(cnt-y-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] > ds[y][x] + 1:
                ds[ny][nx] = ds[y][x] + 1
                dfs(nx, ny)


dfs(0, 0)
d = ds[h - 1][w - 1]
if d >= 0:
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int,input().split())
S = []
maxval = 10000
blacknum = 0
for i in range(H):
    S.append(input())
board = np.zeros((H+2,W+2), dtype=np.int64)
dist = np.full((H+2,W+2), maxval, dtype=np.int64)
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == '#':
            board[i][j] = 1
            dist[i][j] = maxval
            blacknum += 1
        else:
            board[i][j] = 0
            dist[i][j] = maxval
dist[1][1] = 0
for iter in range(563):
    update_flag = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if board[i][j] == 1:
                continue
            newdist = min([dist[i-1][j], dist[i+1][j], dist[i][j-1], dist[i][j+1]])+1
            if newdist < dist[i][j]:
                dist[i][j] = newdist
                update_flag = 1
    if update_flag == 0:
        break
pass_cell = dist[H][W] + 1
maxscore = H*W - pass_cell - blacknum
if pass_cell == 1:
    print(-1)
else:
    print(maxscore)


# 最長経路は1226マスなので1226回るーぷすればいい
# 1226*2500=3065000なのできついか？
# 下に49マス右に49マスは必須なのでこれはループ1回分
# 上や左に進んだ数と同じだけ下や右に進む必要があるので、
# (1226-98)/2 + 1 = 563ループでいけそう
# →563*2500 = 1407500. 大体半分になったけどまだつらそう
# ループのたびに走査方向を切り替えると速くなる…？
# (左から右、上から下)と(右から左、下から上)の2種類持つ感じで

# 1ループで変化がなければフラグ立てて終了させる

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int,input().split())
S = []
maxval = 10000
blacknum = 0
for i in range(H):
    S.append(input())
board = np.zeros((H+2,W+2), dtype=np.int64)
dist = np.full((H+2,W+2), maxval, dtype=np.int64)
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == '#':
            board[i][j] = 1
            dist[i][j] = maxval
            blacknum += 1
        else:
            board[i][j] = 0
            dist[i][j] = maxval
dist[1][1] = 0
for iter in range(563):
    update_flag = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if board[i][j] == 1:
                continue
            newdist = min([dist[i-1][j], dist[i+1][j], dist[i][j-1], dist[i][j+1]])+1
            if newdist < dist[i][j]:
                dist[i][j] = newdist
                update_flag = 1
    if update_flag == 0:
        break
pass_cell = dist[H][W] + 1
maxscore = H*W - pass_cell - blacknum
print(maxscore)


# 最長経路は1226マスなので1226回るーぷすればいい
# 1226*2500=3065000なのできついか？
# 下に49マス右に49マスは必須なのでこれはループ1回分
# 上や左に進んだ数と同じだけ下や右に進む必要があるので、
# (1226-98)/2 + 1 = 563ループでいけそう
# →563*2500 = 1407500. 大体半分になったけどまだつらそう
# ループのたびに走査方向を切り替えると速くなる…？
# (左から右、上から下)と(右から左、下から上)の2種類持つ感じで

# 1ループで変化がなければフラグ立てて終了させる

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    c_of_sharp = 0
    for i in range(h):
        line = list(input())
        for c in line:
            if c == '#':
                c_of_sharp += 1
        f.append(line)
    sy, sx = (0, 0)
    q = deque([[sy, sx]])
    BIG = 100000
    f2 = [[BIG for i in range(w)] for j in range(h)]
    f2[0][0] = 0

    while q:
        y, x = q.pop()
        if (y, x) == (h-1, w-1):
            break
        for dy, dx in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f2[y+dy][x+dx] == BIG and \
                f[y+dy][x+dx] != '#':
                f2[y+dy][x+dx] = f2[y][x]+1
                q.appendleft([y+dy, x+dx])
    else:
        print(-1)
    print(h*w-f2[h-1][w-1]-c_of_sharp-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Q = [[0, 0, 0]]
V = [[0] * w for i in range(h)]
D = [[float("inf")] * w for i in range(h)]
st = 0
while st < len(Q):
    # print(Q)
    if Q[st] == [h-1, w-1]:
        D[-1][-1] = Q[st][2]
        break
    else:
        i = Q[st][0]
        j = Q[st][1]
        d = min(Q[st][2], D[i][j])
        D[i][j] = d

        if V[i][j] == 0:
            V[i][j] = 1
            for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
                if 0 <= i+di <= h-1 and 0 <= j+dj <= w-1 and V[i+di][j+dj] == 0:
                    Q.append([i+di, j+dj, d+1])
    st += 1

white = sum([S[i].count(".") for i in range(h)])
# print(white)

# print(D[-1][-1])

print(white - D[-1][-1] - 1)

Submission status: Wrong Answer

Solution code:
def main():

    H, W = map(int, input().split())
    grid  = []
    for _ in range(H):
        grid.append(list(input()))

    # print(grid)
    white = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                white += 1

    cur = [[0, 0]]
    goal = [H-1, W-1]
    turn = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    reached = False
    grid[0][0] = "#"
    while cur and not reached:
        temp = []
        for i, j in cur:
            if [i, j] == goal:
                reached = True
                break
            for di, dj in mv:
                i1 = i + di
                j1 = j + dj
                if 0 <= i1 < H and 0 <= j1 < W and grid[i1][j1] == ".":
                    grid[i1][j1] = "#"
                    temp.append([i1, j1])
        if not reached:
            cur = temp
            turn += 1

    return  white - (turn+1)


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



def main():
    h, w = LI()
    grid = SRL(h)
    cnt = 0
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.':
                cnt += 1
                grid[y][x] = INF



    que = deque([(0, 0)])
    grid[0][0] = 1
    while que:
        x, y = que.pop()
        cost = grid[y][x]
        for i, j in [(0,1),(1,0),(-1,0),(0,-1)]:
            nxt_x, nxt_y = x + i, y + j
            if not (0<=nxt_x<w and 0<=nxt_y<h):
                continue
            elif grid[nxt_y][nxt_x] != '#' and grid[nxt_y][nxt_x] > cost + 1:
                grid[nxt_y][nxt_x] = cost + 1
                que += [(nxt_x, nxt_y)]


    if grid[h-1][w-1] == '.':
        return -1


    return cnt - grid[h-1][w-1]







print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(stage , visited , start_x,start_y,goal_x,goal_y):
    queue = deque([[start_x,start_y]])
    visited[start_x][start_y] = 1
    while queue:
        x , y = queue.popleft()
        if [x , y] == [goal_x,goal_y]:
            return visited[x][y]
        if not queue:
            print("-1")
            exit(0)
        for dx , dy in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x , new_y = x + dx , dy + y
            #print(new_x,new_y)
            if 0 <= new_x <= goal_x and 0 <= new_y <= goal_y  and stage[new_x][new_y] == "." and visited[new_x][new_y] == -1:
                #print(new_x , new_y)
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x,new_y])
        #print(queue)
if __name__ == "__main__":
    H , W = map(int , input().split())
    stage = []
    for _ in range(H):
        stage.append(list(input()))
    start_x,start_y ,goal_x,goal_y = 0,0,H-1,W-1
    visited = [[-1] * W for _ in range(H)]
    #print(visited)
    #print(stage)
    #print(visited[0][1])
    sum = 0
    for value in stage:
        sum += value.count('.')
    #print(sum)
    print(sum - dfs(stage,visited,start_x,start_y,goal_x,goal_y))

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int, input().split())
map = [list(input()) for _ in range(h)]
dis = [[float("inf")]*w for _ in range(h)]
dy = [1,0,-1,0]
dx = [0,1,0,-1]
que = deque([])
que.append((0,0))
dis[0][0]=1
count = 0

while que:
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
        break
    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if 0<=ny<h and 0<=nx<w and map[ny][nx]!="#" \
           and dis[ny][nx]==float("inf"):
            que.append((ny,nx))
            dis[ny][nx]=dis[p[0]][p[1]]+1

for i in range(h):
    for j in range(w):
        if map[i][j]=="#":
            count+=1

print(h*w-dis[h-1][w-1]-count)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import chain


class Solver:
    def __init__(self, m):
        self.m = m
        self.label = [[-1 for _ in range(len(m[0]))] for _ in range(len(m))]

    def bfs(self, s, g):
        queue = deque()
        start = [a - 1 for a in s]
        goal = [a - 1 for a in g]
        queue.append(start)
        self.label[start[0]][start[1]] = 0
        while len(queue) > 0:
            node = queue.popleft()
            y, x = node
            dist = self.label[y][x] + 1
            if y > 0:
                if self.m[y - 1][x] != "#" and self.label[y - 1][x] == -1:
                    if y-1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y - 1, x])
                        self.label[y - 1][x] = dist
            if y < len(self.m)-1:
                if self.m[y + 1][x] != "#" and self.label[y + 1][x] == -1:
                    if y+1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y + 1, x])
                        self.label[y + 1][x] = dist
            if x > 0:
                if self.m[y][x - 1] != "#" and self.label[y][x - 1] == -1:
                    if y == goal[0] and x-1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x-1])
                        self.label[y][x-1] = dist
            if x < len(self.m[0])-1:
                if self.m[y][x + 1] != "#" and self.label[y][x + 1] == -1:
                    if y == goal[0] and x+1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x+1])
                        self.label[y][x + 1] = dist
        return -1


def main():
    H, W = list(map(int, input().split()))
    m = [list(input()) for _ in range(H)]
    sum = list(chain.from_iterable(m)).count(".")

    solver = Solver(m)
    ans = solver.bfs([1, 1], [H, W])
    print(sum - ans -1)


if __name__ == "__main__":
    main()