Untitled
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)