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
from collections import deque
import numpy as np

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

dd = ((-1, 0), (1, 0), (0, -1), (0, 1))
q = deque([(1, 1)])
cost[1, 1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in dd:
        nx = x + dx
        ny = y + dy
        if S[nx, ny] == 0 and cost[nx, ny] == -1:
            cost[nx, ny] = cost[x, y] + 1
            q.append((nx, ny))

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

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
memo = [[0 for _ in range(w)] for _ in range(h)]
step = [[1, 0], [-1, 0], [0, 1], [0, -1]]

memo[0][0] = 1
white = 0
for row in maze:
    white += row.count('.')

q = [[0, 0, 0]]

while q:
    x, y, c = q.pop(0)
    for a, b in step:
        next_x = x + a
        next_y = y + b
        if next_x == h - 1 and next_y == w - 1:
            print(white - (c + 2))
            exit()
        if next_x >= h or next_x < 0:
            continue
        if next_y >= w or next_y < 0:
            continue
        if memo[next_x][next_y] == 1:
            continue
        if maze[next_x][next_y] == '#':
            continue
        memo[next_x][next_y] = 1
        q.append([next_x, next_y, c + 1])
print(-1)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs():
    q = deque()
    q.append((0, 0))
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    dist = [[inf] * w for _ in range(h)]
    dist[0][0] = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx >= 0 and nx < w and ny >= 0 and ny < h and dist[ny][nx] == inf and maze[ny][nx] != '#':
                dist[ny][nx] = dist[cy][cx] + 1
                q.append((nx, ny))
    return dist[h - 1][w - 1]

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

d = bfs()
if d == inf:
    print(-1)
else:
    print(h * w - cnt - d - 1)

Submission status: Accepted

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

grid[1][1] = "1"

def bfs():
    q = deque([(1,1)])
    used = set()
    while q:
        here = q.popleft()
        num = int(grid[here[0]][here[1]])
        x = here[0]
        y = here[1]
        if grid[x-1][y] == "." and (x-1,y) not in used:
            grid[x-1][y] = str(num + 1)
            used.add((x-1,y))
            q.append((x-1,y))
        if grid[x+1][y] == "." and (x+1,y) not in used:
            grid[x+1][y] = str(num + 1)
            used.add((x+1,y))
            q.append((x+1,y))
        if grid[x][y-1] == "." and (x,y-1) not in used:
            grid[x][y-1] = str(num + 1)
            used.add((x,y-1))
            q.append((x,y-1))
        if grid[x][y+1] == "." and (x,y+1) not in used:
            grid[x][y+1] = str(num + 1)
            used.add((x,y+1))
            q.append((x,y+1))

bfs()
if grid[h][w] == ".":
    print(-1)
else:
    print(white-int(grid[h][w]))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]
queue = deque()
dist = [[-1] * W for _ in range(H)]
queue.append((0, 0))
dist[0][0] = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
    i, j = queue.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and s[ni][nj] == '.' and dist[ni][nj] == -1:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
ans = 0
if dist[-1][-1] == -1:
    ans = -1
else:
    ans = sum(row.count('.') for row in s) - (dist[-1][-1] + 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
def bfs(sy,sx,gy,gx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])

h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=h-1,w-1
bfs(sy,sx,gy,gx)
# print(visited)

if visited[gy][gx]==-1:
    print(-1)
    exit()

c=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            c+=1
print(h*w-c-(visited[gy][gx]+1))

Submission status: Accepted

Solution code:
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
white=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="#":
            a[j+1]=True
        else:
            white+=1

    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
d.append((1,1))
ans=-1
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if index1==h and index2==w:
            ans=distance
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
if ans>=0:
    print(white-ans-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
visited = [[-1] * w for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]
 
sy, sx= 0, 0
gy, gx = h-1, w-1
 
queue = deque([(sy, sx, 0)])
 
while queue:
    y, x, dist = queue.popleft()
    for dy, dx in move:
        if maze[y+dy:y+dy+1] and maze[y+dy][x+dx:x+dx+1]:
            if maze[y+dy][x+dx] == "." and visited[y+dy][x+dx] == -1:
                visited[y+dy][x+dx] = dist + 1
                queue.append((y+dy, x+dx, dist+1))
shortest_distance = visited[gy][gx]
 
if shortest_distance == -1:
    print("-1")
else:
    white_count = 0
    for row in maze:
        for cell in row:
            if cell == ".":
                white_count += 1
 
    score = white_count - 1 - shortest_distance
    print(score)

Submission status: Accepted

Solution code:
#1,1からH,Wへの最短経路の距離を求め、全体から引く
# -*- coding: utf-8 -*-
h,w = list(map(int,input().split()))
inf=float("inf")
s = [[-1]*(w+2)] + [[-1] + [inf if i=="." else -1 for i in input()] + [-1] for _ in range(h)] + [[-1]*(w+2)]
from math import isinf
white = 0
for i in s:
    for j in i:
        if isinf(j):
            white+=1


inf=float("inf")
from collections import deque
s[1][1] = 0
stack_deque = deque([[1,1]])
ret = -1
cnt = 0
while len(stack_deque) > 0:
    curh,curw = stack_deque.popleft()
    cnt = s[curh][curw]+1
    if curh == h and curw==w:
        ret = white - (cnt-1) -1
        break
    if isinf(s[curh-1][curw]):
        s[curh-1][curw]=cnt
        stack_deque.append([curh-1,curw])
    if isinf(s[curh+1][curw]):
        s[curh+1][curw]=cnt
        stack_deque.append([curh+1,curw])
    if isinf(s[curh][curw-1]):
        s[curh][curw-1]=cnt
        stack_deque.append([curh,curw-1])
    if isinf(s[curh][curw+1]):
        s[curh][curw+1]=cnt
        stack_deque.append([curh,curw+1])
print(ret)

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [input() for i in range(H)]
q = deque([(0,0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 1

while q:
    y, x = q.popleft()
    L = [(1,0), (-1,0), (0,1), (0,-1)]
    for i, j in L:
        if ((0 <= y+i <= H-1 and 0 <= x+j <= W-1)
            	and dist[y+i][x+j] == -1
            	and graph[y+i][x+j] == "."):
        	dist[y+i][x+j] = dist[y][x] + 1
        	q.append((y+i, x+j))

white = 0
for i in range(H):
    white += graph[i].count(".")
    
if dist[H-1][W-1] == -1:
    print("-1")
else:
    ans = white - dist[H-1][W-1]
    print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    h,w=MI()
    ss=[[c=="#" for c in SI()] for _ in range(h)]
    dist=[[-1]*w for _ in range(h)]
    q=deque()
    q.append((0,0))
    dist[0][0]=1
    while q:
        i,j=q.popleft()
        d=dist[i][j]
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if (ni,nj)==(h-1,w-1):
                ans = h * w - (d + 1) - sum(sum(row) for row in ss)
                print(ans)
                exit()
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if dist[ni][nj]!=-1:continue
            if ss[ni][nj]:continue
            dist[ni][nj]=d+1
            q.append((ni,nj))
    print(-1)

main()

Submission status: Accepted

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


sy,sx = 0,0
gy,gx = h-1, w-1
que = deque([(sy,sx,0)])

flg = False
ret = -1
while que:
    y,x,c = que.popleft()
    if y==gy and x==gx:
        flg = True
        ret = c
        break
    if cost[y][x] != -1:
        continue
    cost[y][x] = c
    for dy,dx in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
        ny = y + dy
        nx = x + dx
        if 0<=ny<h and 0<=nx<w:
            if S[ny][nx]!='#':
                que.append((ny,nx,c+1))
if not flg:
    print(-1)
else:
    blk, wht = 0, 0
    for s in S:
        for ss in s:
            if ss=='#':
                blk += 1
            else:
                wht += 1
    print(h*w-ret-1-blk)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
S = [["#"] * (W + 2)]
S += [["#"] + list(input()) + ["#"] for _ in range(H)]
S.append(["#"] * (W + 2))

INF = 10 ** 5

visited = [[False] * (W + 2) for _ in range(H + 2)]
dist = [[INF] * (W + 2) for _ in range(H + 2)]

DY = [-1,1,0,0]
DX = [0,0,-1,1]

from collections import deque
def bfs():
    visited[1][1] = True
    dist[1][1] = 0
    que = deque([(1,1)])
    while que:
        y,x = que.popleft()
        for dy,dx in zip(DY,DX):
            ny = y + dy
            nx = x + dx
            if visited[ny][nx]: continue
            if S[ny][nx] == "#": continue

            if dist[ny][nx] > dist[y][x] + 1:
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True
                que.append((ny,nx))
    return True if visited[H][W] else False

if not bfs():
    print(-1)
    exit()

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

print(ans - (dist[H][W] + 1))

Submission status: Accepted

Solution code:
def main():
    from collections import deque

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

    already_black = sum(row.count('#') for row in s)

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

    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1

    while dq:
        r, c = dq.popleft()
        if r == H - 1 and c == W - 1:
            break
        if r > 0 and s[r - 1][c] == '.' and not (~dist[r - 1][c] and dist[r - 1][c] <= dist[r][c] + 1):
            dist[r - 1][c] = dist[r][c] + 1
            dq.append((r - 1, c))
        if c > 0 and s[r][c - 1] == '.' and not (~dist[r][c - 1] and dist[r][c - 1] <= dist[r][c] + 1):
            dist[r][c - 1] = dist[r][c] + 1
            dq.append((r, c - 1))
        if r < H - 1 and s[r + 1][c] == '.' and not (~dist[r + 1][c] and dist[r + 1][c] <= dist[r][c] + 1):
            dist[r + 1][c] = dist[r][c] + 1
            dq.append((r + 1, c))
        if c < W - 1 and s[r][c + 1] == '.' and not (~dist[r][c + 1] and dist[r][c + 1] <= dist[r][c] + 1):
            dist[r][c + 1] = dist[r][c] + 1
            dq.append((r, c + 1))

    if ~dist[H - 1][W - 1]:
        ans = H * W - (dist[H - 1][W - 1] + already_black)
    else:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    inf = 10 ** 9 + 7
    grid = [list(input()) for _ in range(h)]
    count = [[inf for _ in range(w)] for _ in range(h)]
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    wall = 0
    count[0][0] = 1
    for g in grid:
        wall += g.count("#")
    s = deque([[0, 0]])
    while s:
        y, x = s.popleft()
        if grid[y][x] == ".":
            grid[y][x] = "#"
            for dy, dx in d:
                if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == ".":
                    count[y + dy][x + dx] = min(count[y + dy][x + dx], count[y][x] + 1)
                    s.append([y + dy, x + dx])
    print(h * w - count[-1][-1] - wall if count[-1][-1] != inf else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    from collections import deque

    def bfs(sy, sx):
        que = deque()
        dist = [[-1]*W for i in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if c[next_h][next_w] == '#':
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                que.append((next_h, next_w))
        return dist
    d = bfs(0, 0)
    if d[-1][-1] == -1:
        return print(-1)
    seen = [True]*(d[H-1][W-1] + 1)
    ans = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                continue
            elif d[h][w] != -1 and d[h][w] <= d[-1][-1] and seen[d[h][w]]:
                seen[d[h][w]] = False
                continue
            else:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = H*W - 2
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            ans -= 1
q = collections.deque()
q.append((0, 0, 0))
flag = False
while(q):
    x, y, d = q.popleft()
    if x == W-1 and y == H - 1:
        ans -= (d-1)
        flag = True
        break
    if y > 0 and s[y-1][x] == ".":
        q.append((x, y-1, d+1))
        s[y-1][x] = "#"
    if x > 0 and s[y][x-1] == ".":
        q.append((x-1, y, d+1))
        s[y][x-1] = "#"
    if y < H - 1 and s[y+1][x] == ".":
        q.append((x, y+1, d+1))
        s[y+1][x] = "#"
    if x < W - 1 and s[y][x+1] == ".":
        q.append((x+1, y, d+1))
        s[y][x+1] = "#"

if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

# 白いマスの数
ans=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            ans+=1



import collections
from collections import deque
def clear_maze(sx, sy, gx, gy):

    INF=-10**9
    distance = [[INF for i in range(w+2)] for j in range(h+2)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        d = deque()
        d.append((sx, sy))
        distance[sx][sy] = 0

        while len(d):
            x, y = d.popleft()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx<h and  0 <= ny<w:
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        d.append((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1

        return distance[gx][gy]

    return bfs()

v=clear_maze(0,0,h-1,w-1)
INF=-10**9
if v!=INF:
    print(ans-v-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def bfs():
    #sからそのマスまでの最短距離を保存する配列
    d = [[float("inf")]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #s,gの座標を得る
    sx,sy = 0,0
    gx,gy = n-1,m-1
    #キューにs座標をセットしてsのマスを0にする
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 0
    
    #全部の行けるところをqueに入れてsからの距離を＋1ずつしていく
    while q:
        p = q.popleft()
        #gでbreakしなければ行ける全てのマスまでの最短距離を求める事になる
        if p[0] == gx and p[1] == gy:
            break
        #上下左右のマスを調べる
        for k in range(4):
            xi,yi = p[0]+dx[k],p[1]+dy[k]
            #そのマスにいけて行ったことないなら、そこを起点に再起＋そこまでの距離を求める
            if 0 <= xi < n and 0 <= yi < m and maze[xi][yi] != "#" and d[xi][yi] == float("inf"):
                q.append((xi,yi))
                d[xi][yi] = d[p[0]][p[1]] + 1

    #gまでの最短距離を返す
    return d[gx][gy]

n,m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == ".":
            c += 1
res = bfs()
#到達できるなら
if 0 < res < float("inf"):
    print(c - res -1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
sm = 0
for i in range(H): sm += S[i].count(".")
Q = dq([0])
dp = [H * W] * (H * W)
dp[0] = 1
d = [-1, 0, 1, 0]
while len(Q):
  p = Q.popleft()
  y = p // W
  x = p % W
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if S[u][v] == "#": continue
      if dp[u * W + v] == H * W:
        dp[u * W + v] = dp[p] + 1
        Q.append(u * W + v)

if dp[-1] == H * W: print(-1)
else: print(sm - dp[-1])

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
data = []
ans = h*w
for i in range(h):
    s = input()
    for x in s:
        if x == "#":
            ans -= 1
    data.append(s)
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 0
queue = deque()
queue.append((0,0))
while queue:
    x,y = queue.popleft()
    for dx,dy in [[-1,0],[1,0],[0,1],[0,-1]]:
        tox = x+dx
        toy = y+dy
        if 0<=tox<h and 0<=toy<w and dist[tox][toy] == -1 and data[tox][toy] == ".":
            dist[tox][toy] = dist[x][y] + 1
            queue.append((tox,toy))

if dist[-1][-1] == -1:
    print(-1)
else:
    print(ans-dist[-1][-1]-1)

Submission status: Accepted

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

que = deque()
que.append((0, 0))
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 1
while que:
  y, x = que.pop()
  for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    ny, nx = y+i, x+j
    if 0 <= ny < h and 0 <= nx < w:
      if S[ny][nx] == "#":
        continue
      if dist[ny][nx] == -1:
        dist[ny][nx] = dist[y][x] + 1
        que.appendleft((ny, nx))
  if ny == h-1 and nx == w-1:
    break
    
if dist[h-1][w-1] == -1:
  ans = -1
else:
  cnt = 0
  for i in range(h):
    cnt += S[i].count(".")
  ans = cnt - dist[h-1][w-1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dx = [0,1,0,-1]; dy = [1,0,-1,0]
h,w = inpl()
g = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
q = deque()
q.append([0,0])

while q:
    y,x = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == -1 and g[ny][nx] == '.':
            dist[ny][nx] = dist[y][x] + 1
            q.append([ny,nx])

if dist[-1][-1] == -1:
    print(-1)
    quit()
bl = sum(i.count('#') for i in g)
wh = dist[-1][-1] + 1
print(h*w - (wh+bl))

Submission status: Accepted

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

ans = 0
D = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if s[i][j] == ".":
      D[i][j] = 0
      ans += 1
    else:
      D[i][j] = -1

g = gridMan(D)
g.makeWall()

L, ma = g.dist([0, 0])

if L[-1][-1] == -1:
  print(-1)
  exit()

print(ans - L[-1][-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)]
S[0][0]=1
next  = deque([[0,0]])
ans = H*W
while next:
    x,y =next.popleft()
    s = S[x][y]
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
        if 0<=x+i<H and 0<=y+j<W and S[x+i][y+j]=='.':
            S[x+i][y+j]=s+1
            next.append([x+i,y+j])
for i in S:
    ans -=i.count('#')
if type(S[H-1][W-1])==str:
    print(-1)
else:
    print(ans-S[H-1][W-1])

Submission status: Accepted

Solution code:
import collections
import itertools

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


def is_white(i, j):
    return i in range(H) and j in range(W) and s[i][j] == "."


def adjacent_white_squares(i, j):
    return [
        (i + di, j + dj)
        for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]
        if is_white(i + di, j + dj)
    ]


def distance_to_goal():
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[0][0] = 0
    queue = collections.deque([(0, 0)])

    d = 0
    while queue:
        i, j = queue.popleft()
        to_visit = [
            (k, l) for k, l in adjacent_white_squares(i, j) if distances[k][l] == -1
        ]
        for k, l in to_visit:
            if (k, l) == (H - 1, W - 1):
                return distances[i][j] + 1

            distances[k][l] = distances[i][j] + 1
            queue.append((k, l))

    return -1


def black_squares():
    return sum(1 for c in itertools.chain.from_iterable(s) if c == "#")


distance = distance_to_goal()
if distance == -1:
    print(-1)
else:
    print(H * W - (distance + 1) - black_squares())

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[ input() for _ in range(h)]
dist=[ [float('inf') for _ in range(w)] for _ in range(h)]
#print(s)
#do a bfs 
dq=deque()
dist[0][0]=0
dq.append([0,0])
white=0
for i in s:
    white+=i.count('.')
#print(white)
while len(dq)>0:
    xx,yy=dq.popleft()
    if xx==h-1 and yy==w-1:
        break
    for i,j in zip([-1,0,1,0], [0,1,0,-1]):
            x=xx+i
            y=yy+j
            def valid(x,y):
                if not(x>=0 and x<h and y>=0 and y<w) == True:
                    return False
                if s[x][y]=='.':
                    return True
                else:
                    return False
            if valid(x,y):
                if dist[x][y]>dist[xx][yy]+1:
                    dist[x][y]=1+dist[xx][yy]
                    dq.append([x,y])
#print(dist[h-1][w-1])
if dist[h-1][w-1]!=float('inf'):
    print(white-1-dist[h-1][w-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
import collections

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

tizu = []
ans = 0
for i in range(h):
    s = list(input())
    ans += s.count(".")
    tizu.append(s)
  
#4方向走査
dy = [1,0,-1,0]
dx = [0,1,0,-1]

def f(y,x,count):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = count

#最短でゴールまで行く
q = collections.deque()
q.append((0,0))
tizu[0][0] = 0
while q:
    s =  q.popleft()
    count = tizu[s[0]][s[1]]
    f(s[0],s[1],count+1)

#たどり着けない時
if tizu[h-1][w-1] == ".":
    print(-1)
    exit()

            
print(ans-tizu[h-1][w-1] - 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((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        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
    if d[gy][gx] != float("inf"):
        return d[gy][gx]
    else:
        return -1
h, w = map(int, input().split())
sy, sx = 0, 0
gy, gx = h - 1, w - 1
s = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            black += 1
if bfs() == -1:
    print(-1)
else:
    print(h * w - bfs() - black - 1)

Submission status: Accepted

Solution code:
def calc_distance(maze):
    sx,sy,gx,gy = 0,0,w-1,h-1
    #maze = maze.split()
    INF = 10000000000
    field_x_length = w
    field_y_length = h
        
    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)
        
    queue = []
    queue.insert(0, (sy,sx))
    distance[sy][sx] = 0
        
    while queue:
        y, x = queue.pop()
        if(x == gx and y == gy):
            break
                
        for i in range(0,4):
            nx, ny = x +[1,0,-1,0][i], y +[0,1,0,-1][i]
                
            if(0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0,(ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance[gy][gx]
    
h,w = map(int, input().split())
maze = [input() for _ in range(h)]

import collections
count = 0
for i in range(0,h):
    c = collections.Counter(maze[i])
    count += c["#"]

if (calc_distance(maze) < 200):
    print(w*h - count - calc_distance(maze) -1)
else:
    print(-1)