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

Solution (Python):
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()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)
    else:
        print(-1)


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)
    else:
        print(-1)


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)
    maze.debug()


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)
    maze.debug()


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
from collections import deque

Y, X = map(int,input().split())


sy,sx = 1,1
gy,gx = Y,X
s = [["
for y in range(Y):
    s[y+1] = list("
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)

Solution (Python):
H, W = map(int,input().split())
c = [["
dots = 0
for y in range(H):
    c[y+1] = "
    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)

Solution (Python):
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:
    
    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)

Solution (Python):
"""
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():
    
    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():
    
    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("
        print(res)


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):

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)

Solution (Python):
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)