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:
"""
Maze class.

cf. WarpableMaze class.
"""
from collections import deque
from typing import List, Tuple


class Maze:
    __slots__ = [
        "height",
        "width",
        "road",
        "wall",
        "is_unsearched",
        "grid",
        "dist",
    ]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        road: str = ".",
        wall: str = "#",
        keeps_grid: bool = False,
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.road = road
        self.wall = wall
        self.is_unsearched = 1 << 30
        if keeps_grid:
            convert = lambda c: self.is_unsearched if c == self.road else -1
            self.grid = self._flatten_grid(grid)
            self.dist = list(map(convert, self.grid))
        else:
            self.grid = None
            self.dist = self._convert_grid_to_dist(grid)

    def _flatten_grid(self, grid: List[bytes]) -> str:
        """Flatten a 2D grid."""
        flat_grid = self.wall * self.width
        for row in grid:
            flat_grid += self.wall + row.decode() + self.wall
        flat_grid += self.wall * self.width
        return flat_grid

    def _convert_grid_to_dist(self, grid: List[bytes]) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [-1] * self.height * self.width
        i = self.width
        for row in grid:
            for c in row.decode():
                i += 1
                if c == self.road:
                    dist[i] = self.is_unsearched
            i += 2
        return dist

    def _flatten_coordinate(self, x: int, y: int) -> int:
        """Flatten 2D coordinate values.
        Values of a coordinate must be 1-origin.
        """
        return self.width * x + y

    def bfs(
        self,
        start_2d: Tuple[int, int],
        goal_2d: Tuple[int, int],
        updates_dist: bool = False,
    ) -> int:
        """BFS to compute the distance from start to goal.
        Values of start_2d and goal_2d must be 1-origin.
        """
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        moves = (-self.width, self.width, -1, 1)
        dist = self.dist[:]
        dist[start] = 0
        queue = deque([start])

        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for dx in moves:
                nx = x + dx
                if dist[nx] == self.is_unsearched:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        if updates_dist:
            self.dist = dist
        return dist[goal] if dist[goal] != self.is_unsearched else -1


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    import sys

    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    R, C = map(int, readline().split())
    (*start,) = map(int, readline().split())
    (*goal,) = map(int, readline().split())
    (*S,) = read().split()

    maze = Maze(R, C, S)
    print(maze.bfs(start, goal))


def abc088_d():
    # https://atcoder.jp/contests/abc088/tasks/abc088_d
    import sys

    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    (*S,) = read().split()
    maze = Maze(H, W, S)

    if (dist := maze.bfs((1, 1), (H, W))) == -1:
        print(-1)
    else:
        res = H * W - dist - sum((row.decode()).count("#") for row in S) - 1
        print(res)


if __name__ == "__main__":
    # abc007_c()
    abc088_d()

Submission status: Accepted

Solution code:
# 
import queue

H,W=map(int,input().split())
c,b=[],0
for i in [0]*H:
    c.append(input())
    b+=c[-1].count('#')
    
vis=[[0]*W for _ in [0]*H]

q=queue.Queue()
q.put((0,0,1))
res=-1
while not q.empty():
    x,y,d=q.get()
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx,ny=x+dx,y+dy
        if (nx,ny)==(W-1,H-1):
            res=H*W-(d+1)-b
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if not vis[ny][nx] and c[ny][nx]=='.':
                q.put((nx,ny,d+1))
                vis[ny][nx]=1
        if res>-1:
            break
    if res>-1:
        break
print(res)

Submission status: Accepted

Solution code:
import collections
import itertools

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

dis = [[-1] * w for _ in range(h)]
dis[0][0] = 0
que = collections.deque()
que.append((0, 0))


while que:
    py, px = que.popleft()
    for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        ny = py + dy
        nx = px + dx
        if 0 <= ny < h and 0 <= nx < w and dis[ny][nx] == -1 and maze[ny][nx] == ".":
            dis[ny][nx] = dis[py][px] + 1
            que.append((ny, nx))

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    cnt = 0
    for i, j in itertools.product(range(h), range(w)):
        if maze[i][j] == "#":
            cnt += 1
    print(h * w - cnt - dis[h - 1][w - 1] - 1)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = []
walls = 0
for _ in range(H):
    line = INPUT()
    walls += line.count('#')
    S.append(line)

dist = [[INF]*W for _ in range(H)]
dist[0][0] = 1
queue = deque([[0, 0]])
while queue:
    y, x = queue.popleft()
    if y == H - 1 and x == W - 1:
        print(H*W - walls - dist[y][x])
        break

    for dy, dx in [(y, x-1), (y-1, x), (y, x+1), (y+1, x)]:
        if 0 <= dy < H and 0 <= dx < W and S[dy][dx] == '.' and dist[dy][dx] == INF:
            dist[dy][dx] = dist[y][x] + 1
            queue.append([dy, dx])
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, gcd
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 functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    H, W = MAP()
    S = []
    walls = 0
    for _ in range(H):
        line = INPUT()
        walls += line.count('#')
        S.append(line)

    dist = [[INF]*W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([[0, 0]])
    while queue:
        y, x = queue.popleft()
        if y == H - 1 and x == W - 1:
            print(H*W - walls - dist[y][x])
            break

        for dy, dx in [(y, x-1), (y-1, x), (y, x+1), (y+1, x)]:
            if 0 <= dy < H and 0 <= dx < W and S[dy][dx] == '.' and dist[dy][dx] == INF:
                dist[dy][dx] = dist[y][x] + 1
                queue.append([dy, dx])
    else:
        print(-1)


if __name__ == '__main__':
    main()

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
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
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
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 = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = [input() for h in range(H)]
q = deque([(0, 0)])
# s : 0, 0
# g : H - 1, W - 1
visited = [[False] * W for i in range(H)]
dw = [0, 1, 0, -1]
dh = [1, 0, -1, 0]
dist = [[INF] * W for i in range(H)]
dist[0][0] = 1

dic = defaultdict(int)

for h in range(H):
    for w in range(W):
        dic[S[h][w]] += 1

if S[0][0] == "#":
    print("-1")
    exit()
while q:
    h, w = q.popleft()
    # if S[h][w] == "#":
    for i in range(4):
        nw = w + dw[i]
        nh = h + dh[i]
        if 0 <= nw < W and 0 <= nh < H:
            if S[nh][nw] != "#" and visited[nh][nw] == False:
                # dist[nh][nw] = min(dist[h][w] + 1, dist[nh][nw])
                dist[nh][nw] = dist[h][w] + 1
                visited[nh][nw] = True
                q.append((nh, nw))
# print(visited)
# print(*dist, sep="\n")
if dist[H-1][W-1] == INF:
    print(-1)
else:
    print(dic["."] - dist[H-1][W-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
s = ["#"*(W+2)] + ["#"+input()+"#" for _ in range(H)] + ["#"*(W+2)]

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

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

q = deque()
q.append((1, 1))
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 0
cnt = 0
while q:
	y, x = q.popleft()
	for i in range(4):
		ny = y+dy[i]
		nx = x+dx[i]
		if s[ny][nx] == "." and dist[ny][nx]==-1:
			dist[ny][nx] = dist[y][x]+1
			q.append((ny, nx))

print(white-dist[H][W]-1 if dist[H][W] != -1 else -1)

Submission status: Accepted

Solution code:
import networkx as nx
import numpy as np

h, w, *X, = open(0).read().split()
h, w = int(h), int(w)

G = nx.grid_2d_graph(h, w)
for i, S in enumerate(X):
    for j, s in enumerate(S):
        if s == '#':
            G.remove_node((i, j))
try:
    path = nx.shortest_path(G, (0, 0), (h-1, w-1))
except nx.NetworkXNoPath:
    print(-1)
else:
    for node in path:
        G.remove_node(node)
    print(len(G.nodes))

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    h,w = map(int, input().split())
    s = [input().rstrip() for i in range(h)]

    visited = [[0]*w for i in range(h)]
    dist = [[INF]*w for i in range(h)]

    que = deque([(0,0)])
    visited[0][0] = 1
    dist[0][0] = 0

    dx = (1, -1, 0, 0)
    dy = (0, 0, 1, -1)

    while len(que) > 0:
        x,y = que.popleft()
        if x == w-1 and y == h-1: # ゴールまで辿ったら
            break

        for k in range(4): # 上下左右4パターンの移動方法
            nx = x + dx[k]
            ny = y + dy[k]

            if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                que.append((nx,ny))
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1

    if dist[h-1][w-1] == INF:
        print(-1)
    else:
        print(sum(s[i].count(".") for i in range(h)) - (dist[h-1][w-1]+1))


if __name__=="__main__":
    main(
    )

Submission status: Accepted

Solution code:

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

maze=[]

count_white=0

for i in range(h):
    maze_row = input()
    maze.append(maze_row)
    
    count_white+=maze_row.count(".")
    
dist = [ [-1]*w for i in range(h)]
goal = [w-1,h-1]
q=queue.Queue()
q.put((0,0,0))

moves = [[0,1], [1,0], [0,-1], [-1,0]]
dmax=-1
while not q.empty():
    
    x,y,d = q.get()
    
    if x==goal[0] and y==goal[1]:
        time=d
        dist[y][x]=d
        dmax=d
        break
    
    if dist[y][x] >= 0:
        continue
    
    else:
        
        dist[y][x]=d
        
        for dx,dy in moves:
            
            if 0<=x+dx<w and 0<=y+dy<h:
                if dist[y+dy][x+dx] == -1 and maze[y+dy][x+dx]!="#":
                
                    q.put((x+dx,y+dy,d+1))
if dmax!=-1:
    print(count_white-dmax-1)
    
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
white = 0
for i in range(H):
  s = str(input())
  S.append(s)
  white += s.count('.')
  
def main(h, w):
  global H
  global W
  global S
  global l
  tmp = []
  if h < H-1:
    if (S[h+1][w]=='.') and ([h+1, w] not in l):
      tmp.append([h+1, w])
  if w < W-1:
    if (S[h][w+1]=='.') and ([h, w+1] not in l):
      tmp.append([h, w+1])
  if 0 < h:
    if (S[h-1][w]=='.') and ([h-1, w] not in l):
      tmp.append([h-1, w])
  if 0 < w:
    if (S[h][w-1]=='.') and ([h, w-1] not in l):
      tmp.append([h, w-1])
  return tmp
    
cnt = 0
l = [[0, 0]]
tmp = [[0, 0]]
for i in range(10000):
  t = []
  for n in tmp:
    u = main(n[0], n[1])
    l += u
    t += u
  if t == []:
    ans = white+1
  elif [H-1, W-1] in t:
    ans = i+2
    break
  else:
    tmp = t
print(white-ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [[0 if c == '#' else 1 for c in input()] for _ in range(h)]

directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0] = 0
q = [(0, 0)]
for y, x in q:
    for dy, dx in directions:
        ny, nx = y + dy, x + dx
        if (ny < 0 or h <= ny) or (nx < 0 or w <= nx):
            continue
        if not s[ny][nx]:
            continue
        if dist[ny][nx] >= 0:
            continue
        dist[ny][nx] = dist[y][x] + 1
        q.append((ny, nx))

if dist[-1][-1] < 0:
    print(-1)
else:
    print(sum(sum(si) for si in s) - dist[-1][-1] - 1)

Submission status: Accepted

Solution code:
#幅優先探索
H,W=map(int,input().split())
sy,sx=0,0
gy,gx=H-1,W-1
MAZE=[0]*H
queue=[]
queue.append([sy,sx])
black=0
for i in range(H):
  MAZE[i]=list(str(input()))
  black+=MAZE[i].count('#')
MAZE[sy][sx]='#'

d=[[100000000]*W for i in range(H)]
d[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
goal=0
while len(queue)>0:
  #Qを取り出す
  Q=queue.pop(0)
  move=d[Q[0]][Q[1]]
  #もし取り出したところがゴールなら出力して終了
  if Q==[gy,gx]:
    goal=1
    break
  #4方向をループする
  for j in range(4):
    y=Q[0]+dy[j]
    x=Q[1]+dx[j]
    if 0<=y<H and 0<=x<W and MAZE[y][x] == '.':
      queue.append([y,x])
      MAZE[y][x] = '#'
      d[y][x] = move+1
if goal==1:
    print(H*W-black-move-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
##いくつかの人の回答を参考に、メモしながら学習
H, W = map(int, input().split())
Field = [list(input()) for _ in range(H)]

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

# 出力するスコアは「全白マス数」-「最短距離のマス数」なので、まず白マスの数を数える。
white = 0
for i in range(H):
    for j in range(W):
        if Field[i][j] == '.':
            white += 1

# 移動する4方向
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# HxWの行列を作る。初期値は全部"None"。ここにスタートからゴールまでの歩数を入れていく。
    # Field_map[H-1][W-1]がゴールまでの「最短距離のマス数」になる。
Field_cost =[[None]*W for i in range(H)]
Field_cost[0][0] = 0

# whileでゴールまでの最短距離を幅優先探索
from collections import deque
que = deque([])     # デックリストqueに、最短距離を通る際の(i,j)が入っていく。
que.append((0, 0))  # まず(0,0)は通るので。

while que:
    i, j = que.popleft()       # (i,j)が今いるマス
    if i == H-1 and j == W-1:  # (i,j)がゴールマスになったらやめ
        break
    for d in range(4):
        new_i = i + dx[d]
        new_j = j + dy[d]
        if 0 <= new_i and new_i < H and \
           0 <= new_j and new_j < W and \
           Field[new_i][new_j] != '#' and \
           Field_cost[new_i][new_j] == None:  # 1,2は道を外れてないこと。3はちゃんと白マス。4はまだ通ってないこと。
            que.append((new_i, new_j))     # このマス
            Field_cost[new_i][new_j] = Field_cost[i][j] + 1  # 前のマス+1。何マス歩いてきたか。

# 出力するスコアは「全白マス数」-「最短距離のマス数」
if Field_cost[H-1][W-1] is None:
    print("-1")
else:
    print(white - Field_cost[H-1][W-1]-1)

Submission status: Accepted

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

H,W = map(int, input().split())
mapmatrix = [None]*H
before_black_cnt = 0
for i in range(H):
    st = input()
    before_black_cnt += st.count('#')
    mapmatrix[i] = list(st)


queue = deque()
queue.append((0,0))
distancelist = [[-1]*W for _ in range(H)]
distancelist[0][0] = 1

move = ((-1,0),(1,0),(0,-1),(0,1))

while queue:
    x,y = queue.popleft()
    
    distance = distancelist[y][x]
    for dx,dy in move:
        X = x + dx; Y = y + dy
        if X >= 0 and X < W and Y >= 0 and Y < H:
            if distancelist[Y][X] == -1 and mapmatrix[Y][X] == '.':
                distancelist[Y][X] = distance + 1
                queue.append((X,Y))
if distancelist[H-1][W-1] == -1:
    print(-1)
else:
    after_black_cnt = W*H - distancelist[H-1][W-1]
    print(after_black_cnt - before_black_cnt)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
table = [[float('inf') for _ in range(w)] for _ in range(h)]
table[0][0] = 0
def bfs():
    que = deque([[0, 0]])
    # print(que)
    used = [[0 for _ in range(w)] for _ in range(h)]
    used[0][0] = 1
    while que:
        # print(que.popleft())
        y, x = que.popleft()
        for k in range(4):
            if 0 <= y+dy[k] < h and 0 <= x+dx[k] < w:
                if s[y+dy[k]][x+dx[k]] == '#':
                    continue
                if used[y+dy[k]][x+dx[k]] == 0:
                    table[y+dy[k]][x+dx[k]] = min(table[y+dy[k]][x+dx[k]], table[y][x]+1)
                    used[y+dy[k]][x+dx[k]] = 1
                    que.append((y+dy[k], x+dx[k]))
    
    # print(*table, sep='\n')
    return table[h-1][w-1]

c = bfs()
if c == float('inf'):
    print(-1)
else:
    white = 0
    for i in range(h):
        white += s[i].count('.')
    ans = white - (c+1)
    print(ans)

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_multi()

    d = [[-1] * (w+2) for _ in range(h+2)]

    shiro = 0
    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10**9
                shiro += 1


    d[1][1] = 1
    q = deque([])
    q.append([1,1])

    flg = False
    while q:
        wk = q.popleft()
        i = wk[0]
        ii = wk[1]
        hosuu = d[i][ii]

        if i == h and ii == w:
            flg = True
            print(shiro-hosuu)
            break

        def add_que(i,ii,hosuu):
            if d[i][ii] == 10**9:
                d[i][ii] = hosuu + 1
                q.append([i,ii])

        add_que(i-1,ii, hosuu)
        add_que(i+1,ii, hosuu)
        add_que(i,ii-1, hosuu)
        add_que(i,ii+1, hosuu)

    if not flg:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10000
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[-1 for _ in range(W)] for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            A[i][j]=INFTY
            cnt += 1
que = deque([(0,0,0)])
A[0][0] = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and A[i][j+1]<0:
        A[i][j+1]=d+1
        que.append((i,j+1,d+1))
    if i-1>=0 and A[i-1][j]<0:
        A[i-1][j]=d+1
        que.append((i-1,j,d+1))
    if j-1>=0 and A[i][j-1]<0:
        A[i][j-1]=d+1
        que.append((i,j-1,d+1))
    if i+1<H and A[i+1][j]<0:
        A[i+1][j] = d+1
        que.append((i+1,j,d+1))
if A[H-1][W-1]<0:
    print(-1)
else:
    print(H*W-cnt-A[H-1][W-1]-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
MASUlist = [input() for _ in range(H)]
MASU = [[0 for i in range(W)]for j in range(H)]
white = 0
for i in range(H):
    S = MASUlist[i]
    for j in range(W):
        if S[j] == "#":
            MASU[i][j] = 1
        else:
            MASU[i][j] = 0
            white += 1
MASU[H-1][W-1] = 2
d = deque()
d.append([0, 0])
dx_dy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
looked = [[0 for i in range(W)]for j in range(H)]
looked[0][0] = 1

while d:
    x = d.popleft()
    lookx = x[0]
    looky = x[1]
    for i in dx_dy:
        a = lookx+i[0]
        b = looky+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or MASU[a][b] == 1 or looked[a][b] != 0:
            continue
        d.append([a, b])
        looked[a][b] = looked[lookx][looky]+1

ans = looked[H-1][W-1]
if ans == 0:
    print(-1)
else:
    print(white-ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import numpy as np

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

grid = [list(map(str, input().rstrip())) for _ in range(h)]
init = np.where(np.array(grid).flatten() == "#")[0].shape[0]

moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

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

while q:
    curr = q.popleft()
    for m in moves:
        nx = curr[0] + m[0]
        ny = curr[1] + m[1]
        if 0 <= nx < h and 0 <= ny < w:
            if grid[nx][ny] == ".":
                grid[nx][ny] = grid[curr[0]][curr[1]] + 1
                q.append([nx, ny])
                if nx == h - 1 and ny == w - 1:
                    print(h * w - grid[nx][ny] - init)
                    sys.exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

black = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            black += 1

q = deque()
q.append((0, 0, 0))
visited = set()
while q:
    x, y, c = q.popleft()
    if x == W-1 and y == H-1:
        break
    if (x, y) in visited:
        continue
    visited.add((x, y))

    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                q.append((nx, ny, c+1))

if x == W-1 and y == H-1:
    print(H*W - black - c - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())

s=[list(input()) for _ in range(h)]

black_cnt=0
for ss in s:
    black_cnt+=ss.count("#")

from collections import deque
stack=deque([(0,0)])
s[0][0]=1
flag=0
while len(stack)>0:
    #print(stack)
    tmp=stack.popleft()
    if tmp[0]==h-1 and tmp[1]==w-1:
        flag=1
        break

    for (my,mx) in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny=tmp[0]+my
        nx=tmp[1]+mx
        #print(ny,nx)
        if 0<=ny and ny<h and 0<=nx and nx<w:
            #print(ny,nx)
            if s[ny][nx]==".":
                #print(ny,nx,tmp[0],tmp[1],stack)
                s[ny][nx]=s[tmp[0]][tmp[1]]+1
                stack.append((ny,nx))

#for item in s:
 #   print(item)
if flag==1:
    print(h*w-s[-1][-1]-black_cnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]
black = 0
stack = deque([[0,0]])
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            black += 1

dp = [[-1]*W for _ in range(H)]
dp[0][0] = 0
while len(stack) > 0:
    y,x = stack.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < H and 0 <= nx < W and cell[ny][nx] == '.' and dp[ny][nx] == -1:
            dp[ny][nx] = dp[y][x]+1
            stack.append([ny, nx])

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

Submission status: Accepted

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


def read():
    H, W = map(int, input().strip().split())
    S = []
    for i in range(H):
        s = list(input().strip())
        S.append(s)
    return H, W, S


def solve(H, W, S):
    n_cells = 0
    for y in range(H):
        for x in range(W):
            if S[y][x] == ".":
                n_cells += 1
    A = [[-1 for j in range(W)] for i in range(H)]
    A[0][0] = 1
    D = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque()
    q.append((0, 0))
    while q:
        y, x = q.popleft()
        for dy, dx in D:
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and A[ny][nx] == -1:
                A[ny][nx] = A[y][x] + 1
                q.append((ny, nx))
    shortest = A[H-1][W-1]
    return n_cells - shortest if shortest > 0 else -1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
Ss = [input() for _ in range(H)]
from collections import deque
Q = deque()

dirc = ((1, 0), (0, 1), (-1, 0), (0, -1))
Q.append((0, 0))
dist = [[10**18]*W for _ in range(H)]
dist[0][0] = 1
while Q:
    y, x = Q.popleft()
    if y==H-1 and x==W-1:
        break
    for dy, dx in dirc:
        ny, nx = dy+y, dx+x
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if Ss[ny][nx]=='#':
            continue
        if dist[ny][nx]>dist[y][x]+1:
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))

white = 0
for s in Ss:
    white += s.count('.')
if dist[H-1][W-1]>=10**17:
    print(-1)
else:
    print(white-dist[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for _ in range(W*H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0

for i in range(H):
    for j in range(W):
        if s[i][j] == '#': continue
        ans += 1
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < H and 0 <= x < W:
                if s[y][x] == '.':
                    adj[W*i + j].append(W*y + x)

queue = deque([0])
visit = [-1] * (H*W)
visit[0] = 1

while queue:
    now = queue.popleft()
    for u in adj[now]:
        if visit[u] < 0:
            queue.append(u)
            visit[u] = visit[now] + 1

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

Submission status: Accepted

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


def main():
    h,w = map(int, input().split())
    sl = []
    white = 0
    for _ in range(h):
        row = list(input())
        white += row.count('.')
        sl.append(row)

    visited = [ [-1]*w for i in range(h)]
    bfs(sl, visited, 0, 0, h-1, w-1, h, w)
    dist = visited[h-1][w-1]
    if dist == -1:
        print(-1)
    else:
        ans = white - dist - 1
        print(ans)





if __name__ == "__main__":
    main()