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:
from collections import deque

R, C = map(int, input().split())
masu = [list(input()) for _ in range(R)]
sr, sc = 0, 0
gr, gc = R - 1, C - 1

def bfs():
    d = [[float("inf")] * C for _ in range(R)]
    dr = [0, -1, 0, 1]
    dc = [1, 0, -1, 0]
    que = deque([])

    que.append((sr, sc))
    d[sr][sc] = 0
    while que:
        p = que.popleft()
        if p[0] == gr and p[1] == gc:
            break
        for i in range(4):
            nr = p[0] + dr[i]
            nc = p[1] + dc[i]
            if (0 <= nr < R) and (0 <= nc < C) and masu[nr][nc] != "#" and d[nr][nc] == float("inf"):
                que.append((nr, nc))
                d[nr][nc] = d[p[0]][p[1]] + 1
    
    return d[gr][gc]

white = 0
for i in range(R):
    for j in range(C):
        if masu[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    print(white - res - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
"""
Maze class.

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


class Maze:
    __slots__ = ["height", "width", "wall", "sentinel", "unsearched", "dist"]

    def __init__(
        self, height: int, width: int, grid: List[bytes], wall: str = "#",
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.wall = -1
        self.sentinel = -2
        self.unsearched = 1 << 30
        self.dist = self._convert_grid_to_dist(grid, wall)

    def _convert_grid_to_dist(self, grid: List[bytes], wall) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.sentinel] * self.height * self.width
        i = self.width
        for row in grid:
            for c in row.decode():
                i += 1
                dist[i] = self.wall if c == wall else self.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.unsearched:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        if updates_dist:
            self.dist = dist
        return dist[goal] if dist[goal] != self.unsearched else self.wall

    def debug(self) -> None:
        """Show debugging information."""

        def convert(n: int) -> str:
            if n == self.sentinel:
                return "†"
            elif n == self.wall:
                return "#"
            return "."

        print(f"<DEBUG>\nheight={self.height}, width={self.width}\n", file=sys.stderr)
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


class BreakableMaze(Maze):
    def __init__(self, height: int, width: int, grid: List[bytes], wall: str = "#"):
        self.start = -1
        self.goal = -1
        super().__init__(height, width, grid, wall)

    def _convert_grid_to_dist(self, grid: List[bytes], wall) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.sentinel] * self.height * self.width
        i = self.width
        for row in grid:
            for c in row.decode():
                i += 1
                dist[i] = self.wall if c == wall else self.unsearched
                if c == "s":
                    self.start = i
                elif c == "g":
                    self.goal = i
            i += 2
        return dist

    def breakable_bfs(self, updates_dist: bool = False) -> int:
        """BFS to compute the distance from start to goal.
        """
        moves = (-self.width, self.width, -1, 1)
        dist = self.dist[:]
        dist[self.start] = 0
        queue = deque([self.start])

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

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

        if updates_dist:
            self.dist = dist
        return dist[self.goal]


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    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
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

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

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


def arc005_c():
    # https://atcoder.jp/contests/arc005/tasks/arc005_3
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    (*C,) = read().split()
    maze = BreakableMaze(H, W, C)
    print("YES" if maze.breakable_bfs() <= 2 else "NO")


if __name__ == "__main__":
    # abc007_c()  # https://atcoder.jp/contests/abc007/tasks/abc007_3
    abc088_d()  # https://atcoder.jp/contests/abc088/tasks/abc088_d
    # arc005_c()  # https://atcoder.jp/contests/arc005/tasks/arc005_3

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
w_sum=0
maze=[]
inf=10000000
for _ in range(h):
  s=list(input())
  for i in range(w):
    if s[i]=='.':
      s[i]=inf
      w_sum+=1
  maze.append(s)
  
def solve(maze,h,w):
  qu=deque([[0,0]])
  maze[0][0]=0
  while qu:
    y,x=qu.popleft()
    t=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        if maze[ny][nx]>t+1:
          maze[ny][nx]=t+1
          qu.append([ny,nx])
          
  return maze[h-1][w-1]
  
if solve(maze,h,w)==inf:
  print(-1)
else:
  print(w_sum-solve(maze,h,w)-1)

Submission status: Accepted

Solution code:
from queue import Queue
from itertools import product


def main():
    h, w = map(int, input().split())
    grid = ["." * w for _ in range(h)]
    for i in range(h):
        grid[i] = input()
    num_white = 0
    for i, j in product(range(h), range(w)):
        if grid[i][j] == ".":
            num_white += 1
    dist = [[-1] * w for _ in range(h)]
    q = Queue()
    q.put((0, 0))
    dist[0][0] = 1
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]
    while not q.empty():
        i, j = q.get()
        d = dist[i][j]
        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
            if grid[ni][nj] == "#":
                continue
            if dist[ni][nj] != -1 and dist[ni][nj] <= d + 1:
                continue
            dist[ni][nj] = d + 1
            q.put((ni, nj))
    print(num_white - dist[h - 1][w - 1] if dist[h - 1][w - 1] != -1 else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
Maze class.

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


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

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        *,
        road: str = ".",
        wall: str = "#",
        is_unsearched: int = 1 << 30,
        is_unreachable: int = -1,
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.road = road
        self.wall = wall
        self.is_unsearched = is_unsearched
        self.is_unreachable = is_unreachable
        self.dist = self._convert_grid_to_dist(grid)

    def _convert_grid_to_dist(self, grid: List[bytes]) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.is_unreachable] * 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 self.is_unreachable

    def debug(self) -> None:
        """Show debugging information."""
        print(
            f"<DEBUG>\n"
            f"height={self.height}, width={self.width}\n"
            f"is_unsearched={self.is_unsearched}, is_unreachable={self.is_unreachable}",
            file=sys.stderr,
        )

        convert = lambda x: self.road if x != self.is_unreachable else self.wall
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    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
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

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

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


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

Submission status: Accepted

Solution code:
"""
Maze class.

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


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

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        *,
        road: str = ".",
        wall: str = "#",
        is_unsearched: int = 1 << 30,
        is_unreachable: int = -1,
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.road = road
        self.wall = wall
        self.is_unsearched = is_unsearched
        self.is_unreachable = is_unreachable
        self.dist = self._convert_grid_to_dist(grid)

    def _convert_grid_to_dist(self, grid: List[bytes]) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.is_unreachable] * 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 self.is_unreachable

    def debug(self) -> None:
        """Show debugging information."""
        print(
            f"<DEBUG>\n"
            f"height={self.height}, width={self.width}\n"
            f"is_unsearched={self.is_unsearched}, is_unreachable={self.is_unreachable}",
            file=sys.stderr,
        )

        convert = lambda x: self.road if x != self.is_unreachable else self.wall
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    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
    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 - sum((row.decode()).count("#") for row in S) - dist - 1
        print(res)
    maze.debug()


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

Submission status: Accepted

Solution code:
"""
Maze class.

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


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

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.road = road
        self.wall = wall
        self.is_unsearched = 1 << 30
        self.is_unreachable = -1
        self.dist = self._convert_grid_to_dist(grid)

    def _convert_grid_to_dist(self, grid: List[bytes]) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.is_unreachable] * 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 self.is_unreachable

    def debug(self) -> None:
        print(
            f"<DEBUG>\n"
            f"height={self.height}, width={self.width}\n"
            f"is_unsearched={self.is_unsearched}, is_unreachable={self.is_unreachable}",
            file=sys.stderr,
        )

        convert = lambda x: self.road if x != self.is_unreachable else self.wall
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    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
    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 - sum((row.decode()).count("#") for row in S) - dist - 1
        print(res)


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

Submission status: Accepted

Solution code:
"""
Maze class.

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


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

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.road = road
        self.wall = wall
        self.is_unsearched = 1 << 30
        self.is_unreachable = -1
        self.dist = self._convert_grid_to_dist(grid)

    def _convert_grid_to_dist(self, grid: List[bytes]) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.is_unreachable] * 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 self.is_unreachable

    def debug(self) -> None:
        print(
            f"<DEBUG>\n"
            f"height={self.height}, width={self.width}\n"
            f"is_unsearched={self.is_unsearched}, is_unreachable={self.is_unreachable}",
            file=sys.stderr,
        )

        convert = lambda x: self.road if x != self.is_unreachable else self.wall
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


def abc007_c():
    # https://atcoder.jp/contests/abc007/tasks/abc007_3
    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
    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 - sum((row.decode()).count("#") for row in S) - dist - 1
        print(res)
    maze.debug()


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

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",
        "is_unreachable",
        "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
        self.is_unreachable = -1

        if keeps_grid:
            convert = {road: self.is_unsearched, wall: self.is_unreachable}
            self.grid = self._flatten_grid(grid)
            self.dist = [convert[c] for c in 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 = [self.is_unreachable] * 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 self.is_unreachable


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 - sum((row.decode()).count("#") for row in S) - dist - 1
        print(res)


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

Submission status: Accepted

Solution code:
from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [(-1,0),(1,0),(0,-1),(0,1)]
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.pop()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost+1:
            c[y2][x2] = cost+1
            q.append((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
lst = []
block = 0
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '#':
            block += 1
        lst.append(s[j])
queue = [(1, 0)]
visited = set()
flag = False
while queue:
    #print(queue)
    step, pos = queue.pop(0)
    if pos in visited:
        continue
    if pos == h * w - 1:
        flag = True
        ans = step
        break
    visited.add(pos)
    step += 1
    if pos > (pos // w) * w:
        if lst[pos - 1] == '.':
            queue.append((step, pos - 1))
    if pos < ((pos // w) + 1) * w - 1:
        if lst[pos + 1] == '.':
            queue.append((step, pos + 1))
    if pos >= w:
        if lst[pos - w] == '.':
            queue.append((step, pos - w))
    if pos < (h - 1) * w:
        if lst[pos + w] == '.':
            queue.append((step, pos + w))
if flag:
    print(h * w - block - ans)
else:
    print(-1)