import random


def generate_random_grid(n: int, m: int) -> list[list[str]]:
    """
    Returns a random n x m grid filled with spaces and W's
    with equal probabilities.

    Args:
        n (int): the number of rows
        m (int): the number of columns

    Returns:
        list[list[str]]: the randomly generated grid
    """
    ...


def all_coordinates(grid: list[list[str]]) -> list[tuple[int, int]]:
    """
    Returns a list of all possible valid coordinates into the provided
    grid.

    Args:
        grid (list[list[str]]): the provided grid

    Returns:
        list[tuple[int, int]]: a list of valid coordinates into grid
    """
    ...


def find_random_empty(grid: list[list[str]]) -> tuple[int, int]:
    """
    Returns a random pair of coordinates into grid that currently
    point to a space.

    Args:
        grid (list[list[str]]): the grid to search

    Returns:
        tuple[int, int]: the found pair of coordinates pointing to empty
    """
    ...


def get_all_directions(coord: tuple[int, int], grid: list[list[str]]) -> set[tuple[int, int]]:
    """
    Returns a set of coordinate pairs that represent valid coordinates into grid that
    are directly next to the provided `coord`.

    Args:
        coord (tuple[int, int]): the coordinate pair to look near
        grid (list[list[str]]): the grid to look into

    Returns:
        set[tuple[int, int]]: a set of coordinate pairs of all valid coordinates near `coord`
    """
    DIRS: list[tuple[int, int]] = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    ...


def flood_fill(grid: list[list[str]], coord: tuple[int, int]) -> None:
    """
    Repeatedly fills in empty cells in grid with `o`, starting from `coord` 
    until there are no empty cells reachable from `coord`.

    Args:
        grid (list[list[str]]): the grid to flood fill
        coord (tuple[int, int]): the coordinate pair to start at

    Raises:
        ValueError: if the coord doesn't point to an empty square
    """
    ...