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:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

graph = [[-1 for _ in range(W)] for _ in range(H)]

que = deque()
x,y = 0,0 #初期値
que.append((x,y))
graph[x][y] = 0
while len(que) > 0:
    # x,y = que.pop()  # 深さ優先探索
    x,y = que.popleft() #幅優先探索
    step = graph[x][y]
    #左
    if y-1 >= 0 and s[x][y-1] == "." and graph[x][y-1] == -1:
        que.append((x,y-1))
        graph[x][y-1] = step + 1
    #右
    if y+1 < W and s[x][y+1] == "." and graph[x][y+1] == -1:
        que.append((x, y+1))
        graph[x][y+1] = step + 1
    #上
    if x-1 >= 0 and s[x-1][y] == "." and graph[x-1][y] == -1:
        que.append((x-1, y))
        graph[x-1][y] = step + 1
    #下
    if x+1 < H and s[x+1][y] == "." and graph[x+1][y] == -1:
        que.append((x+1, y))
        graph[x+1][y] = step + 1

#ゴールから戻って最短ルートにマークする（複数ある場合は一方だけマーク）
que = deque()
x, y = H-1, W-1     #初期値（ゴール）
que.append((x,y))
step = graph[x][y]
graph[x][y] = -2  # 最短ルートにマーク

if step == -1:
    print(-1)
    exit()

while len(que) > 0:
    x, y = que.popleft()  # 幅優先探索
    if x == y == 0:
        break
    #左
    if y-1 >= 0 and graph[x][y-1] == step - 1:
        que.append((x, y-1))
        graph[x][y-1] = -2
        step -= 1
        continue
    #右
    if y+1 < W and graph[x][y+1] == step - 1:
        que.append((x, y+1))
        graph[x][y+1] = -2
        step -= 1
        continue
    #上
    if x-1 >= 0 and graph[x-1][y] == step - 1:
        que.append((x-1, y))
        graph[x-1][y] = -2
        step -= 1
        continue
    #下
    if x+1 < H and graph[x+1][y] == step - 1:
        que.append((x+1, y))
        graph[x+1][y] = -2
        step -= 1
        continue

ans = 0
for h in range(H):
    for w in range(W):
        if s[h][w] == "." and graph[h][w] != -2:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(-(v[h-1][w-1]<0)or h*w-c-v[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(-1*(v[h-1][w-1]<0)or h*w-c-v[h-1][w-1]-1)

Submission status: Accepted

Solution code:
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("#", "")) for row in s])
    scan = [(0, 0, 1)]  # i, j, cost
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    if path[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(white - path[H-1][W-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
Map=[list(input()) for i in range(H)]
for h in range(H):
  Map[h].insert(0,"#")
  Map[h].append("#")
Map.insert(0,["#"]*(W+2))
Map.append(["#"]*(W+2))
white=sum(Map[i].count(".") for i in range(H+2))

Que=deque([(1,1,1)])
visited=[[10**10]*(W+2) for i in range(H+2)]
while Que:
  x,y,stage=Que.popleft()
  if x==W and y==H:
    print(white-stage)
    exit()
  stage+=1
  for i,j in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
    if Map[j][i]=="." and stage<visited[j][i]:
      visited[j][i]=stage
      Que.append((i,j,stage))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain

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

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

l = [[None for _ in range(w)] for _ in range(h)]
l[0][0] = 0

q = deque([(0, 0)])
while q:
	this_x, this_y = q.popleft()
	this_num = l[this_y][this_x]
	if (this_x, this_y) == (w-1, h-1):
		# [print(" ".join(str(l_j).rjust(2) if l_j != None else "  " for l_j in l_i)) for l_i in l]
		print(sum(s_i.count(".") for s_i in s) - l[h-1][w-1] - 1)
		exit()

	for ad_x, ad_y in ADS:
		x, y = this_x+ad_x, this_y+ad_y
		if not (0 <= x < w and 0 <= y < h):
			continue
		
		square = s[y][x]
		if square == "#":
			continue

		num = l[y][x]
		if num != None:
			continue
		l[y][x] = this_num + 1

		q.append((x, y))

print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
Inf = 1000
Dist, Fin = [[Inf for i in range(W)] for j in range(H)], [[False for i in range(W)] for j in range(H)]
Dist[0][0], Fin[0][0] = 0, True
Q, Search = [(0, 0)], [(-1, 0), (0, -1), (1, 0), (0, 1)]

while Q:
    next = Q.pop(0)
    for s in Search:
        if 0 <= next[0] + s[0] <= H-1 and 0 <= next[1] + s[1] <= W-1:
            if Fin[next[0] + s[0]][next[1]+s[1]] == False:
                Fin[next[0]+s[0]][next[1]+s[1]] = True
                if S[next[0]+s[0]][next[1]+s[1]] == ".":
                    Dist[next[0]+s[0]][next[1]+s[1]] = Dist[next[0]][next[1]] + 1
                    Q.append((next[0]+s[0], next[1]+s[1]))

if Dist[H-1][W-1] == Inf:
    print(-1)
else:
    now, dist = (H-1, W-1), Dist[H-1][W-1]
    S[H-1][W-1] = "#"
    while dist > 0:
        for s in Search:
            if 0 <= now[0] + s[0] <= H-1 and 0 <= now[1] + s[1] <= W-1:
                if Dist[now[0]+s[0]][now[1]+s[1]] == dist-1:
                    now, dist = (now[0]+s[0], now[1]+s[1]), dist-1
                    S[now[0]][now[1]] = "#"
                    break

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

Submission status: Accepted

Solution code:
from collections import deque


H, W = map(int, input().split())
S = [list(map(str, input())) for i in range(H)]
numWhite = -2  # [1,1], [H,W]を除く
for h in range(H):
    numWhite += S[h].count(".")


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


def bfs():
    que = deque([])
    que.append([0, 0])
    D = []
    for h in range(H):
        D.append([float('inf') for _ in range(W)])
    D[0][0] = 0
    while len(que) > 0:
        p = que.popleft()
        if p == [H-1, W-1]:
            break
        else:
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny] == float('inf'):
                    que.append([nx, ny])
                    D[nx][ny] = D[p[0]][p[1]] + 1
    return D[H-1][W-1]


ans = numWhite - bfs() + 1
if isinstance(ans, int):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = []
count_dot = 0
for _ in range(H):
    s = input()
    count_dot += s.count('.')
    S += [list(s)]
S[0][0] = '#'
coord = [[0, 0]]
count = 1
flag = True
while flag:
    count += 1
    coord_new = []
    for i, j in coord:
        for x, y in [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]:
            if (x, y) == (H - 1, W - 1):
                print(count_dot - count)
                exit()
            elif 0 <= x and x < H and 0 <= y and y < W and S[x][y] == '.':
                S[x][y] = '#'
                coord_new += [[x, y]]
    coord = coord_new
    flag = len(coord)
print(-1)

Submission status: Accepted

Solution code:
inf = 2**31 - 1


def bfs(sx, sy, gx, gy):
    que = []
    d = {h: {w: inf for w in range(W)} for h in range(H)}

    que.append((sx, sy))
    d[sy][sx] = 0

    while len(que):
        p = que.pop(0)

        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]

            if (0 <= nx < W) and (0 <= ny < H) and (maze[ny][nx] != '#') and (d[ny][nx] == inf):
                que.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1

    return d[gy][gx]


def wall_count(l):
    temp = []
    for s in l:
        temp.extend(s)
    return temp.count('#')


if __name__ == '__main__':
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)

    H, W = list(map(int, input().split(" ")))

    maze = [list(input()) for h in range(H)]
    walls = wall_count(maze)

    goal = bfs(0, 0, W-1, H-1)

    if goal == inf:
        print(-1)
    else:
        print(H*W - walls - goal - 1)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain
ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]

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

def find_shortest(m):
	q = deque([(0, 0)])
	i = 0
	while q:
		for j in range(len(q)):
			this_x, this_y = q.popleft()
			# this_square = m[this_y][this_x]
			if (this_x, this_y) == (w-1, h-1):
				return i
			m[this_y][this_x] = i

			for ad_x, ad_y in ads:
				x, y = this_x+ad_x, this_y+ad_y
				if not (0 <= x < w and 0 <= y < h):
					continue
				
				square = m[y][x]
				if square == "#" or type(square) == int:
					continue
					
				q.append((x, y))
				m[y][x] = "#"
		i += 1
	return None


white_num = "".join(chain(*s)).count(".")
shortest_lenght = find_shortest(s)
if shortest_lenght:
	print(white_num - 1 - shortest_lenght)
else:
	print(-1)
# しろます - 1 - 最短ルートの長さ

Submission status: Accepted

Solution code:
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))







H,W=map(int,input().split())
black=0
field=[["#"]*(W+2)]
for i in range(H):
    field.append(["#"] + list(input()) + ["#"])

field.append(["#"]*(W+2))

adj=[[float("inf")]*W*H for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if(field[i+1][j+1]=="#"):
            black+=1
            continue
        if(field[i+1][j+2]=="."):
            adj[W*i+j][W*i+j+1]=1
            adj[W*i+j+1][W*i+j]=1
        if(field[i+1][j]=="."):
            adj[W*i+j][W*i+j-1]=1
            adj[W*i+j-1][W*i+j]=1
        if(field[i][j+1]=="."):
            adj[W*i+j][W*(i-1)+j]=1
            adj[W*(i-1)+j][W*i+j]=1
        if(field[i+2][j+1]=="."):
            adj[W*i+j][W*(i+1)+j]=1
            adj[W*(i+1)+j][W*i+j]=1

d=Dijkstra()
kyori=d.dijkstra(adj,0)[-1]
if(kyori==float("inf")):
    print(-1)
else:
    print(H*W-black-kyori-1)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import deque
H,W = inpl()
S =  []
for i in range(H):
    S.append(input())
    
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
Q = deque()
Q.append((0,0))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while Q:
    nw, nh = Q.pop() 
    for dw, dh in d:
        if not 0 <= nh + dh <= H-1:
            continue
        if not 0 <= nw + dw <= W-1:
            continue
        if S[nh+dh][nw+dw] == '#':
            continue
        if dist[nh+dh][nw+dw] != -1:
            continue
        dist[nh+dh][nw+dw] =dist[nh][nw] +1
        Q.appendleft((nw+dw,nh+dh))
if dist[H-1][W-1] == -1:
    print(-1)
else:
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    ans -= dist[H-1][W-1]
    print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [['#' for _ in range(w + 2)]]
s = s + [['#'] + list(input()) + ['#'] for _ in range(h)]
s = s + [['#' for _ in range(w + 2)]]
n_white = 0
for i in range(1, h + 1):
    n_white += s[i].count('.')
q = [[1, 1]]
a = []
d = 1
while(True):
    qq = []
    for i in range(len(q)):
        if q[i] in a:
            continue
        x = q[i][0]
        y = q[i][1]
        if s[x][y - 1] == '.' and [x, y - 1] not in qq:
            qq.append([x, y - 1])
        if s[x - 1][y] == '.' and [x - 1, y] not in qq:
            qq.append([x - 1, y])
        if s[x + 1][y] == '.' and [x + 1, y] not in qq:
            qq.append([x + 1, y])
        if s[x][y + 1] == '.' and [x, y + 1] not in qq:
            qq.append([x, y + 1])
    d += 1
    if [h, w] in qq:
        break
    elif qq == []:
        print(-1)
        exit()
    a = a + q
    q = qq
print(n_white - d)

Submission status: Accepted

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

# 元々の黒マスの数を数える
black = 0
for g in G:
    black += g.count("#")

# コスト管理
C = [[-1] * W for i in range(H)]
C[0][0] = 0

# queue準備
que = deque()
que.append((0, 0))

# BFS
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        # 例外条件
        if not 0 <= nh + dh < H:
            continue
        if not 0 <= nw + dw < W:
            continue
        if G[nh + dh][nw + dw] == "#":
            continue
        if C[nh + dh][nw + dw] > 0:
            continue

        C[nh + dh][nw + dw] = C[nh][nw] + 1
        que.appendleft((nh + dh, nw + dw))

print(H * W - C[H - 1][W - 1] - black - 1 if C[H - 1][W - 1] > 0 else -1)

Submission status: Accepted

Solution code:
from collections import deque

H,W=list(map(int,input().split()))
ans=-1

s=['#'*(W+2)]
s+=['#'+input()+'#' for _ in range(H)]
s+=['#'*(W+2)]

deq=deque([(1,1,0)])
move=[(1,0),(0,1),(-1,0),(0,-1)]
dist=[[-1 for _ in range(W+2)] for _ in range(H+2) ]
while len(deq) !=0:
    x=deq.pop()
    if x[:-1]==(H,W):
        ans=x[-1]
        break
    for m in move:
        i=x[0]+m[0]
        j=x[1]+m[1]
        d=x[2]
        if s[i][j]=='.' and dist[i][j]==-1:
            deq.appendleft((i,j,d+1))
            dist[i][j]=d+1

if ans==-1:
    print(-1)
else:
    sum_=0
    for t in s:
        sum_+=t.count('#')
    b=sum_-(W+2)*2-H*2
    ans=H*W-b-ans-1
    print(ans)

Submission status: Accepted

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

black = 0
for h in range(H):
    for w in range(W):
        black += (G[h][w] == "#")

que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

visited = set([(0, 0)])
while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == "." and (nh + dh, nw + dw) not in visited:
                que.appendleft((nh + dh, nw + dw, cost + 1))
                visited.add((nh + dh, nw + dw))
else:
    print(-1)

Submission status: Accepted

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

INF = float('inf')
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
white = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1

def bfs(si, sj):
    dist = [[INF for i in range(w)] for j in range(h)]
    q = deque([((si, sj), 1)])
    dist[si][sj] = 1

    while q:
        (ni, nj), d = q.popleft()
        for x, y in dir:
            xi = ni + x
            yj = nj + y
            di = d + 1
            if xi < 0 or yj < 0 or xi > h-1 or yj > w-1:
                continue
            if dist[xi][yj] > di and s[xi][yj] == ".":
                dist[xi][yj] = di
                q.append(((xi, yj), di))
    if dist[h-1][w-1] == INF:
        return -1
    else:
        return white - dist[h-1][w-1]

print(bfs(0, 0))

Submission status: Accepted

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


ANS=0
for i in range(H):
    ANS+=MAP[i].count(".")

from collections import deque

QUE = deque()
QUE.append((0,0))
MAP[0][0]=0

while QUE:
    (x,y)=QUE.pop()

    for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if i<0 or j<0 or i>=H or j>=W:
            continue
        if MAP[i][j]==".":
            MAP[i][j]=MAP[x][y]+1
            QUE.appendleft((i,j))
            
        
if MAP[H-1][W-1]==".":
    print(-1)
else:
    print(ANS-MAP[H-1][W-1]-1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(grid: list):
    h = len(grid)
    w = len(grid[0])
    
    dhs = [0, 1, 0, -1]
    dws = [1, 0, -1, 0]
    
    que = deque([(1,(0,0))])
    grid[0][0] = "1"
    
    while que:
        cost, (hcur, wcur) = que.popleft()
    
        for dh, dw in zip(dhs, dws):
            if 0 <= hcur+dh < h and 0 <= wcur+dw < w and grid[hcur+dh][wcur+dw] == ".":
                nex_cost = cost + 1
                grid[hcur+dh][wcur+dw] = str(nex_cost)
                que.append((nex_cost, (hcur+dh, wcur+dw)))
    

h,w = li()

grid = []
for _ in range(h):
    grid.append(lc())

whites = 0
for row in grid:
    whites += row.count(".")

bfs(grid)

if grid[-1][-1] == "#" or grid[-1][-1] == ".":
    print(-1)

else:
    print(whites - int(grid[-1][-1]))

Submission status: Accepted

Solution code:
from collections import deque

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

dxy = [(1,0),(0,1),(-1,0),(0,-1)]
dists = [[-1]*W for i in range(H)]
dists[0][0] = 0
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if dists[ny][nx] >= 0: continue
        if src[ny][nx] == '#': continue
        q.append((nx,ny))
        dists[ny][nx] = dists[y][x] + 1
d = dists[-1][-1]
if d == -1:
    print(d)
else:
    white = 0
    for row in src:
        for c in row:
            if c == '.':
                white += 1
    print(white - d - 1)

Submission status: Accepted

Solution code:
def ABC088D():
    
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    visited = [[False for i in range(W)] for i in range(H)]
    black_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                visited[i][j] = True
                black_cnt += 1
    will_visit = [[0, 0, 0]]
    def sarch(i, j, dist):
        visited[i][j] = True
        if 0 <= i - 1:
            if not visited[i - 1][j]:
                will_visit.append([i - 1, j, dist + 1])
        if 0 <= j - 1:
            if not visited[i][j - 1]:
                will_visit.append([i, j - 1, dist + 1])
        if j + 1 < W:
            if not visited[i][j + 1]:
                will_visit.append([i, j + 1, dist + 1])
        if i + 1 < H:
            if not visited[i + 1][j]:
                will_visit.append([i + 1, j, dist + 1])

    key = 0
    next = 0
    while len(will_visit) > next:
        #print(will_visit)
        next_i = will_visit[next][0]
        next_j = will_visit[next][1]
        next_dist = will_visit[next][2]
        if not visited[next_i][next_j]:
            if next_i == H - 1 and next_j == W - 1:
                key = next_dist
                break
            sarch(next_i, next_j, next_dist)
        if key != 0:
            break
        next += 1
    if key == 0:
        print(-1)
    else:
        key += 1
        print(H * W - key - black_cnt)
        
ABC088D()

Submission status: Accepted

Solution code:
import queue
H,W = map(int,input().split())
maze = [0]*H
for i in range(H):
    maze[i] = input()
inf = float('inf')
d = [[inf for i in range(W)] for i in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]


def bfs():
    que = queue.Queue()
    que.put((0,0))
    d[0][0] = 0
    while que.qsize():
        p = que.get()
        if p == (H-1,W-1):
            break
        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0 <= nx and nx <= H-1 and 0 <= ny and ny <= W-1 \
            and maze[nx][ny] != '#' and d[nx][ny] == inf:
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.put((nx,ny))

bfs()

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

ans = -1
if d[H-1][W-1] != inf:
    ans = H*W-count-1-d[H-1][W-1]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]
black = sum(x == '#' for row in s for x in row)
INF = 10 ** 9
sp = [[INF] * W for _ in range(H)]
sp[0][0] = 0
q = [(0, 0, 0)]
while q:
    dist, prev_x, prev_y = heappop(q)
    for dx, dy in zip([1, 0, -1, 0], [0, -1, 0, 1]):
        x = prev_x + dx
        y = prev_y + dy
        if (0 <= x < W and 0 <= y < H
                and s[y][x] == '.' and dist + 1 < sp[y][x]):
            sp[y][x] = dist + 1
            heappush(q, (dist + 1, x, y))

if sp[H - 1][W - 1] == INF:
    print(-1)
else:
    print(H * W - black - sp[H - 1][W - 1] - 1)

Submission status: Accepted

Solution code:
def AppendQue(now, depth, que, past_visit, maze):
    Next = ((now[0] - 1, now[1]), (now[0], now[1] - 1),
            (now[0] + 1, now[1]), (now[0], now[1] + 1))
    for h, w in Next:
        if h < 0 or w < 0 or h >= H or w >= W:
            continue
        elif (h, w) in past_visit:
            continue
        elif maze[h][w] == "#":
            continue
        elif (h, w) in que:
            continue

        que.append((h, w))
        depth[(h, w)] = depth[now] + 1


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

maze = []
black = 0
for i in range(H):
    maze.append(input())
    black += maze[i].count("#")

if maze[0][0] == "#" or maze[H - 1][W - 1] == "#":
    print(-1)
    exit()

que = []
now = (0, 0)
depth = {}
depth[now] = 1
que.append(now)
past_visit = set()
while True:
    if len(que) == 0:
        print(-1)
        exit()
    now, que = que[0], que[1:]
    if now == (H - 1, W - 1):
        break
    past_visit.add(now)
    AppendQue(now, depth, que, past_visit, maze)

print(H * W - black - depth[(H - 1, W - 1)])

Submission status: Accepted

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

table = [["#"] + list(input()) + ["#"] for _ in range(H)]
table = [["#" for _ in range(W+2)]] + table + [["#" for _ in range(W+2)]]

cnt = 0
for r in table:
    for s in r:
        if s == ".":
            cnt += 1

# BFS
connect = [[0 for _ in range(W+1)] for _ in range(H+1)]
used = [[1000 for _ in range(W+1)] for _ in range(H+1)]

# make dictionary
for r in range(1, H + 1):
    for c in range(W + 1):
        if table[r][c] == ".":
            connect_list = []
            if table[r+1][c] == ".":
                connect_list.append([r+1, c])

            if table[r-1][c] == ".":
                connect_list.append([r-1, c])

            if table[r][c+1] == ".":
                connect_list.append([r, c+1])

            if table[r][c-1] == ".":
                connect_list.append([r, c-1])

            connect[r][c] = connect_list


# search
queue = [[1, 1, 0]]


def bfs(x, y, num):
    while len(queue) > 0:
        r, c, num = queue.pop(0)
        if used[r][c] == 1000:
            used[r][c] = num
            for t in connect[r][c]:
                queue.append([t[0], t[1], num + 1])


bfs(1, 1, 0)

if used[H][W] == 1000:
    print(-1)

else:
    print(cnt - used[H][W] - 1)

Submission status: Accepted

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

dxs = [1, 0, -1, 0]
dys = [0, 1, 0, -1]

dists = [[3000]*w for _ in range(h)]
dists[0][0] = 1
que = deque([(0, 0, 1)])
while len(que) > 0:
    i, j, score = que.popleft()
    
    for dy, dx in zip(dys, dxs):
        i_next, j_next = i+dy, j+dx
        if i_next < 0 or i_next >= h or j_next < 0 or j_next >= w:
            continue
        if s[i_next][j_next] == '#':
            continue
        if dists[i_next][j_next] <= score+1:
            continue
        dists[i_next][j_next] = score+1
        que.append((i_next, j_next, score+1))
# for d in dists: print(d)

if dists[h-1][w-1] == 3000:
    print(-1)
    exit()
d_min = dists[h-1][w-1]
n_black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            n_black += 1
print(h*w - n_black - d_min)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
black = 0
ma = []
maa = []
go = [[0, 0]]
for i in range(h):
    ma.append(list(input()))
    black += ma[i].count("#")
    maa.append([0] * w)
maa[0][0] = 1
while go != []:
    k = go.pop(0)
    if k[0] == h - 1 and k[1] == w - 1:
        print(h * w - black - maa[h - 1][w - 1])
        break
    if k[0] != 0:  # up
        if ma[k[0] - 1][k[1]] == "." and maa[k[0] - 1][k[1]] == 0:
            maa[k[0] - 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] - 1, k[1]])
    if k[0] != h-1:  # down
        if ma[k[0] + 1][k[1]] == "." and maa[k[0] + 1][k[1]] == 0:
            maa[k[0] + 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] + 1, k[1]])
    if k[1] != 0:  # left
        if ma[k[0]][k[1]-1] == "." and maa[k[0]][k[1]-1] == 0:
            maa[k[0]][k[1]-1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1]-1])
    if k[1] != w-1:  # right
        if ma[k[0]][k[1]+1] == "." and maa[k[0]][k[1]+1] == 0:
            maa[k[0]][k[1]+1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1] + 1])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

s = []
white = 0
for y in range(h):
    s.append(input())
    white += s[y].count('.')

def gets(y, x):
    if 1 <= y <= h and 1 <= x <= w:
        return s[y - 1][x - 1] == '.'
    else:
        return False

v = set()
q = deque([(1, 1, 0)])
costMin = -1
while len(q) > 0:
    y, x, cost = q.popleft()
    if (y, x) == (h, w):
        costMin = cost
        break

    if (y, x) not in v:
        v.add((y, x))
        if gets(y - 1, x): q.append((y - 1, x, cost + 1))
        if gets(y + 1, x): q.append((y + 1, x, cost + 1))
        if gets(y, x - 1): q.append((y, x - 1, cost + 1))
        if gets(y, x + 1): q.append((y, x + 1, cost + 1))

if costMin < 0:
    print(-1)
else:
    print(white - costMin - 1)