Untitled

mail@pastecode.io avatarunknown
python
2 months ago
1.8 kB
1
Indexable
Never
def find_min_dice_rolls(matrix_size, max_dice_value, num_coordinates, coordinates, start, end):
    matrix = [[0] * matrix_size for _ in range(matrix_size)]
    visited = [[False] * matrix_size for _ in range(matrix_size)]

    for coord in coordinates:
        x, y = coord
        if x < y:
            matrix[x - 1][y - 1] = 1
        else:
            matrix[x - 1][y - 1] = -1

    queue = [(start - 1, 0, 0)]  # (position, rolls, ladders)
    visited[start - 1][0] = True

    while queue:
        position, rolls, ladders = queue.pop(0)

        for i in range(1, max_dice_value):
            new_position = position + i
            row, col = divmod(new_position, matrix_size)
            
            if new_position == end - 1:
                return rolls + 1, ladders, 0

            if new_position < matrix_size * matrix_size and not visited[row][col]:
                visited[row][col] = True
                if matrix[row][col] == 1:
                    queue.append((new_position, rolls + 1, ladders + 1))
                elif matrix[row][col] == -1:
                    queue.append((new_position, rolls + 1, ladders))
                else:
                    queue.append((new_position, rolls + 1, ladders))

    return -1, 0, 0

# Read input
matrix_size = int(input())
max_dice_value = int(input())
num_coordinates = int(input())
coordinates = []
for _ in range(num_coordinates):
    x = int(input())
    y = int(input())
    coordinates.append((x, y))
start = int(input())
end = int(input())

# Find the minimal number of dice rolls, number of ladders, and number of slides
rolls, ladders, slides = find_min_dice_rolls(matrix_size, max_dice_value, num_coordinates, coordinates, start, end)

# Print the output
print(rolls)
print(ladders)
print(slides)