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:
import sys
import numpy as np
from heapq import heappop, heappush


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')

    can_go = False
    i = j = 1 # start
    c = 0     # real cost
    h = max(H - i, W - j) # goalまでの推定cost 
    s = c + h # score
    q = [] # open list
    heappush(q, (s, c, i, j))
    visited = set() # closed list
    # parent = [[None * (W + 1)] for _ in range(H+1)]

    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))
                h = max(H - y, W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = (grid == '.').sum() - (c + 1)
    else:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def bfs(graph: list):
    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    seen = set()
    seen.add((0, 0))
    todo = [(0, 0)]
    cost = {(0, 0): 1}
    while todo:
        x, y = todo.pop(0)
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H) or not (0 <= ny < W):
                continue
            if (nx, ny) in seen:
                continue
            if graph[nx][ny] == ".":
                todo.append((nx, ny))
                seen.add((nx, ny))
                cost[(nx, ny)] = cost[(x, y)] + 1
                if nx == H - 1 and ny == W - 1:
                    return cost[(nx, ny)]
    return -1


white = 0
for line in HW_graph:
    white += line.count(".")

cost = bfs(HW_graph)
if cost == -1:
    print(cost)
else:
    print(white - cost)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
p = [input() for i in range(h)]

# メモ配列
INF = 10**7
memo = [[INF]*w for i in range(h)]

# 白マスをカウント
wcnt = 0
for i in p:
    for j in i:
        if j == '.':
            wcnt+=1

# 幅探索用キュー初期化
q = deque()
q.append((0, 0))
memo[0][0]  = 0

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

ans = -1
for i in range(INF):
    # キューが空なら終了
    if len(q) == 0:
        break
        
    # キューから一つ取り出す
    x, y = map(int, q.pop())
    
    # ゴールなら終了
    if x == w-1 and y == h-1:
        ans = memo[y][x]
        break
        
    # 4方向の距離を確定して、エンキューする
    for j in range(4):
        nx, ny = x+vx[j], y+vy[j]
        
        # エリア外 or 探索済み or 黒色なら探索しない
        if nx < 0 or w <= nx or ny < 0 or h <= ny or memo[ny][nx] != INF or p[ny][nx] == '#':
            continue
            
        memo[ny][nx] = memo[y][x]+1
        q.appendleft((nx, ny))

if ans == -1:
    print(ans)
else:
    print(wcnt-ans-1)

Submission status: Accepted

Solution code:
import queue

def bfs(h, w, maps):
    distance = [[float("inf")] * w for _ in range(h)]
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

    distance[0][0] = 0
    pri_queue = queue.Queue()
    pri_queue.put((0, 0))
    while True:
        if pri_queue.empty():
            break
        p = pri_queue.get()
        if p[0] == h - 1 and p[1] == w - 1:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] != "#" and distance[nx][ny] == float("inf"):
                pri_queue.put((nx, ny))
                distance[nx][ny] = distance[p[0]][p[1]] + 1

    if distance[h - 1][w - 1] != float('inf'):
        return distance[h - 1][w - 1]

    else:
        return -1

h, w = map(int, input().split())
maps = [list(input()) for _ in range(h)]
wall = 0

for i in maps:
    for j in range(w):
        if i[j] == "#":
            wall += 1

min_dis = bfs(h, w, maps)

print(-1 if min_dis == -1 else h * w - (wall + min_dis + 1))

Submission status: Accepted

Solution code:
from collections import deque
def bfs():
    d=[[float("inf")]*w for i in range(h)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=deque([])
    que.append((0,0))
    d[0][0]=0
    cnt=0
    while que:
        p=que.popleft()
        if p[0]==h-1 and p[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 and 0<=ny and ny<w and maze[nx][ny]!="#" and d[nx][ny]==float("inf"):
                que.append((nx,ny))
                d[nx][ny]=d[p[0]][p[1]]+1
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="#":
                cnt+=1
    if d[h-1][w-1]!=float("inf"):
        return h*w-d[h-1][w-1]-1-cnt
    else:
        return -1

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]

print(bfs())

Submission status: Accepted

Solution code:
from collections import deque
import copy

h,w = map(int, input().split())
s = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
black = -(h+w) * 2 - 4
for i in s:
  black += i.count("#")
s[1][1] = 1
q = deque([(1,1)])
white = 1
while True:
  q2 = deque([])
  white += 1
  while len(q):
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = white
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = white
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = white
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = white
      q2.append((a,b+1))   
  if s[h][w] != ".":
    print(h*w - white - black)
    break
  if len(q2):
    q = copy.copy(q2)
  else:
    print(-1)
    break

Submission status: Accepted

Solution code:
H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      m[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)

Submission status: Accepted

Solution code:
#88d 幅優先探索
#https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

from collections import deque

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

all_white = 0

###入力の読み込みと配列の初期化
#最初の行
c_array = [[0 for _ in range(W+1)]]  #入力値。周りには番兵を置いて(1,1)始まりにする。以下も同様。
visited_flag_array = [[1 for _ in range(W+1)]] #訪問済みフラグ 0は未発見、1はキューへ追加or訪問済みor訪問不可
distance_array = [[-1 for _ in range(W+1)]] #開始地点からの距離。∴開始地点は0  訪問不可能地点は-1
#中間行
for i in range(H):
    c = str(input())
    c_list = [0] + [c[i] for i in range(W)] + [0]   
    c_array.append(c_list)
    
    all_white += c_list.count(".")
    
    visited_list = [1] + [0 for _ in range(W)] + [1]
    visited_flag_array.append(visited_list)

    distance_list = [-1] + [-1 for _ in range(W)] + [-1]
    distance_array.append(distance_list)
#最終行
c_array.append([0 for _ in range(W+1)])
visited_flag_array.append([1 for _ in range(W+1)])
distance_array.append([-1 for _ in range(W+1)])

#幅優先探索のロジック
def bfs(start_node_y,start_node_x):
    candidate_deque = deque() #(y座標,x座標,開始時点からの距離) のキュー
    
    #開始地点をキューに追加・処理
    visited_flag_array[start_node_y][start_node_x] = 1     #訪問フラグを立てる
    candidate_deque.append((start_node_y,start_node_x,0))  #キューへの追加
    distance_array[start_node_y][start_node_x] = 0         #距離の記録
    
    for _ in range(1,H*W*4):
        #print("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$")
        if len(candidate_deque) == 0:
            break
        else:
            visiting_node = candidate_deque.popleft()
            vn_y = visiting_node[0]
            vn_x = visiting_node[1]
            vn_d = visiting_node[2]
            
            #nodeの処理
            #print("現在地点(y,x):(",vn_y,",",vn_x,")=",c_array[vn_y][vn_x])
            #print("距離:", distance_array[vn_y][vn_x],"  訪問フラグ:",visited_flag_array[vn_y][vn_x])
            
            #現在のnodeに接しているnodeを列挙
            connecting_node_list = [(vn_y+1,vn_x),(vn_y,vn_x+1),(vn_y-1,vn_x),(vn_y,vn_x-1)]
            #列挙したnodeをすべて処理
            for connecting_node in connecting_node_list:
                cn_y = connecting_node[0]
                cn_x = connecting_node[1]
                
                #print("接続点(y,x)=(",cn_y,",",cn_x,") =",c_array[vn_y][vn_x])
                #print("訪問フラグ:",visited_flag_array[cn_y][cn_x],end="")
                
                if visited_flag_array[cn_y][cn_x] != 1 and c_array[cn_y][cn_x] == ".":
                    #print("…未訪問 ,",end="")
                    
                    visited_flag_array[cn_y][cn_x] = 1
                    candidate_deque.append((cn_y,cn_x,vn_d + 1))
                    distance_array[cn_y][cn_x] = vn_d + 1
                    
                    #print(candidate_deque)
                    
                    #!!!!!!!!!!!!!!!!!!!最短距離を求める場合はここで抜ける!!!!!!!!!!!!!!!!!!!!
                    if cn_y == H and cn_x == W:
                        break
                #else:
                #    if visited_flag_array[cn_y][cn_x] == 1 and c_array[cn_y][cn_x] == ".":
                #        print("…訪問済み")
                #    elif c_array[cn_y][cn_x] == "#":
                #        print("…訪問不可(#)")
                #        if visited_flag_array[cn_y][cn_x] == 0:
                #            visited_flag_array[cn_y][cn_x] = 1
                #    elif c_array[cn_y][cn_x] == 0:
                #        print("…訪問不可(範囲外)")

#main
bfs(1,1)
shortest_distance = distance_array[H][W] + 1 #原点もカウントに追加したいので+1

#問題の回答形式に合わせる
if shortest_distance == 0: #訪問不可能地点は-1で初期化しており、上で+1しているので。
    print(-1)
else:
    print(all_white - shortest_distance) #最短経路以外は全部塗れる

Submission status: Accepted

Solution code:
import heapq
def main():

    H, W = map(int, input().split())
    A = []
    white = 0
    visited = set()
    visited.add((0, 0))
    for i in range(H):
        A.append(input())
        for j in range(W):
            if A[-1][j] == '.': white += 1
            else: visited.add((i, j))

    h = [[1, 0, 0]]
    goal = [H-1, W-1]
    mv = [[1,0],[-1,0],[0,1],[0,-1]]

    while h:
        n, i, j = heapq.heappop(h)
        if [i, j] == goal:
            return white - n
        for di, dj in mv:
            i1, j1 = i+di, j+dj
            if 0<=i1<H and 0<=j1<W and (i1, j1) not in visited:
                heapq.heappush(h, [n+1, i1, j1])
                visited.add((i1, j1))

    return -1

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

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

Y, X = [int(s) for s in input().split()]
sy, sx = [0, 0]
gy, gx = [Y-1, X-1]

M = []

for i in range(Y):
	M.append([s for s in input().rstrip()]) 

dist = [[[-1,-1,-1] for _ in range(X)] for _ in range(Y)]
queue = deque()

dist[sy][sx] = [0,0,0]
queue.append([sy, sx])

while queue:
	y, x = queue.popleft()
	#print(y,x)
	
	for i in range(4):
		ny = y+dy[i]
		nx = x+dx[i]
		
		if ny>=Y or ny<0 or nx>=X or nx<0: continue
		if dist[ny][nx][0] != -1: continue
		
		if M[ny][nx] == '.':
			dist[ny][nx] = [dist[y][x][0]+1,y,x]
			queue.append([ny, nx])

#print(dist[gy][gx][0])

walls = 0
for i in range(Y):
	for j in range(X):
		if M[i][j] == '#': walls += 1

if dist[gy][gx][0] != -1:
	print(Y*X-(dist[gy][gx][0]+1)-walls)
else:
	print(-1)

Submission status: Accepted

Solution code:
h,w = map(int, input().split( ))
s = []

for i in range(h):
    s.append(input())
#幅優先探索
#経路不要
#最短経路長だけ白
from collections import deque

Q = deque()

Q.append((0,0))
N = [(1,0),(-1,0),(0,1),(0,-1)]
D = [[-1]*w for _ in range(h)]
D[0][0]=1
cnt = 0

for u in range(h):
    for v in range(w):
        if s[u][v]=="#":
            cnt +=1

while Q:
    a,b = Q.popleft()
    for i,j in N:
        if 0<=a+i<h and 0<=b+j<w:
            if D[a+i][b+j]<0 and s[a+i][b+j]==".":
                    D[a+i][b+j] = D[a][b]+1
                    Q.append((a+i,b+j))
           

if D[h-1][w-1]>0:
    print(h*w-cnt-D[h-1][w-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
sl = []
for _ in range(h):
    sl.append(list(input()))
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
kuro = 0
for i in range(h):
    for j in range(w):
        if sl[i][j] == "#":
            kuro += 1

from collections import deque
dist = [-1]*w*h
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for i in [v+1, v-1, v+w, v-w]:
        if v % w == 0 and i == v-1:
            continue
        if v % w == w-1 and i == v+1:
            continue
        if 0 <= i <= w * h - 1:
            if sl[i//w][i%w] == ".":
                if dist[i] > -1:
                    continue
                dist[i] = d + 1
                que.append(i)

if dist[-1] == -1:
    print(-1)
else:
    print(w*h - dist[-1] -1 - kuro)

Submission status: Accepted

Solution code:
# ABC088
from collections import deque
import copy
# 入力
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
field_original = copy.deepcopy(field)

# 4方向の移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# BFSのためのデータ構造
dist = [[-1] * W for _ in range(H)]
que_x = deque()
que_y = deque()

# 探索中に各マスはどこからきたのかを表す配列
prev_x = [[-1] * W for _ in range(H)]
prev_y = [[-1] * W for _ in range(H)]

# 初期条件(スタート地点を0にする)
dist[0][0] = 0
que_x.append(0)
que_y.append(0)

# BFS開始
while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
            continue
        if field[nx][ny] == "#":     # 壁はスルー
            continue
        if dist[nx][ny] == -1:          # まだ見ていない時
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1   # 距離の更新
            prev_x[nx][ny] = x      # どの頂点から伝播してきたかを 縦 方向の座標をメモ
            prev_y[nx][ny] = y      # どの頂点から伝播してきたかを 横 方向の座標をメモ

x = H - 1
y = W - 1

if dist[x][y] == -1:        # ゴール出来てない時は -1 で終了
    print(-1)
    exit()
##print(dist[H-1][W-1])
while x != -1 and y != -1:
    field[x][y] = "o"

    # 前の頂点へいく
    px = prev_x[x][y]
    py = prev_y[x][y]
    x, y = px, py
##print(field)
ans = 0
for i in range(H):
    for k in range(W):
        if field[i][k] == field_original[i][k] == ".":
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [0] * H
shortest_path = [[-1] * W for i in range(H)]
sharp_count = 0
for i in range(H):
    S[i] = input()
    sharp_count += S[i].count("#")

que_list = deque()
que_list.append((0, 0))
shortest_path[0][0] = 0
while que_list:
    q = que_list.popleft()
    if H > q[0]-1 >= 0 and W > q[1] >= 0:
        if S[q[0]-1][q[1]] != "#" and shortest_path[q[0]-1][q[1]] == -1:
            que_list.append((q[0]-1,q[1]))
            shortest_path[q[0]-1][q[1]] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]+1 >= 0:
        if S[q[0]][q[1]+1] != "#" and shortest_path[q[0]][q[1]+1] == -1:
            que_list.append((q[0],q[1]+1))
            shortest_path[q[0]][q[1]+1] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]-1 >= 0:
        if S[q[0]][q[1]-1] != "#" and shortest_path[q[0]][q[1]-1] == -1:
            que_list.append((q[0],q[1]-1))
            shortest_path[q[0]][q[1]-1] = shortest_path[q[0]][q[1]]+1
    if H > q[0]+1 >= 0 and W > q[1] >= 0:
        if S[q[0]+1][q[1]] != "#" and shortest_path[q[0]+1][q[1]] == -1:
            que_list.append((q[0]+1,q[1]))
            shortest_path[q[0]+1][q[1]] = shortest_path[q[0]][q[1]]+1

if shortest_path[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W - (shortest_path[H-1][W-1]+1+sharp_count))

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    H,W = map(int,input().split())
    s = [input() for i in range(H)]
    sy,sx = 0,0
    gy,gx = H-1,W-1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                cnt += 1
    inf = float("inf")
    d = [[inf]*W for i in range(H)]
    q = queue.Queue()
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    def bfs():
        for i in range(H):
            for j in range(W):
                d[i][j] = inf
        q.put([sy,sx])
        d[sy][sx]=0
        while not q.empty():
            p = q.get()
            if p[0] == gy and p[1] == gx:
                break
            for k in range(4):
                ny = p[0]+dy[k]
                nx = p[1]+dx[k]
                if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != "#" and d[ny][nx] == inf:
                    q.put([ny,nx])
                    d[ny][nx] = d[p[0]][p[1]]+1
        return d[gy][gx]
    res = bfs()
    print(-1 if res == inf else H*W-cnt-res-1)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    grid=[None]*(h+2)
    grid[0]=['#']*(w+2)
    grid[-1]=['#']*(w+2)
    for i in range(1,h+1):
        grid[i]=list('#'+input()+'#')

    # startは(1,1) goalは(h,w)
    dist=[[INF]*(w+1) for _ in range(h+1)]
    dist[1][1]=1
    from collections import deque
    from itertools import product

    # BFS
    Q=deque([(1,1)])
    while(Q):
        i,j=Q.popleft()
        # 上下左右の4方向をcheck
        for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
            if(grid[i+di][j+dj]=='#'): continue
            if(dist[i+di][j+dj]!=INF): continue
            dist[i+di][j+dj]=dist[i][j]+1
            Q.append((i+di,j+dj))

    if(dist[h][w]==INF):
        print(-1)
        return

    cnt=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            cnt+=grid[i][j]=='.'
    print(cnt-dist[h][w])
resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    sx, sy = 0, 0
    q = deque()
    q.append([sx, sy])
    d[sy][sx] = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy

            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 \
                and s[vy][vx] == "." and d[vy][vx] == -1:
                q.append([vx, vy])
                d[vy][vx] = d[uy][ux] + 1


bfs()
mn = d[h-1][w-1]

if mn == -1:
    ans = -1
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cnt += 1

    ans = cnt - mn - 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
p={}
for i in range(H):    
    for j,c in enumerate(input()):
        p[(i,j)]=c=='.'
d={(i,j):-1 for i in range(H) for j in range(W)}
white=sum(p.values())
q=deque()
s=(0,0)
q.append(s);d[s]=1
while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and p[v] and d[v]==-1:
            d[v]=d[u]+1
            q.append(v)
if d[(H-1,W-1)]==-1:
    ans=-1
else:
    ans=white-d[(H-1,W-1)]
print(ans)

Submission status: Accepted

Solution code:
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
inf = 10 ** 7
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "#":
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = []
    q.append([0,0])
    step = []
    for i in range(h):
        step.append([-1] * w)
    for i in range(h):
        for j in range(w):
            step[i][j] = inf
    step[0][0] = 0
    while not len(q) == 0:
        s = q[0]
        q = q[1:]
        if s[0] == h-1 and s[1] == w-1:
            break
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and mas[nx][ny] != '#' and step[nx][ny] == inf):
                q.append([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1
    
    if(step[h-1][w-1] == inf):
        return -1
    else:
        return step[h-1][w-1]

least = bfs()
if(least == -1):
    print(-1)
else:
    print(h * w - black_num - least - 1)

Submission status: Accepted

Solution code:
from collections import deque
 
R, C = map(int, input().split())
sy, sx = 1, 1
gy, gx = R, C
F = [ input() for _ in range(R) ]
count = 0
for i in F:
  count += i.count(".")
dist = [ [-1]*(C+1) for _ in range(R+1) ]
dist[sy][sx] = 0
q = deque([[sy, sx]])
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
while len(q) != 0:
  h, w = q.popleft()
  for i in range(4):
    nh, nw = h+dy[i], w+dx[i]
    if nh>R or nh<=0 or nw>C or nw<=0:
      continue
    if F[nh-1][nw-1] == "#":
      continue
    if dist[nh][nw] != -1:
      continue
    dist[nh][nw] = dist[h][w] + 1
    if nh==gy and nw==gx:
      print(count - dist[nh][nw] - 1)
      exit()
    q.append([nh, nw])
print(-1)

Submission status: Accepted

Solution code:
import sys

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

# マップを生成する。####で囲う。"."をカウントしておく(white)
m = []
m.append('#'*(w+2))
white = 0
for i in range(h):
  s = input()
  m.append(list('#' + s + '#'))
  white += s.count('.')
m.append('#'*(w+2))

stack = set([(1, 1)])
dist = 0

# stackがある限りループ
while len(stack) > 0:
  
  #ゴールまでの距離をカウントしていく
  dist += 1
  
  # 空のセットを用意
  next_w = set()
  
  for y, x in stack:
    m[y][x] = dist
    
    # ゴールに到着したら
    if (y, x) == (h, w):
      print(white - dist)
      exit()
      
 	# 上下左右に移動。
    for dx,dy in [0,1],[0,-1],[1,0],[-1,0]:
      # "."なら移動可能
      if m[y-dy][x-dx] == '.':
        next_w.add((y-dy,x-dx))
  stack = next_w

print('-1')

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

dd = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def BFS():
    Q = deque([(0, 0)])
    D = [[-1] * W for _ in range(H)]
    D[0][0] = 0
    while Q:
        i, j = Q.popleft()
        for di, dj in dd:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if D[ni][nj] == -1 and A[ni][nj] == 0:
                    D[ni][nj] = D[i][j] + 1
                    Q.append((ni, nj))
    return D

print(H * W - sum([sum(a) for a in A]) - BFS()[-1][-1] - 1 if BFS()[-1][-1] >= 0 else -1)

Submission status: Accepted

Solution code:
# ABC088 D
h, w = map(int, input().split())
maze = []
wall = 0
for _ in range(h):
    row = list(input())
    wall += row.count('#')
    maze.append(row)

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

def bfs():
    from collections import deque
    que = deque([])

    d = [[float("inf")] * w for _ in range(h)]
    que.append((0, 0))
    d[0][0] = 0
    step = 0

    while que:
        step += 1
        p = que.popleft()
        if p == (h - 1, w - 1):
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

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

    return d[h - 1][w - 1]

print(-1 if bfs() == float("inf") else h * w - wall - bfs() - 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import Counter

W = 0
def g_i(i, j):
    return i * W + (j+1) - 1

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    color = [WHITE] * n
    distance = [INF] * n
    parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        # print("u: {}, du: {}".format(u, du))
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                parent[next] = u
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    return (distance, parent)

def main():
    global W
    h, W = map(int, input().strip().split())
    w = W
    s = [[0] * w for _ in range(h)]
    G = [[] for _ in range(h * w)]
    for i in range(h):
        s[i] = list(input().strip())
    sc = 0
    dc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                sc += 1
                continue
            dc += 1
            if i != 0 and s[i-1][j] == '.':
                G[g_i(i, j)].append((g_i(i-1, j), 1))
            if i != h-1 and s[i+1][j] == '.':
                G[g_i(i, j)].append((g_i(i+1, j), 1))
            if j != 0 and s[i][j-1] == '.':
                G[g_i(i, j)].append((g_i(i, j-1), 1))
            if j != w-1 and s[i][j+1] == '.':
                G[g_i(i, j)].append((g_i(i, j+1), 1))
    # print(G)
    d, p = dijkstra(h * w, 0, G)
    # print(d[h*w - 1])
    # for i in range(h):
    #     for j in range(w):
    #         if p[g_i(i, j)] != -1:
    #             print('.', end='')
    #         else:
    #             print('#', end='')
    #     print('\n', end='')
    # print(g_i(h-1, w-2))
    # print(p[g_i(h-1, w-2)])
    # print(p)
    if d[h*w - 1] == INF:
        print(-1)
    else:
        print(dc - d[h*w - 1] - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

qx = deque([])
qy = deque([])

nowx = 0
nowy = 0
tmpx = 0
tmpy = 0

ans = -1
ans2 = 0
cnt = 1
m = []

sx=[0,1,0,-1]
sy=[1,0,-1,0]
H,W = map(int, input().split())
for i in range(H):
    m.append(list(input()))
f = 0
p=[[999 for i in range(W)] for j in range(H)]

qx.append(nowx)
qy.append(nowy)
p[nowx][nowy]=0

while(len(qx) > 0 and f == 0):
    nowx = qx.popleft()
    nowy = qy.popleft()
    for i in range(4):
        tmpx = nowx + sx[i]
        tmpy = nowy + sy[i]
        if (tmpx < 0 or tmpx > W-1 or tmpy < 0 or tmpy > H-1):
            continue
        if (m[tmpy][tmpx] == '#'):
            continue
        if (tmpx == W-1 and tmpy == H-1):
            p[tmpy][tmpx] = p[nowy][nowx]+1
            ans = p[nowy][nowx]+1
            f = 1
            break
        if (p[tmpy][tmpx] > p[nowy][nowx]+1):
            p[tmpy][tmpx] = p[nowy][nowx]+1
            qx.append(tmpx)
            qy.append(tmpy)

if(ans == -1):
    ans2 = -1
else:
    ans2 = sum(x.count('.') for x in m) - ans -1 
print(ans2)