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: Accepted

Solution code:
from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("#")
for i in range(h):
    s[i] = ["#"]+s[i]+["#"]
s.insert(0,["#" for i in range(w+2)])
s.append(["#" for i in range(w+2)])
q = Queue()
cnt = 0
q.put([1,1,0])
s[1][1]="#"
Z = -1
while (not q.empty()):
    x,y,cnt = q.get()
    if (x,y) == (h,w):
        Z = cnt
        break
    for (i,j) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if s[i][j] != "#":
            s[i][j] = "#"
            q.put([i,j,cnt+1])
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    s = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    bc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                bc += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mt = min(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and s[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print((h * w - mt - 1) - bc if mt != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    brd = '#' * (W + 2)
    for i in range(H):
        brd += '#' + f_i.readline().rstrip() + '#'
    brd += '#' * (W + 2)
    
    INF = W * H
    move = (1, -1, W + 2, -W - 2)
    start = W + 3
    goal = (W + 2) * (H + 1) - 2
    distance = [INF] * ((W + 2) * (H + 2))
    distance[start] = 0
    q = deque()
    q.append(start)
    
    while q:
        pos = q.popleft()
        
        if pos == goal:
            black_cell = brd.count('#') - W * 2 - H * 2 - 4
            ans = H * W - black_cell - distance[pos] - 1
            print(ans)
            break
        
        for mv in move:
            next_pos = pos + mv
            if brd[next_pos] == '.' and distance[next_pos] == INF:
                q.append(next_pos)
                distance[next_pos] = distance[pos] + 1
    else:
        print(-1)

solve()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

M=["."]*H
C=[[0]*50 for i in range(50)]
L=[[0,0,0] for i in range(10**5)]

s=0
for i in range(H):
    t=list(input())
    s+=t.count("#")
    M[i]=t

c=0
i=0
p=0
while(True):
    x=L[i][0]
    y=L[i][1]
    p=L[i][2]
    if(i>c):
        print(-1)
        break
    
    if((H-1)==y and (W-1)==x):
        print(H*W-s-p-1)
        exit()

    if(y>0):
        if(M[y-1][x]=="." and C[y-1][x]==0):    
            c+=1
            L[c][0]=x
            L[c][1]=y-1
            L[c][2]=p+1
            C[y-1][x]=1
    if(x<(W-1)):
        if(M[y][x+1]=="." and C[y][x+1]==0):
            c+=1
            L[c][0]=x+1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x+1]=1
    if(y<(H-1)):
        if(M[y+1][x]=="." and C[y+1][x]==0):
            c+=1
            L[c][0]=x
            L[c][1]=y+1
            L[c][2]=p+1
            C[y+1][x]=1
    if(x>0):
       if(M[y][x-1]=="." and C[y][x-1]==0):
            c+=1
            L[c][0]=x-1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x-1]=1
    i+=1

Submission status: Accepted

Solution code:
from collections import deque


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sx][sy] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and grid[nx][ny] == "." and cost[nx][ny] == float("inf"):
                q.append((nx, ny))
                cost[nx][ny] = cost[x][y] + 1
                if nx == gx and ny == gy:
                    return cost[nx][ny]
    return -1


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
black_cnt = 0
ans = 0


for i in range(h):
    black_cnt += str(grid[i]).count("#")

can_reach = bfs(0, 0, h - 1, w - 1)

if can_reach > 0:
    print(h * w - can_reach - black_cnt)
else:
    print(can_reach)

Submission status: Accepted

Solution code:
from queue import Queue
H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[float('inf')]*W for _ in range(H)]
d[0][0] = 1
cs = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            cs += 1
            d[i][j] = 0


def check(t):
    if 0 <= t[0] < H and 0 <= t[1] < W and d[t[0]][t[1]] == float('inf'):
        return True
    return False


q = Queue()
q.put((0, 0))
while not q.empty():
    h, w = q.get()
    for v in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
        if check(v):
            d[v[0]][v[1]] = d[h][w]+1
            q.put(v)

print(H*W-cs-d[-1][-1] if not (d[-1][-1] == float('inf')) else -1)

Submission status: Accepted

Solution code:
import queue

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

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

ans = [[0 for _ in range(W)] for _ in range(H)]

q = queue.Queue()

def bfs(x,y):
	global q
	global c
	q.put([x,y])
	s[y][x] = '#'
	while not q.empty():
		x,y = q.get()
		if [x,y] == [W-1,H-1]:
			return ans[H-1][W-1]
		if x > 0 and s[y][x-1] == '.':
			q.put([x-1,y])
			ans[y][x-1] = ans[y][x] + 1
			s[y][x-1] = '#'
		if x < W-1 and s[y][x+1] == '.':
			q.put([x+1,y])
			ans[y][x+1] = ans[y][x] + 1
			s[y][x+1] = '#'
		if y > 0 and s[y-1][x] == '.':
			q.put([x,y-1])
			ans[y-1][x] = ans[y][x] + 1
			s[y-1][x] = '#'
		if y < H-1 and s[y+1][x] == '.':
			q.put([x,y+1])
			ans[y+1][x] = ans[y][x] + 1
			s[y+1][x] = '#'

	return -1

bfs = bfs(0,0)
if bfs == -1:
	print(-1)
else:
	print(count-bfs-1)

Submission status: Accepted

Solution code:
# ans = 全白マス数 - 最短距離のマス数

H,W=map(int,input().split())
grid=[None]*H
white=0
for i in range(H):
  grid[i]=input()
  white+=grid[i].count(".")
  
from collections import deque
q=deque()
q.append([0,0,0])

seen=[[False for i in range(W)] for j in range(H)]

while q:
  v=q.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  if grid[y][x]=="#" or seen[y][x]:
    continue
  if y==H-1 and x==W-1:
    print(white-(p+1))
    break
  seen[y][x]=True
  if y-1>=0:
    q.append([y-1,x,p+1])
  if y+1<H:
    q.append([y+1,x,p+1])
  if x-1>=0:
    q.append([y,x-1,p+1])
  if x+1<W:
    q.append([y,x+1,p+1])
else:
  print(-1)

Submission status: Accepted

Solution code:
#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())

inf = 1009
grid = np.zeros((h + 2, w + 2), dtype=int)
for i in range(h):
    grid[i + 1][1:-1] = np.array([1 if j == "." else 0 for j in input()])
white = grid.sum()

cost = np.ones((h+2, w+2), dtype=int)*inf
cost[1][1] = 1

d = ((1, 0), (0, 1), (-1, 0), (0, -1))
to = deque([(1, 1)])
while to:
    x, y = to.popleft()
    c = cost[x][y]
    for xi, yi in d:
        nx = x + xi
        ny = y + yi
        if not grid[nx][ny]:
            continue
        to.append((nx, ny))
        cost[nx][ny] = min(cost[nx][ny], c+1)
        grid[nx][ny] = 0

if cost[-2][-2] == inf:
    ans = -1
else:
    ans = white-cost[-2][-2]
print(ans)

Submission status: Accepted

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

q=[(0,0)]
s[0][0]=0
dxy=[(1,0),(-1,0),(0,1),(0,-1)]
while q:
    x,y=q.pop(0)
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w:
            continue
        if not 0<=ny<h:
            continue
        if s[ny][nx]=="#":
            continue
        if s[ny][nx]==".":
            s[ny][nx]=s[y][x]+1
            q.append((nx,ny))
        else:
            continue
if s[h-1][w-1]=="." or s[h-1][w-1]=="#":
    print(-1)
else:
    kuro=0
    for i in range(h):
        kuro+=s[i].count("#")

    print(h*w-s[h-1][w-1]-1-kuro)

Submission status: Accepted

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

H, W = map(int, input().split())
M = [["#" for _ in range(W+2)]]+[list("#"+input()+"#") for _ in range(H)]+[["#" for _ in range(W+2)]]
seen = deque((1, 1)) #x, y
q = deque([(1, 1, 0)]) #x, y, d
depth = -1
goal = False
wall = 0
for m in M[1:H+1]:
  for b in m[1:W+1]:
    if b == "#":
      wall += 1
while q:
  x, y, d = q.popleft()
  if x == W and y == H:
    depth = d
    goal = True
    break
  for dx, dy in zip((0, 0, -1, 1), (1, -1, 0, 0)):
    if M[y+dy][x+dx] != "#" and not (x+dx, y+dy) in seen:
      seen.append((x+dx, y+dy))
      q.append((x+dx, y+dy, d+1))

if goal:
  print(W*H-wall-(depth+1))
else:
  print(-1)

Submission status: Accepted

Solution code:
r, c = map(int, input().strip().split())

maze = [["#"] * (c + 2)] + [list("#" + input().strip() + "#") for _ in range(r)] + [["#"] * (c + 2)]

points = sum(row.count(".") for row in maze)

def BFS_maze(maze, start_pos, goal_pos, symbol_wall):
    sr, sc = start_pos
    maze[sr][sc] = symbol_wall
    queue = [(sr, sc)]

    gr, gc = goal_pos
    maze[gr][gc] = "g"

    depth = 0
    nextqueue = []

    while queue:
        depth += 1
        for pos in queue:
            posr, posc = pos
            for r, c in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + r
                nextc = posc + c
                terrein = maze[nextr][nextc]
                if terrein == "g":
                    return depth
                elif terrein == symbol_wall:
                    continue
                else:
                    maze[nextr][nextc] = symbol_wall
                    nextqueue.append((nextr, nextc))
        queue = nextqueue[:]
        nextqueue.clear()
    return -1

path_length = BFS_maze(maze, (1, 1), (r, c), "#")
print(-1 if path_length == -1 else points - path_length - 1)

Submission status: Accepted

Solution code:
dbflag=""

def next(b):
	result = []
	x,y = b
	if x -1 >= 0 and S[x-1,y]=='.' and depthS[x-1,y]== -1:
		result.append((x-1,y))
	if y -1 >= 0 and S[x,y-1]=='.' and depthS[x,y-1]== -1:
		result.append((x,y-1))
	if x +1 < H and S[x+1,y]=='.' and depthS[x+1,y]== -1:
		result.append((x+1,y))
	if y +1 < W and S[x, y+1]=='.' and depthS[x,y+1]== -1:
		result.append((x,y+1))
	
	return result

  
def debug(*args):
  if ""!=dbflag: print(*args)

if ""!=dbflag: _INDATA=open(dbflag)

def readline():
  if ""!=dbflag:return _INDATA.readline()
  else: return input()


result = -1

H, W = map(int, readline().split())

#２次元配列
import numpy as np

S= np.ndarray(shape=(H,W), dtype=object)

for i in range(0,H):
	S[i,0:W] =list(readline().rstrip())
	

wNum = S[S == "."].size
bNum = H * W - wNum

debug(H,W)
debug(S)
debug(wNum)



from collections import deque
queue = deque([])
#queue.append(A)
#queue.popleft()


depthS = np.full((H,W), -1, dtype=int)

depthS[0,0] = 0
queue.append((0,0))

while len(queue) > 0 and depthS[H-1,W-1]==-1:
	base = queue.popleft()
	baseDepth = depthS[base]

	debug("----")
	debug(base,baseDepth)
	debug("depthS")	
	debug(depthS)	


	neighbors = next(base)
	
	debug('depthS',depthS)
	for n in neighbors: depthS[n[0],n[1]]=baseDepth + 1

	debug('depthS2',depthS)
	debug('neighbors',neighbors)
	
	for n in neighbors:
		queue.append(n)
	debug("queue",queue)	


if depthS[H-1,W-1]!=-1:
	result = wNum - (depthS[H-1,W-1] + 1)
else:
	result = -1

print(result)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))

    Q = deque([(0, 0)])
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        h, w = Q.popleft()

        if h == H - 1 and w == W - 1:
            break

        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]

            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                Q.append((nh,nw))

    if d[H-1][W-1] == float('inf'):
        print(-1)
        exit()
    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

    print(cnt - d[H-1][W-1] - 1)

         

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    s=[]
    for _ in range(h):
        a=list(input())
        s.append(a)

    t=0
    b=0
    l=0
    r=0
    cntw=0
    si=[[-1 for _ in range(w)]for _ in range(h)]
    before=0
    after=0
    # print(si)
    si[0][0]=0

    tempw=0

    # print(si)
    for i in range(0,h):
        for j in range(0,w):
            if s[i][j]=='.':
                tempw+=1


    before=1
    temps=0
    flag=1
    while flag==1:
        # print(si)
        flag=0
        for i in range(0,h):
            for j in range(0,w):

                if i==0 and j ==0:
                    j=1

                if s[i][j]=='.' :
                    cntw+=1
                    if i==0 or s[i-1][j]=='#' or si[i-1][j]<0:
                        t=10000
                    else:
                        t=si[i-1][j]
                    if j ==0 or s[i][j-1]=='#' or si[i][j-1]<0:
                        # print(i)
                        # print(j)
                        # print(s[i][j-1])
                        # print(si[i][j-1])
                        l=10000
                    else:
                        l=si[i][j-1]
                    if i==h-1 or s[i+1][j] =='#' or si[i+1][j]<0:
                        b=10000
                    else:
                        b=si[i+1][j]
                    if j==w-1 or s[i][j+1]=='#' or si[i][j+1]<0:
                        r=10000
                    else:
                        r=si[i][j+1]
                    temps=min(t,l,b,r)+1
                    # print(temps)
                    if temps<si[i][j] or (si[i][j]==-1 and temps!=10001):
                        si[i][j]=temps
                        flag=1
                        # print(si)
                        # print(i)
                        # print(j)


    if si[-1][-1]<0:
        print(-1)
        return
    else:
        print(tempw-si[-1][-1]-1)





if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

INF = 10**5
d = [[10**5] * W for _ in range(H)]
d[0][0] = 0

q = deque()
q.append((0, 0))

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

while len(q):
    y, x = q.popleft()

    if y == H-1 and x == W-1:
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            maze[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

if d[H-1][W-1] == INF:
    print(-1)
else:
    black = 0
    for a in maze:
        black += a.count('#')
    
    print(H * W - black - d[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S = [list(input()) for _ in range(H)]

white = 0
for i in range(H):
  white += S[i].count('.')

q = [(0,0)]
S[0][0] = 0
while q:
  qq = []
  
  for xy in q:
    x,y = xy
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
      if not(0 <= x+dx < W) or not(0 <= y+dy < H):
        continue
      elif S[y+dy][x+dx] != '.':
        continue
      S[y+dy][x+dx] = S[y][x] + 1
      qq.append((x+dx,y+dy))
  if S[-1][-1]!=".":
      break    
  q = qq

print(white - S[-1][-1] -1 if S[-1][-1] != '.' else -1)

Submission status: Accepted

Solution code:
from collections import deque


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

black = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            black += 1


def bfs(s):
    q = deque()
    q.append(s)
    maze[s[0]][s[1]] = 1

    while len(q):
        x, y = q.popleft()

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (nx, ny) == (H - 1, W - 1) and maze[nx][ny] == '.':
                return maze[x][y] + 1
            elif (0 <= nx < H) and (0 <= ny < W) and maze[nx][ny] == '.':
                maze[nx][ny] = maze[x][y] + 1
                q.append((nx, ny))

    return 0


if maze[0][0] == '.':
    step = bfs((0, 0))
    if step:
        print(H * W - black - step)
    else:
        print(-1)
else:
    print(-1)

Submission status: Accepted

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

total_dot = 0
for sss in S:
    for s in sss:
        if s == ".":
            total_dot += 1

move = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 1
while stack:
    cur_stack = stack
    stack = []
    for si,sj in cur_stack:
        for mi,mj in move:
            i,j = si+mi,sj+mj
            if 0 > i or i >= h or 0 > j or j >= w:
                continue
            next_mass = S[i][j]
            if next_mass == "#":
                continue
            elif next_mass == ".":
                S[i][j] = cnt
                stack.append([i,j])
    cnt += 1
# [print(s) for s in S]
print(total_dot-S[-1][-1]) if S[-1][-1] != "." else print(-1)

Submission status: Accepted

Solution code:
# ans = 全白マス数 - 最短距離のマス数

H,W=map(int,input().split())
grid=[None]*H
white=0
for i in range(H):
  grid[i]=input()
  white+=grid[i].count(".")
  
from collections import deque
q=deque()
q.append([0,0,0])

seen=[[False for i in range(W)] for j in range(H)]

while q:
  v=q.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  if grid[y][x]=="#" or seen[y][x]:
    continue
  if y==H-1 and x==W-1:
    print(white-(p+1))
    break
  seen[y][x]=True
  if y-1>=0:
    q.append([y-1,x,p+1])
  if y+1<H:
    q.append([y+1,x,p+1])
  if x-1>=0:
    q.append([y,x-1,p+1])
  if x+1<W:
    q.append([y,x+1,p+1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
masu = [0 for h in range(H+2)]
masu[0] = ['#' for _ in range(W+2)]
masu[H+1] = ['#' for _ in range(W+2)]
init = 0
for h in range(1, H + 1):
    w = list(input().strip())
    init += w.count('#')
    masu[h] = ['#'] + w + ['#']

def bfs(Q, c, masu):
    nextq = []
    ans = 10 ** 9 +7
    for q in Q:
        h, w = q
        if w == W and h == H:
            return c
        ans = 10 ** 9 + 7
        for ww, hh in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if masu[h+hh][w+ww] == '#':
                continue
            masu[h+hh][w+ww] = '#'
            nextq.append([h+hh, w+ww])

    if len(nextq):
        ans = min(ans, bfs(nextq, c+1, masu))

    return ans
masu[1][1] = '#'
ans = bfs([(1, 1)], 1, masu)
if ans == 10 ** 9 + 7:
    print(-1)
else:
    print(H*W-ans-init)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
s=[]

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count(".")
    s.append(temp)

d=deque([[0,0]])
c=[[10000]*W for i in range(H)]
step=[[-1,0],[0,-1],[1,0],[0,1]]
c[0][0]=1

while d:
    h0,w0=d.popleft()
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="#" or c[h][w]!=10000:
            continue
        if h==H-1 and w==W-1:
            ans = cnt - c[h0][w0]-1
            print(ans)
            exit()
        c[h][w]=c[h0][w0]+1
        d.append([h,w])
print(-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

# Dijikstra
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)])
    grid = np.pad(grid, 1, 'constant')
    # atcoderではnp.pad() のargにconstant_valuesを指定できない
    q = []
    heappush(q, (0, 1, 1))
    visited = set()
    cost = np.full((H + 1, W + 1), np.inf)
    cost[1][1] = 0
    while q:
        c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        cost[i][j] = c
        if i == H and j == W:
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                heappush(q, (c + 1, y, x))
    

    if cost[H][W] != np.inf:
        ans = int(np.sum(grid == '.') - (cost[H][W] + 1))
    else:
        ans = -1

    print(ans)  

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

# Dijikstra
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)])
    grid = np.pad(grid, 1, 'constant')
    # atcoderではnp.pad() のargにconstant_valuesを指定できない
    q = []
    heappush(q, (0, 1, 1))
    visited = set()
    can_go = False
    while q:
        cost, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if i == H and j == W:
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                heappush(q, (cost + 1, y, x))
    
    if can_go:
        ans = np.sum(grid == '.') - (cost + 1)
    else:
        ans = -1

    print(ans)  
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

# A* algorithm (Dijikstraの応用)
# Dijikstra: actual cost の順
# A*: score( actual_cost + heuristic_cost) の順(scoreが同じ場合はactual_costの順)
# ただしA* algorithm は hueristic_costが計算できるのが前提。また、全頂点への始点からの距離を求めるならDijikstraを使う。今回はstart, endが決まっているのでA*を使った。
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    # atcoderではnp.pad() のargにconstant_valuesを指定できないみたい

    
    i = j = 1             # start
    c = 0                 # actual_cost
    h = (H - 1) + (W - 1) # heuristic_cost 
    s = c + h             # score
    q = []                # status: open
    heappush(q, (s, c, i, j))
    visited = set()       # status: closed
    
    # 今回は最短距離を求めれば良いので必要ないが、最短経路を求める場合にはparent_nodeの記録が必要なので一応parentも記録しておく
    parent = [[None] * (W + 1) for _ in range(H+1)]

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if c == s: # h == 0 ならそこがgoal
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                parent[y][x] = (i, j)
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    # 経路も求める場合はこんな感じ
    # i, j = H, W
    # res = [(H, W)]
    # while parent[i][j]:
    #     i, j = parent[i][j]
    #     res.append((i, j))
    # res = list(reversed(res))
    # print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

# A* algorithm (Dijikstraの応用)
# Dijikstra: actual cost の順
# A*: score( actual_cost + heuristic cost) の順(scoreが同じ場合はactual_costの順)
# ただしA* algorithm は hueristic_costが計算できるのが前提。また、全頂点への始点からの距離を求めるならDijikstraを使う。今回はstart, endが決まっているのでA*を使った。
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    # atcoderではnp.pad() のargにconstant_valuesを指定できないみたい

    
    i = j = 1             # start
    c = 0                 # real cost
    h = (H - 1) + (W - 1) # heuristic cost 
    s = c + h             # score
    q = []                # status: open
    heappush(q, (s, c, i, j))
    visited = set()       # status: closed
    
    # 今回は最短距離を求めれば良いので必要ないが、最短経路を求める場合にはparent_nodeの記録が必要
    parent = [[None] * (W + 1) for _ in range(H+1)]

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if c == s: # h == 0 ならそこがgoal
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                parent[y][x] = (i, j)
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    # 経路も求める場合はこんな感じ
    # i, j = H, W
    # res = [(H, W)]
    # while parent[i][j]:
    #     i, j = parent[i][j]
    #     res.append((i, j))
    # res = list(reversed(res))
    # print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

# A* algorithm (Dijikstraの発展形) を使う
# Dijikstraでは始点からの距離が短い頂点から探索していくが、A*は終点からの距離が近い頂点から順に探索していくので計算量は少なくなる傾向にある。
# ただしA* algorithm では予め終点までの推定距離が分かっている必要がある。
def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    # atcoderではnp.pad() のargにconstant_valuesを指定できないみたい

    
    i = j = 1 # start
    c = 0     # real cost
    h = (H - 1) + (W - 1) # goalまでの推定cost 
    s = c + h # score
    q = [] # open list
    heappush(q, (s, c, i, j))
    visited = set() # closed list
    
    # 今回は最短距離を求めれば良いので必要ないが、最短経路を求める場合には親nodeの記録が必要
    # parent = [[None] * (W + 1) for _ in range(H+1)]

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                visited.add((y, x))
                # parent[y][x] = (i, j)
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    # 経路も求める場合はこんな感じ
    # i, j = H, W
    # res = [(H, W)]
    # while parent[i][j]:
    #     i, j = parent[i][j]
    #     res.append((i, j))
    # res = list(reversed(res))
    # print(res)

if __name__ == "__main__":
    main()