from typing import List


def create_cave(depth: int, tx: int, ty: int) -> List[List[int]]:
    """
    Creates the cave according to the cave generation rules.

    Since the cave is essentially infinite a constant size padding is applied
    around the target coordinates to make the pathfinding feasible. Note that
    there needs to be a padding because the optimal path can overshoot the
    target. The padding size for this input was found simply by starting with
    a very large value and progressively decreasing it until a value small
    enough was found which produces the correct pathfinding result but is
    still relatively quick to compute.
    """
    PADDING = 50
    cave = [[0] * (tx + PADDING) for _ in range(ty + PADDING)]

    for y in range(ty + PADDING):
        for x in range(tx + PADDING):
            index = None
            if y == 0 and x == 0:
                index = 0
            elif y == 0:
                index = x * 16807
            elif x == 0:
                index = y * 48271
            elif y == ty and x == tx:
                index = 0

            if index is None:
                cave[y][x] = (cave[y-1][x] * cave[y][x-1] + depth) % 20183
            else:
                cave[y][x] = (index + depth) % 20183

    return cave