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
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]

    ans = 0
    for y in range(H):
        for x in range(W):
            if board[y][x] == ".":
                ans += 1

    q = deque()
    q.append((0, 0, 0))
    check[0][0] = True
    while len(q) > 0:
        cost, x, y = q.popleft()
        if x == W-1 and y == H-1:
            print(ans - 1 - cost)
            return
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if board[ny][nx] == "." and not check[ny][nx]:
                    q.append((cost+1, nx, ny))
                    check[ny][nx] = True
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

inf = 10 ** 6

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque([[0,0]])
d = [[inf] * w for _ in range(h)]
d[0][0] = 0

while q:
    v = q.popleft()
    if v == [h-1, w-1]:
        break
    for i in range(4):
        x = v[0] + dx[i]
        y = v[1] + dy[i]
        if x>=0 and x<h and y>=0 and y<w and s[x][y]==".":
            if d[x][y] == inf:
                q.append([x,y])
                d[x][y] = d[v[0]][v[1]] + 1

if d[h-1][w-1] == inf:
    print(-1)
else:
    numw = 0
    for i in range(h):
        numw += s[i].count(".")
    print(numw - d[h-1][w-1] -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque

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

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = 0 <= i <= H - 1
    cond_j = 0 <= j <= W - 1
    return cond_i and cond_j


def is_reachable(i, j, ):
    if is_valid(i, j):
        if field[i][j] == '.':
            return True
    return False


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_reachable(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

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

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

if dist[(H - 1, W - 1)] == -1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid_graph = [list(input()) for _ in range(H)]
# 幅優先で最短経路を求めるだけ
q = deque()
q.append([0, 0])
distance = [[1000]*W for _ in range(H)]
distance[0][0] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != 1000:
            continue
        if grid_graph[ny][nx] == "#":
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
black = 0
if distance[H-1][W-1] == 1000:
    print(-1)
    exit()
for i in range(H):
    for j in range(W):
        if grid_graph[i][j] == "#":
            black += 1
print(H*W - distance[H-1][W-1] - black - 1)  # 最後の-1は出発地点のマスを黒くできない分

Submission status: Accepted

Solution code:

from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*w for _ in range(h)]
    dist[sy][sx] = 0 

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy 
            nx = x + dx 
            if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == float('inf') and s[ny][nx] != '#':
                dist[ny][nx] = dist[y][x] + 1 
                q += [[ny, nx]]

    return dist 

d = bfs(0, 0)[h-1][w-1]
if d == float('inf'):
    print(-1)
    exit()
block = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            block += 1
print(h*w-d-block-1)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(10**6)

H, W = [int(n) for n in input().split(' ')]
S = [list(input()) for i in range(H)]

dist = [[-1]*W for i in range(H)]
dist[0][0] = 1
Q = deque([])
Q.append([0,0])
while Q:
    y, x = Q.popleft()
    if [y, x] == [H-1, W-1]:
        break
    for i, j in [[1,0], [-1,0], [0,1], [0,-1]]:
        if y+i<0 or x+j<0 or y+i>=H or x+j>=W:
            continue
        if dist[y+i][x+j]==-1 and S[y+i][x+j]==".":
            dist[y+i][x+j] = dist[y][x] + 1
            Q.append([y+i, x+j])
if dist[H-1][W-1]==-1:
    print(-1)
else:
    white = 0
    for i in range(H):
        for j in range(W):
            if S[i][j]==".":
                white += 1
    print(white-dist[H-1][W-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):
    ans+=maze[i].count('.')

for i in range(h):
    maze[i]=['#']+maze[i]+['#']
maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]
# 迷路　BFS
import collections
from collections import deque
def clear_maze(sx, sy, gx, gy):

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

        while len(d):
            x, y = d.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  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    d.appendleft ((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

        return distance[gx][gy]

    return bfs()
v=clear_maze(1,1,h,w)

if v==-10**9:
    print(-1)
else:
    print(ans-v-1)

Submission status: Accepted

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def bfs(point, field, target, H, W):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    visited[point[0]][point[1]] = 1
    que = deque()
    que.append(point)

    while True:
        v = que.popleft()
        depth = visited[v[0]][v[1]]
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and visited[a[0]][a[1]] == -1:
                visited[a[0]][a[1]] = 1 + depth
                if a == target:
                    return visited[a[0]][a[1]]
                else:
                    que.append(a)
        if len(que) == 0:
            return 0

def main():
    H, W = list(map(int, input().split()))
    target = (H, W)
    field = [[-1] * (W+2)]
    number_of_whites = 0
    for _ in range(H):
        s = input()
        number_of_whites += s.count('.')
        field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
    field += [[-1] * (W+2)]

    shortest_path = bfs((1, 1), field, target, H, W)
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def bfs(point, field, target, H, W):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    visited[point[0]][point[1]] = 1
    que = deque()
    que.append(point)

    while True:
        v = que.popleft()
        depth = visited[v[0]][v[1]]
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and visited[a[0]][a[1]] == -1:
                visited[a[0]][a[1]] = 1 + depth
                if a == target:
                    return visited[a[0]][a[1]]
                else:
                    que.append(a)
        if len(que) == 0:
            return 0

H, W = list(map(int, input().split()))
target = (H, W)
field = [[-1] * (W+2)]
number_of_whites = 0
for _ in range(H):
    s = input()
    number_of_whites += s.count('.')
    field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
field += [[-1] * (W+2)]

shortest_path = bfs((1, 1), field, target, H, W)
if shortest_path > 0:
    print(number_of_whites - shortest_path)
else:
    print(-1)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>0 else -1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[inf]*(w+1) for _ in range(h+1)]
    que = deque()
    que.append((0,0))
    d[0][0] = 0

    while que:
        cx,cy = que.popleft()
        if cx == w and cy == h:
            break
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            nx, ny = cx+dx, cy+dy
            if 0 <= nx <= h and 0 <= ny <= w and s[nx][ny] != "#" and d[nx][ny] == inf:
                que.append((nx,ny))
                d[nx][ny] = d[cx][cy] + 1
    return d[h][w]

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
inf = float("inf")
h,w = h-1,w-1
cnt = bfs()
dot = 0
for i in s:
    dot += i.count(".")
if 0 < cnt < inf:
  print(dot-cnt-1)
else:
  print(-1)

Submission status: Accepted

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

    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    f_inf = float('inf')
    maze = [[f_inf] * w for _ in range(h)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        y, x = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_y, next_x = y + i, x + j
            if -1 < next_y < h and -1 < next_x < w:
                if grid[next_y][next_x] != "#":
                    if maze[next_y][next_x] > maze[y][x] + 1:
                        maze[next_y][next_x] = maze[y][x] + 1
                        que.append([next_y, next_x])

    if maze[h - 1][w - 1] != f_inf:
        res = h * w - (maze[h - 1][w - 1] + 1)
        for i in range(h):
            for j in range(w):
                if grid[i][j] == "#":
                    res -= 1
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=1
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("#")
print(h*w-black-D[h][w] if D[h][w]!=inf else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("#")
print(h*w-(black+D[h][w]+1) if D[h][w]!=inf else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("#")
print(h*w-black-D[h][w]-1 if D[h][w]!=inf else -1)

Submission status: Accepted

Solution code:
#bfs
def bfs(s,sx,sy,gx,gy):
    from collections import deque
    inf = float("inf")
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[inf for _ in  range(w)] for _ in  range(h)]
    que = deque()
    que.append([sx,sy])
    d[sx][sy] = 1
    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 < h and 0 <= ny < w and s[nx][ny] == '.' and d[nx][ny] == inf:
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

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

cnt = 0
for i in s:
    for j in i:
        if j == ".":
            cnt+=1

ans = bfs(s,0,0,h - 1,w - 1)
if ans==float("inf"):
    print(-1)
else:
    print(cnt - ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
h,w = mi()
a = [list(input()) for _ in range(h)]
b = [[-1]*w for i in range(h)]
from collections import deque
l=deque()
l.append((0,0))
b[0][0]=1
y_drct = [-1,0,1,0]
x_drct = [0,1,0,-1]
default_white = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            default_white +=1
while len(l)>0:
    cy,cx = l.popleft()
    if cy==h-1 and cx==w-1:
        break
    for i in range(4):
        ny=cy+y_drct[i]
        nx=cx+x_drct[i]
        if 0<=ny<h and 0<=nx<w:
            if a[ny][nx] == '.' and b[ny][nx]==-1:
                l.append((ny,nx))
                b[ny][nx]=b[cy][cx]+1

if b[h-1][w-1] == -1:
    print(-1)
else:
    print(default_white-b[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque
r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
w_c = 0
for i in range(r):
    for j in range(c):
        if s[i][j] == '.':
            w_c += 1
            for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
                if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                    if s[i+y][j+x] == '.':
                        G[i*c+j].append((i+y)*c+j+x)


# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
# print(G)
dist = [-1]*N
que = deque([sy*c+sx])
dist[sy*c+sx] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
if dist[gy*c+gx] == -1:
    print(-1)
else:
    print(w_c-dist[gy*c+gx]-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
M=[input() for _ in range(H)]
D=[[10**5]*W for _ in range(H)]

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

visited=[[0]*W for _ in range(H)]
q=deque([[0,0,0]])

while q:
    x,y,dist=q.popleft()
    if visited[x][y]==1:
        continue
    visited[x][y]=1
    D[x][y]=dist
    
    for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
        if x+i>=H or y+j>=W or x+i<0 or y+j<0:
            continue
        if M[x+i][y+j]=='#':
            continue
        q.append([x+i,y+j,dist+1])
if D[H-1][W-1]==10**5:
    print(-1)
else:
    print((H*W-1-D[H-1][W-1])-cnt)

Submission status: Accepted

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

ex = [[0] * w for i in range(h)]

ex[0][0] = 1
do = [[0,0]]
check = [[1,0],[-1,0],[0,1],[0,-1]]

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




while(len(do)!=0):
  x,y = do.pop(0)

  
  for i,j in check:
    a = x + i
    b = y + j
    if(-1<a<h and -1<b<w):
      if(a == h-1 and b == w-1):
        print(white-(ex[x][y])-1)
        exit()
      elif(ex[a][b] == 0 and s[a][b] =='.'):
        ex[a][b] = ex[x][y] +1
        do.append([a,b])
print(-1)

Submission status: Accepted

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

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

def bfs():
    log=[[0 for _ in range(W)] for _ in range(H)]
    queue=deque([[0,0]])
    while queue:
        y,x = queue.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            next_y,next_x = y+j, x+k

            if 0 > next_y or next_y >= H or 0 > next_x or next_x >= W:
                continue
            elif log[next_y][next_x] == 0 and \
                maze[next_y][next_x] != '#':
                log[next_y][next_x] = log[y][x] + 1
                queue.append([next_y,next_x])
    
    return log[H-1][W-1]

min_wh = bfs()

if min_wh == 0:
    print('-1')
    sys.exit()

ans = (W*H - min_wh - 1) - bl_cnt

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = [['#'] * (w+2)]
cou = 0
for i in range(h):
    a = ['#'] + list(input()) + ['#']
    maze.append(a)
x = ['#'] * (w+2)
maze.append(x)

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

ng = True
pos = [[1, 1, 0]]
checklist = [[0] * (w+2) for _ in range(h+2)]
while len(pos) > 0:
    x, y, depth = pos.pop(0)
    if ([x, y] == [h, w]) & (maze[x][y] != '#'):
        ans = h * w - cou - depth - 1
        #print(cou)
        #print(depth)
        print(ans)
        ng = False
        break
    maze[x][y] = 'f'

    if (maze[x+1][y] == '.') & (checklist[x+1][y] == 0):
        pos.append([x+1, y, depth+1])
        checklist[x+1][y] = 1
    if (maze[x][y+1] == '.') & (checklist[x][y+1] == 0):
        pos.append([x, y+1, depth+1])
        checklist[x][y+1] = 1
    if (maze[x-1][y] == '.') & (checklist[x-1][y] == 0):
        pos.append([x-1, y, depth+1])
        checklist[x-1][y] = 1
    if (maze[x][y-1] == '.') & (checklist[x][y-1] == 0):
        pos.append([x, y-1, depth+1])
        checklist[x][y-1] = 1
    #print(pos)
    #print(maze)


if (len(pos) == 0) & ng:
    print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]
grid = ["#"*(W+2)]
for i in range(H):
    grid.append("#"+input()+"#")
grid.append("#"*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if grid[h][w] == ".":
            ans += 1

visited = [[False for i in range(W+2)] for i in range(H+2)]

visit_p = deque()
visit_p.append((1, 1, 0))
cnt = 0

f = False

while visit_p:
    nh, nw, num = visit_p.popleft()

    for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:

        if not (0 < nh+dh < H+2) or not (0 < nw+dw < W+2):
            # 範囲外
            continue

        if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '#':
            # 壁または訪問済み
            continue

        visit_p.append((nh+dh, nw+dw, num+1))
        visited[nh+dh][nw+dw] = True

        if nh+dh == H and nw+dw == W:
            cnt = num + 2
            f = True
            break
    else:
        continue
    break

if f:
    ans -= cnt
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in que:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)

Submission status: Accepted

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

dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1

q = [(0, 0)]
while q:
    nq = []
    while q:
        y, x = q.pop()
        t = dp[y][x] + 1
        if y < H - 1:
            if s[y + 1][x] == '.' and dp[y + 1][x] > t:
                dp[y + 1][x] = t
                nq.append((y + 1, x))
        if y > 0:
            if s[y - 1][x] == '.' and dp[y - 1][x] > t:
                dp[y - 1][x] = t
                nq.append((y - 1, x))
        if x < W - 1:
            if s[y][x + 1] == '.' and dp[y][x + 1] > t:
                dp[y][x + 1] = t
                nq.append((y, x + 1))
        if x > 0:
            if s[y][x - 1] == '.' and dp[y][x - 1] > t:
                dp[y][x - 1] = t
                nq.append((y, x - 1))
    q = nq

if dp[H - 1][W - 1] == 2501:
    print(-1)
else:
    print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [[c for c in input()] for _ in range(H)]
a = sum([S[y][x] == "." for x in range(W) for y in range(H)])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
B = [[-1]*W for _ in range(H)]
q = deque([(0, 0, 1)])  # y,x,step
while len(q) > 0:
    y, x, step = q.popleft()
    if y < 0 or H <= y or x < 0 or W <= x:
        continue
    if S[y][x] == '#' or B[y][x] >= 0:
        continue

    B[y][x] = step

    for i in range(4):
        q.append((y+dy[i], x+dx[i], step+1))
# print(*B, sep='\n')
print(a - B[H-1][W-1] if B[H-1][W-1] >= 0 else -1)

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]
gy, gx = H-1, W-1
maze[0][0]=1

blackTiles = 0
for i in range(H):
  for j in range(W):
    if maze[i][j]=="#":
      blackTiles += 1
      
que = deque([[0,0]])
patterns = [[1,0],[-1,0],[0,1],[0,-1]]
flag = False
while que:
  now = que.popleft()
  nowY = now[0]
  nowX = now[1]
  nowStep = maze[nowY][nowX]
  if nowY == gy and nowX == gx:
    ret = nowStep
    flag = True
    break
  for pattern in patterns:
    nextY = nowY + pattern[0]
    nextX = nowX + pattern[1]
    nextStep = nowStep + 1
    if 0 <= nextY < H and 0<= nextX < W and maze[nextY][nextX]==".":
      maze[nextY][nextX] = nextStep
      que.append([nextY,nextX])
if flag:
  print(H*W-ret-blackTiles)
else:
  print(-1)

Submission status: Accepted

Solution code:
#088_D
import queue
h, w = map(int, input().split())
inf = 10 ** 5
s = [input() for _ in range(h)]
d = [[inf]*w for _ in range(h)]

que = queue.Queue()
que.put((0, 0))
d[0][0] = 0
while not que.empty():
    qx, qy = que.get()
    if qx == h-1 and qy == w-1:
        break
        
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        px, py = qx+dx, qy+dy
        if 0 <= px < h and 0<= py < w:
            if s[px][py] == '#':
                continue
            elif d[px][py] != inf:
                continue
            d[px][py] = d[qx][qy] + 1
            que.put((px, py))
            
if d[h-1][w-1] == inf:
    print(-1)
else:
    print(h * w - (d[h-1][w-1]+1) - sum(s[i].count('#') for i in range(h)))

Submission status: Accepted

Solution code:
from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
nokoshi = 1
que = deque([(0, 0)])
done = [[False] * w for _ in range(h)]

white_num = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            white_num += 1

while que:
    for i in range(len(que)):
        y, x = que.popleft()

        if y == h - 1 and x == w - 1:
            print(white_num - nokoshi)
            exit()

        if y < 0 or y >= h or x < 0 or x >= w or field[y][x] == "#" or done[y][x] is True:
            continue
        done[y][x] = True

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    nokoshi += 1
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

INF = float('inf')
path = [[INF] * W for _ in range(H)]
q = deque()

q.append((0, 0, 1))
path[0][0] = 1
isGoal = False
while q:
    x, y, s = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if (nx, ny) == (H - 1, W - 1):
            path[nx][ny] = s + 1
            isGoal = True
            break
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > s + 1:
            q.append((nx, ny, s + 1))
            path[nx][ny] = s + 1
    else:
        continue
    break

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

if isGoal:
    print(cnt - path[H - 1][W - 1])
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque
H, W = map(int, input().split())
areas = []

black_count = 0
for _ in range(H):
    text = list(input().rstrip())
    for char in text:
        if char == '#':
            black_count += 1
    areas.append(text)

# 最短経路探索でかかったコストを使えば、コストが計算できる。全てのますの数から、最初から黒に塗られているを引いて、さらに最短コストを引けば良い
# 0,0からH,wへ行く


def bfs(areas, start_point, goal_point):
    scores = [[10**9 + 7 for _ in range(W)] for _ in range(H)]
    scores[0][0] = 1
    mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        for next_postion in mv:
            next_point = [now_point[0] + next_postion[0],
                          now_point[1] + next_postion[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '#':
                    continue
                if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    if scores[goal_point[0]][goal_point[1]] == 10**9 + 7:
        return -1
    return scores[goal_point[0]][goal_point[1]]


cost = bfs(areas, [0, 0], [H - 1, W - 1])
if cost == -1:
    print(cost)
else:
    print(H * W - black_count - cost)