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

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if 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

    except RuntimeError:
        print(-1)
        sys.exit()


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

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

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)

Submission status: Accepted

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



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    INF = 10000000

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

    d = [[INF]*W for i in range(H)]

    from collections import deque
    q = deque()

    q.appendleft([0,0])
    d[0][0] = 0

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

    while(len(q)):
        i,j = q.pop()

        for di,dj in dx:
            if(0 <= i+di < H and 0 <= j+dj < W and d[i+di][j+dj] == INF and maze[i+di][j+dj] == '.'):
                q.appendleft([i+di,j+dj])
                d[i+di][j+dj] = d[i][j]+1

    # print(d[H-1][W-1])
    if(d[H-1][W-1] == INF):
        print(-1)
    else:
        print(sum([i.count('.') for i in maze]) - d[H-1][W-1] - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):a.append(list(input()))
white=[flatten for inner in a for flatten in inner].count(".")
turn=1
a[-1][-1]=1
while turn in [flatten for inner in a for flatten in inner]:
    for i in range(h):
        for j in range(w):
            if a[i][j]==turn:
                if i>0 and a[i-1][j]==".":a[i-1][j]=turn+1
                if i<h-1 and a[i+1][j]==".":a[i+1][j]=turn+1
                if j>0 and a[i][j-1]==".":a[i][j-1]=turn+1
                if j<w-1 and a[i][j+1]==".":a[i][j+1]=turn+1
    turn+=1
    if a[0][0]!=".":break
print(-1 if a[0][0]=="." else white-a[0][0])

Submission status: Accepted

Solution code:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while True:
        if len(queue) > 0:
            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 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])
        else:
            return -1


H, W = map(int, input().split())
white = 0
s = ['#' * (W + 2)]
for i in range(H):
    s_i = '#' + input() + '#'
    white += s_i.count('.')
    s.append(s_i)
s.append('#' * (W + 2))

visited = [[-1] * (W+2) for i in range(H+2)]
shortest = bfs(s, visited, 1, 1, H, W)
if shortest > 0:
    print(white - shortest - 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)]
def repaint(maze,sx,sy):
  maze[sy][sx] = 1 
  que = deque([(sx,sy)])
  dxdy = [(1,0),(0,1),(-1,0),(0,-1)]
  while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
      if 0<=x+dx<w and 0<=y+dy<h and maze[y+dy][x+dx] == ".":
        maze[y+dy][x+dx] = maze[y][x] + 1
        que.append((x+dx,y+dy))
  return True
white = 0
for x in maze:
  white += x.count(".")
repaint(maze,0,0)
if maze[h-1][w-1] == ".":
  print(-1)
else:
  print(white-maze[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque
import sys


def input():
    return sys.stdin.readline()[:-1]


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

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

board = [list(input().strip()) for _ in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]

q = deque([])
q.append([sy, sx, 0])
is_reach = False

while q:
    y, x, z = q.popleft()
    if y == gy and x == gx:
        is_reach = True
        break
    if (not 0 <= y < H) or (not 0 <= x < W):
        continue
    if board[y][x] == "." and visited[y][x] == 0:
        q.append([y+1, x, z+1])
        q.append([y, x+1, z+1])
        q.append([y-1, x, z+1])
        q.append([y, x-1, z+1])
        visited[y][x] = 1

if is_reach:
    num_white = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == ".":
                num_white += 1
    print(num_white-z-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from queue import Queue


def main(h, w, a):
    visited = [[False] * w for _ in range(h)]
    visited[0][0] = True
    #print(visited)
    cur = [[0, 0]]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    cnt = 0
    dis = -1
    while len(cur) > 0:
        cnt += 1
        nex = []
        for pos in cur:
            for i in range(4):
                tx = pos[0] + dx[i]
                ty = pos[1] + dy[i]
                #print(tx, ty)
                if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '#' and  not visited[ty][tx]:
                    if tx == w - 1 and ty == h - 1:
                        dis = cnt
                    nex.append([tx, ty])
                    visited[ty][tx] = True
        #print(cur)
        #print(nex)
        cur = nex
    if dis < 0:
        print(-1)
        return
    tmp = 0
    for R in a:
        for c in R:
            if c == '#':
                tmp += 1
    ret = h * w - tmp - dis - 1
    print(ret)
    return

if __name__ == '__main__':
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    main(h, w, a)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
start = (0, 0)
goal = (H-1, W-1)
S = [start]
T = {start: 1}
while S and goal not in T:
    S2 = []
    for x, y in S:
        for pos in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            x2, y2 = pos
            if 0<= x2 <= H-1 and 0<= y2 <= W-1:
                if g[x2][y2] != '#' and pos not in T:
                    T[pos] = T[(x, y)] + 1
                    S2.append(pos)
    S = S2
if goal not in T:
    print(-1)
else:
    print(white - T[goal])

Submission status: Accepted

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

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

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

d = [[0 for i in range(w)] for i in range(h)] # 最小距離

from queue import Queue

q = Queue()

# 初期化
for i in range(h):
    for j in range(w):
        d[i][j] = float('inf')

q.put((0, 0))
d[start[0]][start[1]] = 0

# queueが空になるまでループ
while q.qsize():
    # キューの先頭
    p = q.get()

    # ゴールに到着したら終了
    if p[0] == goal[0] and [1] == goal[1]:
        break

    # 移動
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if 0 <= nx and nx < h and 0 <= ny and ny < w:
            if s[nx][ny] == '.' and d[nx][ny] == float('inf'):

                q.put((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

dist = d[goal[0]][goal[1]]
if dist == float('inf'):
    print(-1)
else:
    count_w = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                count_w += 1
    print(count_w - dist - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from collections import deque

input = sys.stdin.readline

def main():
    H, W = [int(e) for e in input().split()]
    S = [0 for _ in range(H)]
    for i in range(H):
        S[i] = list(input())[:W]

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

    dp = [[0 for _ in range(W)] for _ in range(H)]
    enc = [[False for _ in range(W)] for _ in range(H)]

    i = 0
    j = 1

    q = deque([[0, 0]])
    enc[0][0] = True
    dp[0][0] = 1
    while len(q) != 0:
        pos = q.popleft()

        x = pos[0]
        y = pos[1]

        if x+1 != H and S[x+1][y] == "." and not enc[x+1][y]:
            dp[x+1][y] = dp[x][y] + 1
            enc[x+1][y] = True
            q.append([x+1, y])
        if y+1 != W and S[x][y+1] == "." and not enc[x][y+1]:
            dp[x][y+1] = dp[x][y] + 1
            enc[x][y+1] = True
            q.append([x, y+1])
        if x-1 != -1 and S[x-1][y] == "." and not enc[x-1][y]:
            dp[x-1][y] = dp[x][y] + 1
            enc[x-1][y] = True
            q.append([x-1, y])
        if y-1 != -1 and S[x][y-1] == "." and not enc[x][y-1]:
            dp[x][y-1] = dp[x][y] + 1
            enc[x][y-1] = True
            q.append([x, y-1])

    res = w - dp[H-1][W-1]
    print(res if dp[H-1][W-1] != 0 else -1)


main()

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
from itertools import chain

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

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S_initial = deepcopy(S)

    
def bfs():
    S[0][0] = "#"
    dq = deque() ## (y, x, dist from start)
    dq.append((0,0,0))
    while dq:
        y,x,d = dq.popleft()
        if d > H*W:
          break
        for dy,dx in dire:
            ny = y + dy; nx = x + dx
            if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
                continue
            if (ny,nx) == (H-1,W-1):
                return d+1
            if S[ny][nx] == ".":
                dq.append((ny,nx,d+1))
                S[ny][nx] = "#"
    return -1

dist = bfs()
if dist == -1:
  print(-1)
else:
  S_flatten = list(chain.from_iterable(S_initial))
  cnt_dot = S_flatten.count('.') - (dist+1)
  print(cnt_dot)

Submission status: Accepted

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

WHITE = '.'
BLACK = '#'

num_white = 0
for x in range(H):
    for y in range(W):
        if S[x][y] == WHITE:
            num_white += 1

is_reached = False
positions = [(0, 0)]
delta_positions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
S[0][0] = 1

while positions:
    new_positions = []
    for x, y in positions:
        for dx, dy in delta_positions:
            new_x = x + dx
            new_y = y + dy
            if 0 <= new_x and new_x < H and 0 <= new_y and new_y < W:
                if S[new_x][new_y] == WHITE:
                    new_positions.append((new_x, new_y))
                    S[new_x][new_y] = S[x][y] + 1
                    if new_x == H - 1 and new_y == W - 1:
                        is_reached = True
                        break
    positions = new_positions

if is_reached:
    print(num_white - S[H-1][W-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
matrix = [input() for _ in range(H)]
(sy, sx) = (0, 0)
(gy, gx) = (H - 1, W - 1)

dist = [[None for _ in range(W)] for _ in range(H)]

q = deque([(sy, sx)])
dist[sy][sx] = 1

count_dots = 0
for i in range(H):
    count_dots += matrix[i].count(".")

while q:
    cy, cx = q.popleft()
    if (cy, cx) == (gy, gx):
        break

    for (dy, dx) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        ny, nx = cy + dy, cx + dx

        if 0 <= nx < W and 0 <= ny < H and matrix[ny][nx] == ".":
            if dist[ny][nx] is None:
                q.append((ny, nx))
                dist[ny][nx] = dist[cy][cx] + 1

if dist[gy][gx] is None:
    print(-1)
    exit()

print(count_dots - dist[gy][gx])

Submission status: Accepted

Solution code:
# ほぼ最短路を求めるだけ

import heapq as hp
import numpy as np

H,W = map(int,input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.pad(S,1,'constant')
visited = np.zeros_like(S,dtype=np.bool)

dist = np.inf

h = []
hp.heappush(h,(0,1,1))

while h:
  d,x,y = hp.heappop(h)
  if x == H and y == W:
    dist = d
    break
  for dx,dy in [[0,1],[1,0],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    if S[nx,ny] == '.' and not visited[nx,ny]:
      visited[nx,ny] = True
      hp.heappush(h,(d+1,nx,ny))
      
if dist == np.inf:
  print(-1)
else:
  print((S == '.').sum() - dist - 1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
T = [[] for i in range(H)]
b = 0
for i in range(H):
    T[i] = list(input())
    for j in range(W):
        if T[i][j] == '#':
            b += 1

que = [(0, 0, 1)]
while que:
    x, y, k = que.pop(0)
    if x == H - 1 and y == W - 1:
        print(H * W - b - k)
        exit()

    for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
            T[nx][ny] = '#'
            que.append((nx, ny, k + 1))
print(-1)

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    h, w = intin()
    slistlist = ['#' * (w + 2)]
    slistlist.extend(['#' + input() + '#' for _ in range(h)])
    slistlist.append('#' * (w + 2))

    clistlist = []
    for i in range(h + 2):
        clistlist.append([False] * (w + 2))

    white_count = 0
    for slist in slistlist:
        for s in slist:
            if s == '.':
                white_count += 1

    paths = {(1, 1): 1}

    while paths:
        next_paths = defaultdict(lambda: float('inf'))

        for p, c in paths.items():
            if slistlist[p[0]+1][p[1]] == '.' and not clistlist[p[0]+1][p[1]]:
                next_paths[(p[0]+1, p[1])] = min(c + 1, next_paths[(p[0]+1, p[1])])
                clistlist[p[0]+1][p[1]] = True
            if slistlist[p[0]-1][p[1]] == '.' and not clistlist[p[0]-1][p[1]]:
                next_paths[(p[0]-1, p[1])] = min(c + 1, next_paths[(p[0]-1, p[1])])
                clistlist[p[0]-1][p[1]] = True
            if slistlist[p[0]][p[1]+1] == '.' and not clistlist[p[0]][p[1]+1]:
                next_paths[(p[0], p[1]+1)] = min(c + 1, next_paths[(p[0], p[1]+1)])
                clistlist[p[0]][p[1]+1] = True
            if slistlist[p[0]][p[1]-1] == '.' and not clistlist[p[0]][p[1]-1]:
                next_paths[(p[0], p[1]-1)] = min(c + 1, next_paths[(p[0], p[1]-1)])
                clistlist[p[0]][p[1]-1] = True

        paths = next_paths
        if (h, w) in paths:
            print(white_count - paths[(h, w)])
            return

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int,input().split())
S = []
wall = 0
for i in range(H):
    s = list(input())
    wall += s.count("#")
    S.append(s)
q = deque()
q.append([0, 0, 0])
S[0][0] = "#"
while q:
    y, x, cnt = q.popleft()
    if y == H-1 and x == W-1:
        break
    for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and S[y + dy][x + dx] == ".":
            q.append([y + dy, x + dx, cnt + 1])
            S[y + dy][x + dx] = "#"

if S[H-1][W-1] == ".":
    print(-1)
else:
    score = H * W - (cnt + 1) - wall
    print(score)

Submission status: Accepted

Solution code:
R,C = map(int,input().split())

maze = []
for i in range(R):
    maze.append(input())

def bfs(sx,sy,gx,gy):
    queue = []
    queue.append([sx,sy])

    visited = [ [ float("inf") for i in range(C)] for j in range(R)]
    visited[sx][sy] = 0

    while queue:
        p = queue.pop(0)

        if gx == p[0] and gy == p[1]:
            break

        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = p[0] + d[0]
            ny = p[1] + d[1]

            if 0 <= nx and 0 <= ny and nx < R and ny < C and maze[nx][ny] == "." and visited[nx][ny] == float("inf"):
                queue.append([nx,ny])
                visited[nx][ny] = visited[p[0]][p[1]] + 1
    return visited[gx][gy]

k = bfs(0,0,R-1,C-1)
if k == float("inf"):
    print(-1)
    exit()
c = 0
for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            c += 1
print(c - k - 1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
check = [[False]*W for _ in range(H)]
ans = [[0]*W for _ in range(H)]

q = deque()
q.append([0,0])
check[0][0] = True

while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if not check[next_i][next_j] and l[next_i][next_j] != '#':
                q.append([next_i,next_j])
                check[next_i][next_j] = True
                ans[next_i][next_j] = ans[i][j]+1

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

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

Submission status: Accepted

Solution code:


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    start, goal = (0, 0), (high - 1, width - 1)

    now_data = set()
    now_data.add(start)
    next_data = set()
    pre_data = set()
    pre_data.add(start)

    move_tada = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    count = 1
    while len(now_data) > 0:
        if goal in pre_data:
            break
        count += 1
        for now_x, now_y in now_data:
            for add_x, add_y in move_tada:
                move_x, move_y = now_x + add_x, now_y + add_y
                if 0 <= move_x < high and 0 <= move_y < width:
                    if data[move_x][move_y] == '.' and (move_x, move_y) not in pre_data:
                        ok_data = (move_x, move_y)
                        pre_data.add(ok_data)
                        next_data.add(ok_data)
        now_data = next_data
        next_data = set()

    if goal in pre_data:
        white_data = 0
        for i in range(high):
            white_data += data[i].count('.')
        print(white_data - count)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
inf=10**3
T=[[] for _ in range(h+2)]
T[0]=["#" for _ in range(w+2)]
T[h+1]=["#" for _ in range(w+2)]
for i in range(h):
  T[i+1]=["#"]+[inf if _!="#" else "#" for _ in input()]+["#"]
count=0
for t in T:
  count+=t.count("#")
count-=(2*(h+2)+2*w)
T[1][1]=0
Chk=[[1,1]]
while len(Chk)>0:
  c=Chk.pop(0)
  x,y=c[0],c[1]
  if T[x-1][y]!="#" and T[x-1][y]>T[x][y]+1:
    T[x-1][y]=T[x][y]+1
    Chk.append([x-1,y])
  if T[x][y-1]!="#" and T[x][y-1]>T[x][y]+1:
    T[x][y-1]=T[x][y]+1
    Chk.append([x,y-1])
  if T[x+1][y]!="#" and T[x+1][y]>T[x][y]+1:
    T[x+1][y]=T[x][y]+1
    Chk.append([x+1,y])
  if T[x][y+1]!="#" and T[x][y+1]>T[x][y]+1:
    T[x][y+1]=T[x][y]+1
    Chk.append([x,y+1])
print(-1 if T[h][w]==10**3 else h*w-count-T[h][w]-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for ci in c:
    for j in ci:
        if j==".":
            ans+=1
reached=[[0]*W for i in range(H)]
stack.append((0,0))
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
if reached[H-1][W-1]==0:
    print(-1)
else:
    print(ans-(reached[H-1][W-1]+1))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
maze = [input() for x in range(h)]
idou = ([1,0],[0,1],[-1,0],[0,-1])
min_step = [[0 for x in range(w)] for i in range(h)]
next_node = [(0,0)]
past_node = []
min_step[next_node[0][0]][next_node[0][1]] = 1
while next_node:
    for a in idou:
        hei = next_node[0][0] + a[0]
        wei = next_node[0][1] + a[1]
        try:
            if (maze[hei][wei] == "#")|(hei<0)|(wei<0)|(hei>=h)|(wei>=w)|((hei,wei) in past_node):
                continue
            else:
                past_node.append((hei,wei))
                if min_step[hei][wei] != 0:
                    continue
                else:
                    min_step[hei][wei] = min_step[next_node[0][0]][next_node[0][1]]+1
                next_node.append((hei,wei))
        except IndexError:
            continue
    next_node.pop(0)
count = 0
for x in range(h):
    for y in range(w):
        if maze[x][y] == "#":
            count+=1
if min_step[h-1][w-1] == 0:
  print(-1)
else:
  print(h*w-min_step[h-1][w-1]-count)

Submission status: Accepted

Solution code:
import numpy as np
H,W = [ int(it) for it in input().split() ]
x = np.array([ [0 if v == "." else 1 for v in input() ] for i in range(H)]).astype(np.int32)
Close = np.zeros(x.shape).astype(np.int32)
fcost = np.zeros(x.shape).astype(np.int32)+10000
fcost[0,0]=0


gx,gy=(x.shape[0]-1,x.shape[1]-1  )

Open=[(0,0,-1)]
dw=[[0,1],[0,-1],[1,0],[-1,0]]


FLAG_END = False
BREAK = False

Open.sort(key=lambda x:-x[2])
nx,ny,_ =  Open.pop()
for i in range(100000):
    while ( Close[nx,ny]==1 ):
        if ( len(Open)==0):
            print (-1)
            BREAK=True
            break
        Open.sort(key=lambda x:-x[2])
        nx,ny,_ =  Open.pop()
    if BREAK:
        break
    Close[nx,ny]=1
    for dx,dy in dw:
        mx,my=nx+dx,ny+dy
        if ( 0<=mx and mx<x.shape[0] and  0<=my and my<x.shape[1] ):
            if ( Close[mx,my] == 0 and x[mx,my]==0 ):
                fcost[mx,my]=min(fcost[mx,my],fcost[nx,ny]+1)
                Open.append( (mx,my,abs(mx-gx)+abs(my-gy)+fcost[mx,my])  )   
                if (mx==gx and my==gy):
                    FLAG_END = True
                    break
    if (FLAG_END):
        break
if (FLAG_END):
    print (x.shape[0]*x.shape[1]-np.sum(x)-fcost[gx,gy]-1 )

Submission status: Accepted

Solution code:
#ABC088-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
used=[[False for i in range(w)] for j in range(h)]
q=[[0,0,1]]
pos=False
while len(q)>0:
    gy,gx,dis=q.pop(0)
    if gy==h-1 and gx==w-1:
        pos=True
        break
    if not used[gy][gx]:
        if gy!=0:
            if G[gy-1][gx]=="." and not used[gy-1][gx]:
                q.append([gy-1,gx,dis+1])
        if gx!=0:
            if G[gy][gx-1]=="." and not used[gy][gx-1]:
                q.append([gy,gx-1,dis+1])
        if gy!=h-1:
            if G[gy+1][gx]=="." and not used[gy+1][gx]:
                q.append([gy+1,gx,dis+1])
        if gx!=w-1:
            if G[gy][gx+1]=="." and not used[gy][gx+1]:
                q.append([gy,gx+1,dis+1])
    used[gy][gx]=True
if pos:
    ans=0
    for i in range(h):
        ans+=G[i].count(".")
    print(ans-dis)
else:
    print(-1)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
s[0][0]=1
while (H-1,W-1) not in q:
    q2=[]
    i+=1
    for h,w in q:
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
            s[h-1][w]=i
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
            s[h+1][w]=i
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
            s[h][w-1]=i
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
            s[h][w+1]=i
    q=q2
    if len(q)==0:
        break
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)

Submission status: Accepted

Solution code:
import queue

H, W = list(map(int, input().split()))
s = [list(input()) + ['#'] for i in range(H)] + [['#' for i in range(W+1)]]
white = sum([s[i].count('.') for i in range(H)])

q = queue.Queue()
s[0][0] = 1
q.put((0,0))

while not q.empty():
    i, j = q.get()
    for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if s[x][y] == '.':
            s[x][y] = s[i][j]+1
            q.put((x, y))

if s[H-1][W-1] in ['.', '#']:
    print(-1)
else:
    print(white-s[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, # current x
        0, # current y
        0, # count
    ))

    while not q.empty():
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '#':
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
                
        #print(stayed)
    return -1
            

shortest_path_len = bfs()

if shortest_path_len != -1:
    cnt_dot = sum([s.count('.') for s in maze])


    ans = cnt_dot - shortest_path_len - 1
    print(ans)
else:
    print(-1)