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 heapq import heappop, heappush

H, W = map(int, sys.stdin.readline().split())
grid = ['#' * (W + 2)]
grid += ['#' + sys.stdin.readline().rstrip() + '#' for _ in range(H)]
grid += ['#' * (W + 2)]

def heuristic_cost(y, x):
    return abs(H - y) + abs(W - x)

def main():
    h = heuristic_cost(1, 1)
    c = 0
    s = h + c
    hq = [(s, c, 1, 1)]
    nex = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    cost = [[None] * (W+1) for _ in range(H+1)]
    while hq:
        s, c, y, x = heappop(hq)
        if not cost[y][x] is None:
            continue
        cost[y][x] = c
        for dy, dx in nex:
            i = y + dy
            j = x + dx
            if grid[i][j] == '.' and cost[i][j] is None:
                h = heuristic_cost(i, j)
                s = h + (c + 1)
                heappush(hq, (s, c+1, i, j))

    white_cnt = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            white_cnt += (grid[i][j] == '.') & 1
    
    ans = white_cnt - (cost[H][W] + 1) if not cost[H][W] is None else -1
    return ans 

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

Submission status: Accepted

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

white=sum([1 if s[y][x]=='.' else 0 for x in range(W) for y in range(H)])
used=[[False for x in range(W)] for y in range(H)]
q=Queue()
q.put((0,0,1))
while True:
    if q.empty():
        print(-1)
        break
    x,y,l=q.get()
    if used[y][x]:
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    used[y][x]=True
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx=x+d[0]
        ny=y+d[1]
        if ny>=0 and ny<H and nx>=0 and nx<W:
            if s[ny][nx]=='.':
                q.put((nx,ny,l+1))

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    p_black = 0
    maze = [[3000 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == '#':
                maze[i][j] = -1
                p_black += 1
    maze[0][0] = 0
    
    move = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    que = deque([[0, 0]])
    white = 1
    while que:
        cy, cx = que.popleft()
        if cy == H - 1 and cx == W - 1:
            white += maze[H - 1][W - 1]
            break
        
        for i in range(4):
            ny = cy + move[i][0]
            nx = cx + move[i][1]
            if 0 <= ny <= H - 1 and 0 <= nx <= W - 1:
                if maze[ny][nx] == 3000:
                    maze[ny][nx] = maze[cy][cx] + 1
                    que.append([ny, nx])
    
    if white == 1:
        print(-1)
    else:
        ans = H * W - p_black - white
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False

def result():
    cnt = 0
    for j in range(W):
        for i in range(H):
            if s_tmp[i][j] =='.':
                cnt += 1
    if flg == False:
        print(-1)
    else :
        print(cnt-z-2)
        
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    #print(z+1)
                    flg = True
                    result()
                    sys.exit()
                s[ny][nx] = 'y'
if flg == False:
        print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    s=[[] for _ in range(H+2)]
    s[0]=s[H+1]=['#']*(W+2)
    white=-1
    for i in range(1,H+1):
        row=['#']+list(input())+['#']
        s[i]=row
        for cell in row:
            if cell=='.':
                white+=1
    queue=deque()
    queue.append([1,1])
    d=[[INF]*(W+2) for _ in range(H+2)]
    d[1][1]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while queue:
        cell=queue.popleft()
        for k in range(4):
            if s[cell[0]+dx[k]][cell[1]+dy[k]]=='.' and d[cell[0]+dx[k]][cell[1]+dy[k]]==INF:
                queue.append([cell[0]+dx[k],cell[1]+dy[k]])
                d[cell[0]+dx[k]][cell[1]+dy[k]]=min(d[cell[0]+dx[k]][cell[1]+dy[k]],d[cell[0]][cell[1]]+1)
    if d[H][W]==INF:
        print(-1)
    else:
        print(white-d[H][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]

import sys
from collections import deque

moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
H, W = fetch_int_input()
maze = [list(fetch_one_line()) for _ in range(H)]
X, Y = 0, 1
STARTS = (0, 0)
GOALS = (H - 1, W - 1)


def count_wall(maze, wall="#"):
    wall_num = 0
    for one_line in maze:
        wall_num += "".join(one_line).count(wall)
    return wall_num

def bfs():
    que = deque()
    d = [[sys.maxsize for _ in range(W)] for _ in range(H)]
    que.append(STARTS)
    d[STARTS[X]][STARTS[Y]] = 0

    while que:
        now_pos = que.popleft()
        if now_pos == GOALS:
            break
        for move in moves:
            np = (now_pos[X] + move[X], now_pos[Y] + move[Y])
            if np[X] >= 0 and np[Y] >= 0 and np[X] < H and np[Y] < W and maze[np[X]][np[Y]] == '.' and d[np[X]][np[Y]] == sys.maxsize:
                que.append(np)
                d[np[X]][np[Y]] = d[now_pos[X]][now_pos[Y]] + 1

    return d[GOALS[X]][GOALS[Y]]

min_distance = bfs()
if min_distance == sys.maxsize:
    changable_num = -1
else:
    wall_num = count_wall(maze, "#")
    changable_num = H * W - 2 - (min_distance - 1) - wall_num
print(changable_num)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '#', str, space=False, padding=True)

# グリッドBFS
directions = ((1,0),(-1,0),(0,1),(0,-1))
que = deque([(1, 1, 0)])
dist = list2d(H+2, W+2, INF)
while que:
    h, w, c = que.popleft()
    if dist[h][w] != INF:
        continue
    dist[h][w] = c
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if grid[h2][w2] == '#':
            continue
        que.append((h2, w2, c+1))

# ゴール到達不可
if dist[H][W] == INF:
    print(-1)
    exit()

# 白マスをカウント
cnt = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] == '.':
            cnt += 1
# 最短経路で通るマスの分を引く
ans = cnt - (dist[H][W] + 1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '#', str, space=False, padding=True)

# グリッドBFS
directions = ((1,0),(-1,0),(0,1),(0,-1))
que = deque([(1, 1, 0)])
dist = list2d(H+2, W+2, INF)
while que:
    h, w, c = que.popleft()
    if dist[h][w] != INF:
        continue
    dist[h][w] = c
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if grid[h2][w2] == '#':
            continue
        que.append((h2, w2, c+1))

# ゴール到達不可
if dist[H][W] == INF:
    print(-1)
    exit()

# 経路復元
que = deque([(H, W)])
while que:
    h, w = que.popleft()
    grid[h][w] = '@'
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if dist[h2][w2] == dist[h][w] - 1:
            que.append((h2, w2))
            break

# 最短経路で通る場所以外をカウント
ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] == '.':
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
s_y, s_x = (0, 0)
g_y, g_x = (H-1, W-1)

c = [input() for a in range(H)]

d = [[ sys.maxsize for b in range(W)] for a in range(H)]

blackcount = 0
for y in range(H):
  blackcount += c[y].count('#')

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

q = deque([[s_y, s_x]])

d[s_y][s_x] = 0

while len(q) > 0:
  y, x = q.popleft()
  if y==g_y and x==g_x:
    print(H * W - blackcount - 1 - d[y][x])
    exit()
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and c[ny][nx] == '.' and d[ny][nx] == sys.maxsize:
      q.append([ny, nx])
      d[ny][nx] = d[y][x]+1
      
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
mat = []
wsum = 0
for i in range(H):
    mat.append(list(input()))
    wsum += mat[i].count('.')
start = [0,0]
x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
alr = [[-1 for i in range(W)] for j in range(H)]
alr[0][0] = 0
que = deque()
count = 0
que.append([0,0])
flag = False
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if q[0]+x1[i] == H-1 and q[1]+y1[i] == W-1:
                count = alr[q[0]][q[1]] + 1
                flag = True
                que.clear()
            elif mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                que.append([q[0]+x1[i],q[1]+y1[i]])
if flag:
    print(wsum - (count+1))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
 
def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                maze[new_y][new_x] == "." and   \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
 
    return -1
 

def main():
    sharp = 0
 
    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]
 
    for k in range(H):
        sharp += maze[k].count('#')
 
    print(bfs(H, W, maze, visited, sharp))
 
main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                maze[new_y][new_x] == "." and   \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

    return -1












def main():
    sharp = 0

    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]

    for k in range(H):
        sharp += maze[k].count('#')

    print(bfs(H, W, maze, visited, sharp))

main()

Submission status: Accepted

Solution code:
import copy
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    walled_maze = copy.copy(maze)
    walled_maze[H:H] = [''.join(['#' for _ in range(W+2)])]
    walled_maze[0:0] = [''.join(['#' for _ in range(W+2)])]
    for row_num in range(1, H+1):
        walled_maze[row_num] = '#{}#'.format(walled_maze[row_num])
    # for i in range(H+2):
    #     print(walled_maze[i])

    stack = deque()
    sx, sy = 1, 1
    gx, gy = H, W
    distances = [[-1]*(W+2) for _ in range(H+2)]
    vectors = ((1, 0), (-1, 0), (0, 1), (0, -1))

    distances[sx][sy] = 0
    for vec_x, vec_y in vectors:
        x = sx + vec_x
        y = sy + vec_y
        stack.append((x, y))
        distances[x][y] = float('inf')

    min_path_dist = -1
    while len(stack):
        x, y = stack.popleft()
        if x < 0 or x >= H+1 or y < 0 or y >= W+1 or walled_maze[x][y] == '#':
            continue
        for vec_x, vec_y in vectors:
            try:
                next_x = x + vec_x
                next_y = y + vec_y
                if distances[next_x][next_y] < 0:
                    stack.append((next_x, next_y))
                    distances[next_x][next_y] = float('inf')
                else:
                    if distances[x][y] > distances[next_x][next_y] + 1:
                        distances[x][y] = distances[next_x][next_y] + 1
            except IndexError:
                pass

        # print('{} {}'.format(x, y))
        # print(stack)
        # for i in range(H+2):
        #     print(distances[i])

        if x == gx and y == gy:
            min_path_dist = distances[x][y]
            break

    if min_path_dist < 0:
        print('-1')
    else:
        black_square_num = sum([row.count('#') for row in maze])
        print(H*W-(min_path_dist+1)-black_square_num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Y,X=map(int,input().split())
info=[]
come=[[0]*X for i in range(Y)]
num=[[0]*X for i in range(Y)]
bl=0 # #の数
come[0][0]=1
for i in range(Y):
    a=list(input())
    info.append(a)
    for j in range(X):
        if a[j]=="#":
            bl+=1
def bfs(y,x,nanpo):
    if not(0<=y<=(Y-1) and 0<=x<=(X-1)):
        return
    if info[y][x]=="#":
        return
    if come[y][x]==1:
        return
    come[y][x]=1
    num[y][x]=nanpo
    next_.append([y,x])
    
next_=[[0,0]]
l=1
nanpo=1
while l>0:
    for i in range(l):
        #print(i)
        #print(next_)
        bfs(next_[0][0]+1,next_[0][1],nanpo)
        bfs(next_[0][0]-1,next_[0][1],nanpo)
        bfs(next_[0][0],next_[0][1]+1,nanpo)
        bfs(next_[0][0],next_[0][1]-1,nanpo)
        del next_[0]
    nanpo+=1
    l=len(next_)
#print(num)
if come[Y-1][X-1]==0:
    print(-1)
else:
    print(X*Y-bl-(num[Y-1][X-1]+1))
#print(bl)

Submission status: Accepted

Solution code:
import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(field,visited,sy,sx,gy,gx):
    queue = deque([[sy,sx]])
    visited[sy][sx] = 0
    while queue:
        y,x = queue.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
 
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            if new_y < 0 or new_y > gy or new_x < 0 or new_x > gx:
              continue
            if field[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                
if __name__ == "__main__":
 
    h,w=map(int,input().split())
    sy=1
    sx=1
    field=[list(input()) for i in range(h)]
    visited = [[-1]*w for i in range(h)]
    sy, sx, gy, gx = sy-1, sx-1, h-1, w-1
    ans=bfs(field,visited,sy,sx,gy,gx)
    #print(ans)
    cnt=0
    for i in range(h):
      for j in range(w):
        if field[i][j]==".":
          cnt+=1
    if ans == None:
      print(-1)
    else:
      print(cnt - ans -1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(H,W,G):
    d  = [[-1] * W for i in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = deque([])
    q.append((0,0))
    d[0][0] = 0

    while(len(q) != 0):
        x,y = q.popleft()

        if(x == (H-1) & y == (W-1)):
            break

        for i in range(4):
            nx , ny = x + dx[i] , y + dy[i]

            if (0 <= nx and nx <= (H-1) and 0<= ny and ny <= (W-1) and G[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return d


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

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            G[i][j] = 1

d = bfs(H,W,G)
point = -1

if d[H-1][W-1] != -1:
    point = H * W - sum(map(sum,G)) - d[H-1][W-1] -1

print(point)

Submission status: Accepted

Solution code:
height, width = map(int, input().split(" "))
grids = list()
grids_accessed = list()
whites = 0
for h in range(height):
    inputted = input()
    whites += inputted.count(".")
    grids.append(list(inputted))
    grids_accessed.append([False]*len(inputted))


def get_next(x, y):
    nexts = ((x-1, y),
             (x+1, y),
             (x, y-1),
             (x, y+1))
    for x, y in nexts:
        if (0 <= x <= width-1) and (0 <= y <= height-1):
            if grids[y][x] == ".":
                yield x, y


def dfs():
    queue = list()
    x, y = 0, 0
    queue.append((x, y))
    while True:
        try:
            x, y = queue.pop(0)
        except IndexError:
            return
        if x == width-1 and y == height-1:
            return
        for n_x, n_y in get_next(x, y):
            if grids_accessed[n_y][n_x] is False:
                grids_accessed[n_y][n_x] = (x, y)
                queue.append((n_x, n_y))


def get_shortest():
    x, y = width-1, height-1
    distance_traveled = 0
    while True:
        if x == 0 and y == 0:
            return distance_traveled
        else:
            x, y = grids_accessed[y][x]
            distance_traveled += 1


dfs()
if grids_accessed[height-1][width-1] is False:
    print(-1)
else:
    d = get_shortest() + 1
    score = whites - d
    if score < 0:
        score = -1
    print(score)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import copy
import math
#--------Pypy3---------
#from fractions import gcd
#--------Python3---------
#from math import gcd
#----------Recursion------------
sys.setrecursionlimit(10**9)

num = 10**8
d = [(1,0),(-1,0),(0,1),(0,-1)]
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
visited=[[0 for _ in range(W)]for _ in range(H)]
def bfs(maze,visited,x,y):
    queue = deque()
    queue.append([0,0])
    visited[x][y] = 1
    while queue:
        x,y = queue.popleft()
        if x == H-1 and y == W-1:
            return visited[x][y]
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W:
                if maze[nx][ny] == "." and visited[nx][ny] == 0:
                    visited[nx][ny]=visited[x][y]+1
                    queue.append([nx,ny])
    return -1
def main():
    """code here"""
    cnt = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j]==".":
                cnt+=1
    ans = bfs(maze,visited,0,0)
    if ans == -1:
        print(-1)
        exit()

    print(cnt-ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
w_cnt = 0
for i in range(H):
    w_cnt += grid[i].count('.')


inf = float('inf')
d = [[inf]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


d[0][0] = 0
que = deque()
que.append([0,0])
while len(que) != 0:
    p = que.popleft()
    if p[0] == W-1 and p[1] == H-1:break
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == inf:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
if d[H-1][W-1] == inf:
    print(-1)
else:
    print(w_cnt-d[H-1][W-1]-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = list(list(input())for i in range(h))
cntng = 0
for i in range(h):
    cntng+= s[i].count("#")


start = (0,0) 
goal = (h-1,w-1)
vec = ((1,0),(0,1),(-1,0),(0,-1))

stack = [start]
move = 0

while stack:
    next = []
    move+=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            
            if ty>h-1 or tx>w-1 or ty<0 or tx<0:continue
            if s[ty][tx] == ".":
                s[ty][tx] = move
                next.append((ty,tx))
    stack = next
         
    stack = next
    if goal in stack:
        break
if s[h-1][w-1]== ".":
    print(-1)
    exit(0)
ans = max(0,h*w - (move+1)-cntng)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int,input().split())
maze = [input() for i in range(H)]
visit = [[-1]*W for i in range(H)]
x, y = 0, 0
cnt = 0
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      cnt += 1
def bfs(maze, visit, x, y):
  queue = deque()
  queue.append([0, 0])
  visit[y][x] = 0
  while queue:
    y, x = queue.popleft()
    if y == H-1 and x == W-1:
      return cnt-visit[y][x]-1
    for i, j in [[1,0],[-1,0],[0,1],[0,-1]]:
      nextx, nexty = x+i, y+j
      if nextx<0 or nextx>=W or nexty<0 or nexty>=H:
        continue
      elif maze[nexty][nextx] != "#" and visit[nexty][nextx] == -1:
        visit[nexty][nextx] = visit[y][x] + 1
        queue.append([nexty,nextx])
  return -1
print(bfs(maze,visit,x,y))

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([(0, 0, 1)])

while q:
  h, w, c = q.popleft()
  if s[h][w] != ".": continue
  s[h][w] = c
  if h+1 == H and w+1 == W: break
  if 0 <= h-1: q.append((h-1, w, c+1))
  if h+1 < H : q.append((h+1, w, c+1))
  if 0 <= w-1: q.append((h, w-1, c+1))
  if w+1 < W : q.append((h, w+1, c+1))
else:
  print(-1)
  exit()

print(H*W - sum([sum([x == "#" for x in sh]) for sh in s]) - s[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np
temp=list(map(int, input().split()))
H=temp[0]
W=temp[1]

s=(0,0)
g=(H-1,W-1)

c=np.zeros((H,W)).astype(int)

for i in range(H):
  temp=input()
  a=np.zeros(W).astype(int)
  for j in range(W):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  c[i]=a
n_black=int(np.sum(c))
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<H and v[1]>=0 and v[1]<W:
        adj.append(v)
  return adj  

color=np.zeros((H,W)).astype(int)
d=np.zeros((H,W)).astype(int)-1
d[s[0],s[1]]=0
def BFS():
  Q=[s]
  while Q !=[]:
    u=Q[0]
    if g==u:
      print(H*W-n_black-(d[u[0],u[1]]+1))
      return
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0 and color[v[0],v[1]]==0:
        color[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  print(-1)
BFS()

Submission status: Accepted

Solution code:
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)
gy = H - 1
gx = W - 1

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    queue.append([sy,sx])
    while queue:
        now = queue.popleft()
        if now == [gy, gx]:
            return visited[gy][gx]
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1]+ x[_]
            if 0 < nx < W and 0 < ny < H: 
                if lst[ny][nx] != "X" and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
                    print(now, [gy, gx], visited[ny][nx])
    return -1

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    queue.append([sy,sx])
    while queue:
        now = queue.popleft()
        if now == [gy, gx]:
            return visited[gy][gx]
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1]+ x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if lst[ny][nx] != "#" and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
    return -1

step = bfs(0,0, gy, gx)
if step == -1:
    print(step)
else:
    ans = H * W -  sum([_.count('#') for _ in lst]) - (step + 1)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
c=[['#']*(W+2)]
ten=0
for i in range(H):
    ip=list(input())
    ten+=ip.count('.')
    c.append(['#']+ip+['#'])
c.append(['#']*(W+2))
Q=deque([[1,1,1]])

def move(yxc):
    global Q,c
    y,x,cost=yxc[0],yxc[1],yxc[2]
    if c[y+1][x]=='.':
        c[y+1][x]=cost+1
        Q.append([y+1,x,cost+1])
    if c[y-1][x]=='.':
        c[y-1][x]=cost+1
        Q.append([y-1,x,cost+1])
    if c[y][x+1]=='.':
        c[y][x+1]=cost+1
        Q.append([y,x+1,cost+1])
    if c[y][x-1]=='.':
        c[y][x-1]=cost+1
        Q.append([y,x-1,cost+1])

c[1][1]=1
while len(Q)>0:
    move(Q.popleft())

goal=c[H][W]
if goal=='.' or goal=='#':
    print(-1)
else:
    print(ten-goal)