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:
H, W = (int(i) for i in input().split())
S = []
for i in range(H):
	row = input()
	S.append([(0 if row[j]=="." else 1) for j in range(W)])

D = [[10000 for j in range(W)] for i in range(H)]
R = [[False for j in range(W)] for i in range(H)]

N_black = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == 1:
			D[i][j] = -1
			R[i][j] = True
			N_black += 1

def update(i0, j0, i1, j1):
	global D
	center = D[i0][j0]
	adj = D[i1][j1]
	r = R[i1][j1]
	if adj != -1 and r == False and center + 1 < adj:
		D[i1][j1] = center + 1


def check_around(i ,j):
	# UP
	if i != 0:
		update(i, j, i-1, j)
	# LEFT
	if j != 0:
		update(i, j, i, j-1)
	# DOWN
	if i != H-1:
		update(i, j, i+1, j)
	# RIGHT
	if j != W-1:
		update(i, j, i, j+1)

def minimum_point():
	global H, W
	m = 10001
	ni = 0
	nj = 0
	for i in range(H):
		for j in range(W):
			d = D[i][j]
			if d != -1 and R[i][j] == False and d < m:
				m = d
				ni = i
				nj = j
	return (ni, nj)


D[0][0] = 1
R[0][0] = True

pi = 0
pj = 0

for idx in range(W*H):
	check_around(pi, pj)
	pi, pj = minimum_point()
	R[pi][pj] = True

if D[H-1][W-1] == 10000:
	print(-1)
else:
	print(W*H-D[H-1][W-1]-N_black)

Submission status: Accepted

Solution code:
def d_grid_epainting(H, W, S):
    INF = float('inf')
    white = 0  # 全マスのうち白マスの数
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                white += 1

    def bfs():
        # スタート座標は(0,0)とする
        queue = [(0, 0)]
        dist = [[INF for _ in range(W)] for _ in range(H)]  # スタートからの距離
        dist[0][0] = 0  # スタート地点には0歩で到達可能とする
        while len(queue):
            i, j = queue.pop()
            if i == H - 1 and j == W - 1:
                # ゴール座標と一致するなら
                break
            for k in range(4):
                nh, nw = i + [1, 0, -1, 0][k], j + \
                    [0, 1, 0, -1][k]  # (i,j)の右、上、左、下
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#' and dist[nh][nw] == INF:
                    # (nh,nw)が迷路内であり、黒マスでなく、まだ距離が確定していないとき
                    queue.insert(0, (nh, nw))  # 次に探索する座標
                    dist[nh][nw] = dist[i][j] + 1
        return dist[H - 1][W - 1]

    tmp = bfs()
    if tmp == INF:
        ans = -1
    else:
        # tmp+1個の白マス(スタートとゴールを含む)を踏んでゴールに最短でたどり着いた。
        # それらのマスは黒にできないので、すべての白マス数から引く
        ans = white - (tmp + 1)
    return ans

H,W = [int(i) for i in input().split()]
S = [input().strip() for j in range(H)]
print(d_grid_epainting(H, W, S))

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return tuple(map(int, input().split()))

H, W = inpl()

S = [input() for _ in range(H)]
V = [[True if S[h][w]=="." else False for w in range(W)] for h in range(H)]
V[0][0] = True

Q = deque() #step, H, W
Q.append([1, 0, 0])

ok = False
while Q:
    s, h, w = Q.popleft()
    if h == H-1 and w == W-1:
        ok = True
        break
    
    if h > 0:
        if V[h-1][w]:
            V[h-1][w] = False
            Q.append([s+1, h-1, w])
    
    if h < H-1:
        if V[h+1][w]:
            V[h+1][w] = False
            Q.append([s+1, h+1, w])

    if w > 0:
        if V[h][w-1]:
            V[h][w-1] = False
            Q.append([s+1, h, w-1])
    
    if w < W-1:
        if V[h][w+1]:
            V[h][w+1] = False
            Q.append([s+1, h, w+1])

if ok:
    b = sum([s.count("#") for s in S])
    print(H*W - b - s)
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
s.append(list('w' * (w+2)))
d = []
d.append([-1]*(w+2))
sharp = 0
for i in range(h):
    ipt = list('w' + input() + 'w')
    sharp += ipt.count('#')
    s.append(ipt)
    d.append([-1]*(w+2))
s.append(list('w' * (w+2)))
d.append([-1]*(w+2))
queue = [(h, w)]
d[h][w] = 1


while len(queue) > 0 and d[1][1] == -1:
    c = queue.pop(0)
    r = c[0]
    c = c[1]
    dst = d[r][c] + 1
    if s[r-1][c] == '.' and d[r-1][c] == -1:
        queue.append((r-1, c))
        d[r-1][c] = dst

    if s[r+1][c] == '.' and d[r+1][c] == -1:
        queue.append((r+1, c))
        d[r+1][c] = dst

    if s[r][c-1] == '.' and d[r][c-1] == -1:
        queue.append((r, c-1))
        d[r][c-1] = dst

    if s[r][c+1] == '.' and d[r][c+1] == -1:
        queue.append((r, c+1))
        d[r][c+1] = dst

    '''for i in d:
        print(i)
    print(" ")'''
if d[1][1] == -1:
    print(-1)
else:
    print(h * w - sharp - d[1][1])

#print(d[1][1])

Submission status: Accepted

Solution code:
import numpy as np
import scipy as sp
import scipy.sparse.csgraph as sg

H, W = [int(a) for a in input().split()]
ss = []
for _ in range(H):
    ss.append(input())

g = np.zeros((H*W,H*W))

v_edges = [((i,j), (i,j+1)) for i in range(H) for j in range(W-1) if ss[i][j] == "." and ss[i][j+1] == "."]
h_edges = [((i,j), (i+1,j)) for i in range(H-1) for j in range(W) if ss[i][j] == "." and ss[i+1][j] == "."]

for (si,sj), (di,dj) in v_edges + h_edges:
    g[si*W+sj][di*W+dj] = 1
    g[di*W+dj][si*W+sj] = 1

r = sg.dijkstra(g, indices=[0,H*W-1])
score = r[0,H*W-1]

if sp.isinf(score):
    print(-1)
    exit(0)
else:
    #print(r)
    #print(ss) 

    ss_ = "".join(ss)
    num = len([0 for c in ss_ if c == '.'])
    #print(num)
    #print(score)
    print("%d" % (num - (score+1)))

Submission status: Accepted

Solution code:
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
maze=[["" for i in range(W)] for j in range(H)]
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="#"):
            bla+=1
            maze[i][j]="#"
        else:
            whi+=1
            maze[i][j]="."

def clear_maze(sx,sy,gx,gy,maze,W,H):
    INF=100000000
    distance=[[INF for i in range(W)] for j in range(H)]
    
    def bfs():
        testx=[1,0,-1,0]
        testy=[0,1,0,-1]
        queue=[]
        
        queue.insert(0,(sy,sx))
        
        distance[sy][sx]=0
        count=0
        while len(queue):
            if(count>100000000):
                return -1
            count+=1
            x,y=queue.pop()
            
            if(x==gx and y==gy):
                break
            
            for i in range(0,4):
                nx,ny=x+testx[i],y+testy[i]
                
                if(0<=nx and nx<W and 0<=ny and ny<H):
                    if(maze[ny][nx]!="#"):
                        if(distance[ny][nx]==INF):
                            queue.insert(0,(nx,ny))
                            distance[ny][nx]=distance[y][x]+1
        if(distance[gy][gx]==INF):
            return -1
        else:
            return distance[gy][gx]
        
    return bfs()

area=W*H
step=clear_maze(0,0,W-1,H-1,maze,W,H)
if(step==-1):
    print(-1)
elif(maze[0][0]=="#"):
    print(-1)
elif(maze[H-1][W-1]=="#"):
    print(-1)
else:
    score=area-step-1-bla
    print(score)

Submission status: Accepted

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

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

goalFlag=False
while len(que)>0:
    p=que.pop(0)
    if p[0]==gx and p[1]==gy: 
        goalFlag=True
        break
    for (dx,dy) in zip(x,y):
        nextx=p[0]+dx
        nexty=p[1]+dy
        if H>nexty>=0 and W>nextx>=0 and s[nexty][nextx]=='.' and dst[nexty][nextx]==INF:
            que.append([nextx,nexty])
            dst[nexty][nextx]=dst[p[1]][p[0]]+1
if goalFlag:
    count=0 
    for h in range(H):
        for w in range(W):
            if h==w==0 or (h==gy and w==gx):
                continue
            elif s[h][w]=='.':
                count+=1
    print(count-dst[gy][gx]+1)
else: print(-1)

Submission status: Accepted

Solution code:
import sys,collections;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def debug_print(maze):
    for xx in maze:
        for yy in xx:
            print(yy,end="")
        print("\n",end="")

def clear_maze(sx, sy, gx, gy, maze):
#    debug_print(maze)
    INF = 100000000
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sx][sy] = 0
        while len(queue):
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
        if distance[H-1][W-1] == INF:
            print(-1)
            exit()
        return distance[gx][gy] 
    return bfs()

H,W = Is()
maze = []
for _ in range(H):
    maze.append(list(S()))
sx, sy = 0, 0 # スタート地点の座標
gx, gy = H-1, W-1 # ゴール地点の座標
a = clear_maze(sx, sy, gx, gy, maze)
for i in range(H):
    a += maze[i].count("#")
print(H*W-a-1)

Submission status: Accepted

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, h, w, d, q):
    if q.empty(): return d[h - 1][w - 1]
    k, i, j = q.get()
    if i > 0 and m[i - 1][j] == '.' and k + 1 < d[i - 1][j]:
        d[i - 1][j] = k + 1
        q.put((k + 1, i - 1, j))
    if i < h - 1 and m[i + 1][j] == '.' and k + 1 < d[i + 1][j]:
        d[i + 1][j] = k + 1
        q.put((k + 1, i + 1, j))
    if j > 0 and m[i][j - 1] == '.' and k + 1 < d[i][j - 1]:
        d[i][j - 1] = k + 1
        q.put((k + 1, i, j - 1))
    if j < w - 1 and m[i][j + 1] == '.' and k + 1 < d[i][j + 1]:
        d[i][j + 1] = k + 1
        q.put((k + 1, i, j + 1))
    return s(m, h, w, d, q)

h, w = map(int, raw_input().split())
m = [raw_input()[:w] for _ in range(h)]
q = Queue.PriorityQueue()
d = [None] * h
for i in range(h):
    d[i] = [1000000] * w
d[0][0] = 1
for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            q.put((d[i][j], i, j))
c = s(m, h, w, d, q)
if c == 1000000: print -1
else:
    a = 0
    for row in m:
        a += row.count('#')
    print h * w - c - a

Submission status: Accepted

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

    # for i in range(h):
    #     print(maze[i])

    nwall = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                nwall += 1

    q = []
    q.insert(0, (0,0))
    hist = [[0 for i in range(w)] for j in range(h)]
    hist[0][0] = 1


    while(len(q) > 0):
        x, y = q.pop()

        if x == w-1 and y == h-1:
            return h*w - nwall - hist[h-1][w-1]

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

            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if maze[ny][nx] == '#':
                continue
            if hist[ny][nx] >= 1:
                continue
            # print("x,y", x,y)
            # print("nx,ny", nx,ny)

            q.insert(0, (nx,ny))
            hist[ny][nx] = hist[y][x] + 1

    return -1


print(solve())

Submission status: Accepted

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

def isWay(x, y):
    if x >= 0 and x < h and y >= 0 and y < w and arr[x][y] == '.':
        return True
    else:
        return False

numWay = 0
for i in range(h):
    for j in range(w):
        if arr[i][j] == '.':
            numWay += 1

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
if arr[h-1][w-1] == '.':
    print(-1)
else:
    print(numWay - arr[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import Counter

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


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

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

    def bfs():
        queue = []

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

        distance[sx][sy] = 0

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

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

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

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


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

    return bfs()


try:
  q=w * h - clear_maze(0, 0, h, w, maze)-1 - c
  if q<0:
    print('-1')
  else:
    print(w * h - clear_maze(0, 0, h, w, maze)-1 - c)
except:
  print('-1')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = [int(s) for s in input().split(" ")]

maze = [list(input()) for _ in range(H)]

distance = [[float("inf") for i in range(W)] for j in range(H)]

def bfs():
    queue = []
    sx = 0
    sy = 0
    gx = H-1
    gy = W-1

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

    distance[sx][sy] = 0

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

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

        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            
            if (0 <= nx < H and 0 <= ny < W):
                if maze[nx][ny] != '#' and distance[nx][ny] == float("inf"):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

    return distance[gx][gy]

d = bfs()
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            cnt += 1
if  d == float("inf"):
    print(-1)
else:
    print(cnt - d - 1)

Submission status: Accepted

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

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

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

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

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

  if len(q) <= 0:
    break

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

Submission status: Accepted

Solution code:
#幅優先探索
#https://abc007.contest.atcoder.jp/submissions/2107192

R,C = map(int, input().split())
#sy,sx = map(int, input().split())
#gy,gx = map(int, input().split())

count=0

sy,sx = 2,2
gy,gx = R+1, C+1

c_org = [ [ -1 if c_org == "#" else 9999 for c_org in input()] for r in range(R)]

for i in range(R):
    c_org[i].append( -1)
    c_org[i].insert(0,-1)

    count=count+c_org[i].count(9999)

c_plus=[-1 for i in range(C+2)]

c=[]
c.append(c_plus)
for i in range(R):
    c.append(c_org[i])
c.append(c_plus)


#print(c)
 
c[sy - 1][sx - 1] = 0
 
neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]
check_list = [(sy - 1, sx - 1)]
index = 0
 
while index < len(check_list):
    check_rc = check_list[index]
    for neighbor in [ (check_rc[0] + n[0], check_rc[1] + n[1]) for n in neighbors]:
        if c[neighbor[0]][neighbor[1]] >= 0 and  c[neighbor[0]][neighbor[1]] > c[check_rc[0]][check_rc[1]] + 1:
            c[neighbor[0]][neighbor[1]] = c[check_rc[0]][check_rc[1]] + 1
            check_list.append(neighbor)
    index += 1


#---------------------------------------------------
#print(c[gy - 1][gx - 1])
#print(count)
if c[gy - 1][gx - 1]!=9999:
    print(count-c[gy - 1][gx - 1]-1)
else:
    print(-1)

Submission status: Accepted

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

count = 0
for i in s:
  count += i.count('#')

c = 1
queue = []
s[0][0] = c
queue.append((0,0))
while len(queue) != 0:
  v = queue.pop(0)
  c = s[v[0]][v[1]]+1
  if 0 <= v[0]-1:
    if s[v[0]-1][v[1]] == '.':
      s[v[0]-1][v[1]] = c
      queue.append((v[0]-1, v[1]))
  if 0 <= v[1]-1:
    if s[v[0]][v[1]-1] == '.':
      s[v[0]][v[1]-1] = c
      queue.append((v[0], v[1]-1))

  if v[0]+1 < h:
    if s[v[0]+1][v[1]] == '.':
      s[v[0]+1][v[1]] = c
      queue.append((v[0]+1, v[1]))

  if v[1]+1 < w:
    if s[v[0]][v[1]+1] == '.':
      s[v[0]][v[1]+1] = c
      queue.append((v[0], v[1]+1))
if s[h-1][w-1] == '.':
  print(-1)
else:
  print(h*w-count-s[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
ss = ['#' + input() + '#' for i in range(H)]
ss = ['#' * (W + 2)] + ss + ['#' * (W + 2)]

numWhite = sum(map(lambda s: s.count('.'), ss))

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

dist = [[float('inf')] * (W + 2) for i in range(H + 2)]
dist[1][1] = 1

Q = deque()
Q.append((1, 1))
while Q:
    i, j = Q.popleft()

    for di, dj in dij:
        if ss[i + di][j + dj] == '#': continue
        if dist[i + di][j + dj] == float('inf'):
            dist[i + di][j + dj] = dist[i][j] + 1
            Q.append((i + di, j + dj))

if dist[H][W] == float('inf'):
    print(-1)
else:
    print(numWhite - dist[H][W])

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

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

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

Submission status: Accepted

Solution code:
R,C=map(int,input().split())
sx,sy=1,1
gx,gy=R,C
count=0
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
for i in range(R):
	for j in range(C):
		if(mp[i][j]=='#'):
			count+=1
ans=[[3000 for i in range(C)] for j in range(R)]
ans[sx-1][sy-1]=0
start=[sx-1,sy-1]
goal=[gx-1,gy-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]=='.':
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return

while True:
	try:
		print(R*C-bfs(mp,start,goal)-1-count)
		break
	except (RuntimeError,TypeError,NameError):
		print(-1)
		break

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    a = [[c=='#' for c in S()] for _ in range(h)]

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (0,0)
        d[s] = 1
        q = []
        heapq.heappush(q, (1, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for ni,nj in [(0,1),(0,-1),(1,0),(-1,0)]:
                ny = u[0] + ni
                nx = u[1] + nj
                if ny < 0 or ny >= h or nx < 0 or nx >= w:
                    continue
                if v[(ny,nx)] or a[ny][nx]:
                    continue
                uv = (ny,nx)
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search()
    r = d[(h-1,w-1)]
    if r == inf:
        return -1
    for ai in a:
        for aj in ai:
            if not aj:
                r -= 1

    return -r


print(main())

Submission status: Accepted

Solution code:
R,C=map(int,input().split())
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
ans=[[3000 for i in range(C)] for j in range(R)]
ans[0][0]=0
start=[0,0]
goal=[R-1,C-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]==".":
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return 

bfs(mp,start,goal)
if ans[R-1][C-1]==3000:
  print("-1")
else:
  max_ans=R*C-ans[R-1][C-1]-1
  for i in range(R):
    for j in range(C):
      if mp[i][j]=='#':
        max_ans-=1
  print(max_ans)

Submission status: Accepted

Solution code:
from collections import deque

WHITE = -1
BLACK = -2
GOAL = -3
field_mapping = {
    '.': WHITE,
    '#': BLACK
}


def neighbors(y, x):
    points = []
    if y-1 >= 0:
        points.append([y-1, x])
    if y+1 < H:
        points.append([y+1, x])
    if x-1 >= 0:
        points.append([y, x-1])
    if x+1 < W:
        points.append([y, x+1])
    return points


def searching():
    field[0][0] = 1
    queue = deque([[0, 0]])
    while len(queue) > 0:
        [y, x] = queue.popleft()
        current_distance = field[y][x]
        for [n_y, n_x] in neighbors(y, x):
            point_status = field[n_y][n_x]
            if point_status == WHITE:
                field[n_y][n_x] = current_distance + 1
                queue.append([n_y, n_x])
            elif point_status == GOAL:
                return current_distance + 1
    return -1


def main():
    global H, W, field
    [H, W] = [int(i) for i in input().split()]
    field = []
    white_num = 0
    for i in range(H):
        line = []
        for color in [field_mapping[s] for s in input()]:
            line.append(color)
            if color == WHITE:
                white_num += 1
        field.append(line)
    field[H-1][W-1] = GOAL
    walked_points = searching()
    if walked_points < 0:
        print(-1)
    else:
        print(white_num - walked_points)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import exit

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

P = set()
Q = {(0, 0)}
QQ = set()

def add(x, y):
    if s[x][y] == '.' and (x, y) not in P:
        QQ.add((x, y))

def search_next(x, y):
    if x > 0:
        add(x-1, y)
    if x < H-1:
        add(x+1, y)
    if y > 0:
        add(x, y-1)
    if y < W-1:
        add(x, y+1)

count = 0

while True:
    count += 1
    for q in Q:
        search_next(*q)
    P = P.union(Q)
    Q = QQ
    QQ = set()
    if (H-1, W-1) in Q:
        break
    elif len(Q) == 0:
        print(-1)
        exit(0)

white = 0
for line in s:
    white += line.count('.')

print(white - count - 1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list('#' * (w + 2))]
queue = [[1, 1, 1]]
dot = 0
for i in range(h):
    s.append(['#'] + list(input()) + ['#'])
    dot += s[-1].count('.')
s.append(list('#' * (w + 2)))

def move(yxc):
    y, x, cost = yxc[0], yxc[1], yxc[2]
    global queue
    for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        ny, nx = y + dy, x + dx
        if s[ny][nx] == '.':
            s[ny][nx] = cost + 1
            queue.append([ny, nx, cost + 1])

while len(queue) > 0:
    move(queue.pop(0))

s[1][1] = 1
move([1, 1, 1])
if s[h][w] == '.':
    print(-1)
else:
    print(dot - s[h][w])

Submission status: Accepted

Solution code:
# coding=utf-8

line = input().split(" ")
H = int(line[0])
W = int(line[1])

s = []
cnt_w = 0
for _ in range(H):
    line = list(input())
    for x in line:
        if x==".":
            cnt_w += 1
    s.append(line)

INF = 100000

diff = [
    [0,1]
    ,[0,-1]
    ,[1,0]
    ,[-1,0]
]

def dfs():
    q = []
    m = []
    for i in range(H):
        m.append([INF for _ in range(W)])
    q.append((0,0))
    m[0][0] = 1

    while len(q)>0:
        p = q.pop(0)
        if H-1==p[0] and W-1==p[1]:
            break

        for d in diff:
            ni = p[0]+d[0]
            nj = p[1]+d[1]
            if 0<=ni<H and 0<=nj<W:
                if s[ni][nj]=="." and m[ni][nj]==INF:
                    q.append((ni,nj))
                    m[ni][nj] = m[p[0]][p[1]]+1

    return m[H-1][W-1]

r = dfs()

if r == INF:
    print("-1")
else:
    print(cnt_w - r)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
Field = [list(input()) for i in range(H)]

que = deque()
que.append([0, 0])
Field[0][0] = 0

while que:
    now = que.popleft()
    if now == [H-1, W-1]:
        break

    if now[0]+1 <= H -1:
        if Field[now[0]+1][now[1]] == ".":
            Field[now[0]+1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]+1, now[1]])

    if now[0]-1 >= 0:
        if Field[now[0]-1][now[1]] == ".":
            Field[now[0]-1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]-1, now[1]])

    if now[1] + 1 <= W -1:
        if Field[now[0]][now[1]+1] == ".":
            Field[now[0]][now[1]+1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]+1])

    if now[1] -1 >= 0:
        if Field[now[0]][now[1]-1] == ".":
            Field[now[0]][now[1]-1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]-1])
else:
    print(-1)
    exit()
Z = int(Field[H-1][W-1])

sharp_cnt = 0
for f in Field:
    sharp_cnt += f.count("#")

print(H*W - sharp_cnt - Z - 1)