Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
m = [['#']*(w+2)] + [['#']+list(input())+['#'] for _ in range(h)] + [['#']*(w+2)]

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque([(1, 1, 1)])
m[1][1] = '@'
ans = -1
while q:
    x, y, c = q.popleft()
    if x == h and y == w:
        ans = c
        break
    for dx, dy in d:
        nx, ny = x+dx, y+dy
        if m[nx][ny] == '.':
            q.append((nx, ny, c+1))
            m[nx][ny] = '@'

if ans != -1:
    for i in range(1, h+1):
        for j in range(1, w+1):
            if m[i][j] == '#':
                ans += 1
    ans = h*w - ans

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def search_maze(maze, start, goal, size):
    TO_NEXT_CELL = [(1,0), (0,1), (-1,0), (0,-1)]
    h = size[0]
    w = size[1]
    distance = [[float("inf") for _ in range(w)] for _ in range(h)]
    min_step = -1
    queue = deque([start])
    distance[start[0]][start[1]] = 1
    while len(queue) != 0:
        i, j = queue.popleft()
        d = distance[i][j]
        if i == goal[0] and j == goal[1]:
            min_step = d
            break
        for next_cell in TO_NEXT_CELL:
            next = (i + next_cell[0], j + next_cell[1])
            if (0 <= next[0] and next[0] < h and 0 <= next[1] and next[1] < w and distance[next[0]][next[1]] == float('inf')):
                if maze[next[0]][next[1]] == '.':
                    queue.append(next)
                    distance[next[0]][next[1]] = d + 1
    return min_step

if __name__ == '__main__':
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input().strip()))
    white_count = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                white_count += 1
    min_step = search_maze(maze, (0,0), (h-1,w-1), (h,w))
    if min_step == -1:
        print ('-1')
    else:
        ans = white_count - min_step
        print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

check = [[False] * w for i in range(h)]

ans = 0
q = deque()
q.append((0, 0, 0))
while len(q) > 0:
    x, y, step = q.popleft()
    if x == w-1 and y == h-1:
        ans = step
        break
    for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
        if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
            if board[n_y][n_x] == "." and not check[n_y][n_x]:
                q.append((n_x, n_y, step+1))
                check[n_y][n_x] = True

if ans != 0:
    air = 0
    for y in range(h):
        for x in range(w):
            if board[y][x] == ".":
                air += 1
    print(air - ans - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
field = []
for i in range(0, H):
	field.append(input())
countwhite = 0
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			countwhite += 1
minfield = []
for i in range(0, H):
	lst = []
	for j in range(0, W):
		lst.append(5000000000000000)
	minfield.append(lst)
queue = [[1, [0, 0]]]
while queue != []:
	now = queue.pop(0)
	if now[0] < minfield[now[1][0]][now[1][1]]:
		minfield[now[1][0]][now[1][1]] = now[0]
		for i in range(0, 2):
			nexth = now[1][0] - 1 + 2*i
			if 0 <= nexth and nexth < H:
				if field[nexth][now[1][1]] == '.':
					queue.append([now[0]+1, [nexth, now[1][1]]])
			nextw = now[1][1] - 1 + 2*i
			if 0 <= nextw and nextw < W:
				if field[now[1][0]][nextw] == '.':
					queue.append([now[0]+1, [now[1][0], nextw]])
if minfield[H-1][W-1] == 5000000000000000:
	print(-1)
else:
	print(countwhite-minfield[H-1][W-1])

Submission status: Accepted

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

C = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      C += 1
    
S[0][0] = 0
for l in range(C-1):
  for i in range(H):
    for j in range(W):
      if S[i][j] == l:     
        for k in [[0,1],[1,0],[-1,0],[0,-1]]:
          if not(0 <= i + k[0] < H):
            continue
          elif not(0 <= j + k[1] < W):
            continue
          elif S[i+k[0]][j+k[1]] != ".":
            continue
          else:
            S[i+k[0]][j+k[1]] = S[i][j]+1
        
if S[H-1][W-1] == ".":
  print(-1)
  exit()
  
ans = C - S[H-1][W-1] -1
print(ans)

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((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            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

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1

# 白いマスを数える
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    # 白いマスの数から最短経路でかかるコスト分を引く
    # ゴールを黒いマスに変えることはできないためその分も引く
    print(white - res - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

que = deque([[0, 0]])

flag = False
while len(que):
    px, py = que.popleft()
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i, j in zip(dx, dy):
        nx = px + i
        ny = py + j
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if maze[ny][nx] == '#':
            continue
        if visited[ny][nx]:
            continue
            
        visited[ny][nx] = visited[py][px] + 1
        que.append([nx, ny])
        
        if nx == W-1 and ny == H-1:
            cnt = visited[ny][nx] + 1
            flag = True
            break
    if flag:
        break

if flag:
    print(H*W - black - cnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
	H, W = map(int,input().split())
	pos = [""]*H
	for i in range(H):
		pos[i] = input()

	offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	def bfs(s, h, w):
		queue = [[0, 0, 0]]
		is_visited = [[False for _ in range(w)] for _ in range(h)]
		is_visited[0][0] = True
		while queue:
			cur = queue.pop(0)
			for o in offset:
				y, x = cur[0]+o[0], cur[1]+o[1]
				if x < 0 or x >= w or y < 0 or y >= h:
					continue
				if x == w-1 and y == h-1:
					return cur[2]+1
				if is_visited[y][x]:
					continue
				if s[y][x] == ".":
					queue.append([y, x, cur[2]+1])
					is_visited[y][x] = True
		return -1

	white_num = 0
	for i in range(H):
		for j in range(W):
			if pos[i][j] == ".":
				white_num += 1
	route = bfs(pos, H, W)
	if route == -1:
		print(-1)
	else:
		print(white_num-route-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W and S[h][w] == '.'


dot_count = 0
for r in S:
    dot_count += r.count('.')

# 道の数 - 最短路
sh = sw = 0
que = deque()
que.append((sh, sw, 0))
delta = list(zip(*[[0, 0, 1, -1], [1, -1, 0, 0]]))
distance = -1
while que:
    h, w, d = que.popleft()
    if h == H - 1 and w == W - 1:
        distance = d
        break
    for dh, dw in delta:
        if ok(h + dh, w + dw):
            S[h + dh][w + dw] = '#'
            que.append((h + dh, w + dw, d + 1))

if distance > 0:
    print(dot_count - distance - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
X = [1,0,-1,0]
Y = [0,-1,0,1]
num = 0
D = []
for i in range(H):
  s = list(input())
  num += s.count(".")
  D.append(s)
Q = deque()
Q.append((0,0))
dist = [[-1]*W for i in range(H)]
dist[0][0] = 0

while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if 0 <= nx < W and 0 <= ny < H and dist[ny][nx] == -1 and D[ny][nx] == ".":
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

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

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
went = [[False]*W for i in range(H)]
queue = deque()#append/popleft/(h,w,turn)
queue.append((0,0,0))
went[0][0] = True
dist = -1
while queue:
    curh,curw,curturn = queue.popleft()
    if curh==H-1 and curw == W-1:
        dist = curturn
        break
    for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        newh,neww = curh+dx,curw+dy
        if 0<=newh<H and 0<=neww<W and not went[newh][neww]\
        and S[newh][neww]==".":
            went[newh][neww] = True
            queue.append((newh,neww,curturn+1))

white = sum([s.count(".") for s in S])
if dist == -1:print(-1)
else:print(white - dist - 1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
INF = 10**9
maze = []
for i in range(H):
    maze.append(input())

dist = [[INF for j in range(W)] for i in range(H)]

sy, sx = 0, 0
gy, gx = H - 1, W - 1

dirc = [[0, 1], [1, 0], [0, -1], [-1, 0]]

togo = []
togo.append([sy, sx])
dist[sy][sx] = 0
def bfs():
    while len(togo) > 0:
        y, x = togo.pop(0)
        if y == gy and x == gx:
            break
        for dy, dx in dirc:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and dist[ny][nx] == INF:
                togo.append([ny, nx])
                dist[ny][nx] = dist[y][x] + 1
    
    return dist[gy][gx]

ret = bfs()

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

if ret == INF:
    print(-1)
else:
    res = cnt-ret-1
    print(res)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(s.count('.') for s in S)

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = None
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if (not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '#' or (ni, nj) in used:
            continue
        used.add((ni, nj))
        que.append((ni, nj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
C = [list(input()) for _ in range(H)]
# スタートの位置
sy,sx = 0,0
# ゴールの位置
gy,gx = H-1,W-1

INF = 1000000
# スタート、ゴールを除く.の数
nulcnt = -2

# . をすべてINFにしながら、.の数を数える（スタート、ゴール除く）
for y in range(H):
    for x in range(W):
        if C[y][x] == '.':
            nulcnt += 1
            C[y][x] = INF

def bfs(C,sy,sx,gy,gx):
    # スタート地点をqueに入れ、距離を０に
    que = deque([[sy,sx]])
    C[sy][sx] = 0

    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            # スタートからゴールまでの最短経路数を返す
            return C[gy][gx]
        for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
            ny = y + dy
            nx = x + dx
            if (0 <= ny < H) and (0 <= nx < W):
                if C[ny][nx] != '#' and (C[ny][nx] > C[y][x] + 1):
                    que.append([ny,nx])
                    C[ny][nx] = C[y][x] + 1
    # ゴールにたどりつけなかった
    return -1

saitan = bfs(C,sy,sx,gy,gx)

if saitan != -1:
    print(nulcnt - saitan + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

# #を数えておく
cntsharp = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j] == "#":
            cntsharp += 1

# BFS
seen = [[-1] * (W+2) for i in range(H+2)]
seen[1][1] = 0 # 始めどこから行くか
q = deque([[1,1,1]]) #h,w,p
mvs = [(1,0),(-1,0),(0,1),(0,-1)]

while len(q) > 0:
    h,w,p = q.popleft()
    for dh,dw in mvs: 
        next_h = h + dh
        next_w = w + dw
        next_p = p + 1
        if seen[next_h][next_w] == -1 and board[next_h][next_w] != "#":
            seen[next_h][next_w] = next_p
            q.append([next_h,next_w,next_p])
            
if seen[H][W] == -1:
    print(-1)
else:
    print(H*W-cntsharp-seen[H][W])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())
from collections import deque
dp=[[-1]*w for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
que=deque([])
que.append((0,0))
dp[0][0]=1
while len(que)>0:
    now=que.popleft()
    for i in d:
        if 0<=now[0]+i[0]<=h-1 and 0<=now[1]+i[1]<=w-1:
            x=now[0]+i[0]
            y=now[1]+i[1]
            if dp[x][y]==-1 and s[x][y]=='.':
                que.append((x,y))
                dp[x][y]=dp[now[0]][now[1]]+1
if dp[h-1][w-1]==-1:
    print(-1)
else:
    count=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='.':
                    count=count+1
    print(count-dp[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
sx,sy=1,1
gx,gy=h,w
w+=2

grh=[list('#')*w]
res=0
for i in range(h):
    tmp=input()
    res+=tmp.count('.')    
    grh+=[list('#'+tmp+'#')]
grh+=[list('#')*w]
h+=2


def bfs():
    que=deque()
    g=[[float('inf')]*w for i in range(h)]
    g[sx][sy]=1
    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que.append((sx,sy))

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if grh[nx][ny]=='.' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1

    return g[gx][gy]


res-=bfs()
print(-1 if res==float('-inf') else res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

H, W = LI()
c = SR(H)
sy, sx = 0, 0
gy, gx = H-1, W-1

white_counts = 0
for i in range(H):
    for j in range(W):
        if (c[i][j]=="."):
            white_counts += 1

def bfs(sy, sx, gy, gx, c, road=".", blocks=["#"]):
    H = len(c)
    W = len(c[0])
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    dist = [[107]*W for i in range(H)]
    dist[sy][sx] = 0

    q = deque()
    q.append((sy, sx))

    while q:
        y, x = q.popleft()
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx):
                        return (dist[y][x]+1)
                    elif (dist[y+dy][x+dx] > dist[y][x]+1):
                        dist[y+dy][x+dx] = dist[y][x]+1
                        q.append((y+dy, x+dx))
    return -1

path = bfs(sy, sx, gy, gx, c)
print(white_counts-path-1 if (path!=-1) else -1)

Submission status: Accepted

Solution code:
from sys import stdin
input = [int(x) for x in stdin.readline().rstrip().split()]
H=input[0]
W=input[1]
start=[0,0]
goal=[H-1,W-1]
road=[]
wall_len=0
for h in range(H):
    road.append(list(stdin.readline().rstrip().split()[0]))
    wall_len+=len([x for x in road[h] if x == "#"])

def bfs(H,W,start,goal,road):
    road_dist=[[float("inf") for w in range(W)] for h in range(H)]
    queue_list=[start]
    already_list=[]
    road_dist[start[0]][start[1]]=0
    move_list=[[0,1],[0,-1],[1,0],[-1,0]]
    while len(queue_list)>0:
        now_position=queue_list.pop(0)
        already_list.append(now_position)
        now_dist=road_dist[now_position[0]][now_position[1]]
        if now_position == goal:
            break
        next_list=[]
        for dy, dx in move_list:
            next_y=now_position[0]+dy
            next_x=now_position[1]+dx
            if (0<=next_x<W) & (0<=next_y<H):
                if (road[next_y][next_x]!="#") & (road_dist[next_y][next_x]==float("inf")):
                    next_list.append([next_y,next_x])
        for p in next_list:
            if p in queue_list:
                continue
            if p in already_list:
                continue
            queue_list.append(p)
            road_dist[p[0]][p[1]]=now_dist+1

    return road_dist

rd=bfs(H,W,start,goal,road)
if rd[goal[0]][goal[1]] == float("inf"):
    output=-1
else:
    output=H*W-(rd[goal[0]][goal[1]]+1+wall_len)

print(output)

Submission status: Accepted

Solution code:
from collections import deque

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

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

dist = [[-1 for i in range(W)] for j in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    q = deque()
    q.append([0, 0])
    dist[0][0] = 1
    while q:
        p = q.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:
                if s[nx][ny] != '#' and dist[nx][ny] == -1:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[H-1][W-1]

d = bfs()
if d > 0:
    ans = cnt - d
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue

H, W = map(int, input().split())
N = H * W
field = []

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

INF = 10000
cost = [[INF] * W for _ in range(H)]

for _ in range(H):
    field.append(list(input()))

n_black = 0
for r in field:
    for c in r:
        if c == '#':
            n_black += 1

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

while not que.empty():
    x, y = que.get()

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

    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and field[nx][ny] != '#' and cost[nx][ny] == INF:
            que.put((nx, ny))
            cost[nx][ny] = cost[x][y] + 1    

if cost[H-1][W-1] == INF:
    print(-1)
    exit()

print(N - n_black - cost[H-1][W-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[[1]*(w+2)]+[[1]+[1 if i=="#" else 0 for i in input()]+[1] for i in range(h)]+[[1]*(w+2)]
c=[[0]*(w+2) for i in range(h+2)]
q=[(1,1)]
e=[(0,1),(0,-1),(1,0),(-1,0)]
kyori=1
while len(q)>0 and c[h][w]==0:
    tl=q
    q=[]
    for x,y in tl:
        for X,Y in e:
            if(l[y+Y][x+X]==0 and c[y+Y][x+X]==0):
                q.append((x+X,y+Y))
                c[y+Y][x+X]=1
    kyori+=1
if  c[h][w]==0:
    print(-1)
else:
    print(sum([i.count(0) for i in l])-kyori)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[0][0]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]

import sys
sys.setrecursionlimit(10**4)
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
Grid[0][0] = 0
if  flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-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
import sys

H,W  = map(int, input().split())
sx, sy = 1,1
gx, gy = W,H
count=-1
maze=[0]*(H+2)
maze[0] = list("#"*(W+2))
for i in range(1,H+1):
    maze[i] = list("#"+input()+"#")
    count+=maze[i].count('.')
maze[H+1] = list("#"*(W+2))
ans = [[-1 for i in range(W+2)] for j in range(H+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append((sx, sy))
ans[sx][sy] = 0
 
while q:
    cx, cy = q.popleft()
    if cx == gx and cy == gy:
        print(count-ans[gy][gx])
        sys.exit()
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]
        if ans[ny][nx] == -1 and maze[ny][nx] != "#":
            q.append((nx, ny))
            ans[ny][nx] = ans[cy][cx] + 1
print(-1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
#H×Wのマス目入力の周りに"."を付け加える関数
def pixel_input(H,W,border="#"):
    pixel = \
    [[border]*(W+2)] + \
    [[border] + list(input()) + [border] for _ in range(H)] + \
    [[border]*(W+2)]
    return pixel
p=pixel_input(H,W)
s=sum([p[i].count("#")-2 for i in range(1,H+1)])

que=[(1,1)]
cnt=1

while(1):
    que2=[]
    for x,y in que:
        if p[x-1][y]==".":
            que2.append((x-1,y))
            p[x-1][y]="#"
        if p[x+1][y]==".":
            que2.append((x+1,y))
            p[x+1][y]="#"
        if p[x][y-1]==".":
            que2.append((x,y-1))
            p[x][y-1]="#"
        if p[x][y+1]==".":
            que2.append((x,y+1))
            p[x][y+1]="#"
    cnt+=1
    if (H,W) in que2:
        break
    elif que2==[]:
        cnt=-1
        break
    else:
        que=que2

if cnt>=0:
    print(H*W-s-cnt)
else:
    print(-1)

Submission status: Accepted

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


def bfs(h, w):  
    for i in dhw:
        dh = i[0]
        dw = i[1]
        if h+dh < 0 or h+dh > H-1 or w+dw < 0 or w+dw > W-1 or field[h+dh][w+dw] == '#':
            continue
        if seen[h+dh][w+dw] == -1:
            seen[h+dh][w+dw] = seen[h][w] + 1
            todo.append([h+dh, w+dw])
        
        
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_origin = 0
for i in range(H):
    black_origin += field[i].count('#')
dhw = ((-1, 0), (1, 0), (0, -1), (0, 1))
seen = [[-1]*W for _ in range(H)]
todo = deque()
seen[0][0] = 0
todo.append([0, 0])

while len(todo) > 0:
    n_ad = todo.popleft()
    bfs(n_ad[0], n_ad[1])

if seen[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W-(seen[H-1][W-1]+1)-black_origin)

Submission status: Accepted

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

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

queue = [(0,0)]
check = [(0,0)]
C = [0,0]
count = 0
hNow,wNow = 0,0

while 1:
    count += 1
    if len(queue) != 0:
        if queue[0] == (H-1,W-1):
            print(H*W - black -1 - max(C))
            break # ゴールか判定
    if len(queue) == 0:
        print(-1)
        break
    hNow,wNow = queue[0][0],queue[0][1]
    queue.pop(0)
    if hNow < H-1:
        if map_list[hNow+1][wNow] != "#":
            if (hNow+1,wNow) not in check:
                queue.append((hNow+1,wNow))
                check.append((hNow+1,wNow))
                C.append(C[count]+1)
    if wNow < W-1:
        if map_list[hNow][wNow+1] != "#":
            if (hNow,wNow+1) not in check:
                queue.append((hNow,wNow+1))
                check.append((hNow,wNow+1))
                C.append(C[count]+1)
    if hNow > 0:
        if map_list[hNow-1][wNow] != "#":
            if (hNow-1,wNow) not in check:
                queue.append((hNow-1,wNow))
                check.append((hNow-1,wNow))
                C.append(C[count]+1)
    if wNow > 0:
        if map_list[hNow][wNow-1] != "#":
            if (hNow,wNow-1) not in check:
                queue.append((hNow,wNow-1))
                check.append((hNow,wNow-1)) #近いやつを入れる
                C.append(C[count]+1)
    #print(queue)
#print(count)
#print(C)
#print(black)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [["#" for _ in range(W+2)]]
white = 0
for h in range(H):
    s = ["#"] + list(input()) + ["#"]
    white += s.count(".")
    S.append(s)
S.append(["#" for _ in range(W+2)])

S[1][1] = 0
start = (1, 1)
goal = (H, W)
ans = -1
stack = deque()
stack.append(start)
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while stack:
    x, y = stack.pop()
    if (x, y) == goal:
        ans = white - S[x][y] - 1
        print(ans)
        exit()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if S[nx][ny] != ".":
            continue
        stack.appendleft((nx, ny))
        S[nx][ny] = S[x][y] + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
point = -1
kabe = 0
for i in range(H):
    maze.append(input())
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            kabe += 1

def bfs(sy,sx,gy,gx,h,w):
    jikan = 0
    q = deque([sy*w + sx])
    saitan = [1000000]*h*w
    saitan[sy*w + sx] = 0
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and saitan[gy*w +gx] == 1000000:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if maze[my][mx] == '#':
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
    jikan = saitan[gy*w +gx]
    return jikan

    #print(sg_list[0][0],sg_list[0][1],sg_list[1][0],sg_list[1][1])
    #print('test')
time = bfs(0,0,H-1,W-1,H,W)
#print(time)
if time == 1000000:
    point = -1
else:
    point = point + 1 +(H * W - time - kabe-1)
print(point)

Submission status: Accepted

Solution code:
import collections

h,w=map(int,input().split())
checked=[[0]*(w+2) for _ in range(h+2)]
board=[['#']*(w+2)]
for _ in range(h):
  board.append(['#']+list(input())+['#'])
board.append(['#']*(w+2))
q=collections.deque()
q.append((1,1,1))
checked[1][1]=1
ans=-1
while 1:
  if len(q)==0:
    break
  x,y,t=q.popleft()
  if x==w and y==h:
    ans=t
    break
  if board[y][x-1]=='.' and checked[y][x-1]==0:
    checked[y][x-1]=1
    q.append((x-1,y,t+1))
  if board[y][x+1]=='.' and checked[y][x+1]==0:
    checked[y][x+1]=1
    q.append((x+1,y,t+1))
  if board[y-1][x]=='.' and checked[y-1][x]==0:
    checked[y-1][x]=1
    q.append((x,y-1,t+1))
  if board[y+1][x]=='.' and checked[y+1][x]==0:
    checked[y+1][x]=1
    q.append((x,y+1,t+1))
if ans==-1:
  print(-1)
else:
  cnt=0
  for i in range(1,h+1):
    cnt+=board[i].count('#')-2
  print(h*w-cnt-ans)