Description

You are an explorer preparing to venture into a mysterious forest filled with rewards and challenges.

The forest is represented as a Binary Tree, where each node is a checkpoint containing a score. Positive scores represent rewards, while negative scores represent penalties.

The forest has a main entrance at the root node (ID = 1). However, your expedition may begin at a different checkpoint, specified by S.

You will explore the region consisting of checkpoint S and all of its descendants.

An ending checkpoint (leaf node) is a checkpoint with no children.

Before starting your adventure, you want to evaluate the rewards and discover the most valuable routes through the forest.

Your task is to implement the following three functions :

1. count_reward_stops(node)

Some checkpoints provide valuable rewards.

Count the number of checkpoints with a positive score in the region starting at node.

• node represents the starting checkpoint of the region.

• A checkpoint is considered a reward stop if its score is strictly greater than 0.

• Include the starting checkpoint and all its descendants.

2. best_expedition(node)

You want to find the most rewarding expedition route.

An expedition begins at the specified checkpoint and follows the forest paths downward until reaching an ending checkpoint.

Find the maximum total score obtainable from such an expedition.

• The expedition must start at node and end at a leaf node.

• At each checkpoint, you may continue to its left or right child, if available.

• The total score includes all checkpoints along the route, including the starting and ending checkpoints.

3. best_crossing_through_start(node)

Some of the forest's most valuable routes connect two different ending checkpoints.

A forest crossing is a path connecting two distinct ending checkpoints. Unlike a regular expedition, a forest crossing may travel upward and downward along the tree connections.

Find the maximum total score of a forest crossing that passes through the starting checkpoint node.

• The crossing must connect a leaf node in the left subtree of node to a leaf node in its right subtree.

• The crossing must pass through the starting checkpoint node.

• The total score includes all checkpoints along the path, with each checkpoint counted exactly once.

• Return the maximum total score of a valid forest crossing.

Important Notes

• All checkpoint scores may be negative.

• The starting checkpoint S may be any node in the tree, not necessarily the root.

• All three functions consider only the subtree rooted at S.

• An expedition must end at a leaf node, even if stopping earlier would produce a higher score.

• A forest crossing must connect two distinct leaf nodes, one in the left subtree and one in the right subtree of S.

• A forest crossing must pass through the starting checkpoint S.

• Each checkpoint along a crossing is counted exactly once.

• The starting checkpoint S is guaranteed to have both a left child and a right child.

Start code

tree = {}

def count_reward_stops(node):
    #TODO
    pass

def best_expedition(node):
    #TODO
    pass

def best_crossing_through_start(node):
    #TODO
    pass

N, S = map(int, input().split())
for _ in range(N):
    node_id, score, left, right = map(int, input().split())
    tree[node_id] = [score, left, right]

print("Reward Stops:", count_reward_stops(S))
print("Best Expedition:", best_expedition(S))
print("Best Forest Crossing:", best_crossing_through_start(S))

 

Input

The first line contains two integers, N and S, representing the number of checkpoints and the starting checkpoint.

The next N lines each contain four integers:

node score left right

• node: The ID of the current checkpoint.

• score: The score of the checkpoint.

• left: The ID of its left child, or 0 if there is no left child.

• right: The ID of its right child, or 0 if there is no right child.

The root node always has ID 1, but the starting checkpoint S may be any node in the tree.

The starting checkpoint S is guaranteed to have both a left child and a right child.

Output

Print three lines:

• Reward Stops: X, where X is the number of checkpoints with a positive score in the subtree rooted at S.

• Best Expedition: Y, where Y is the maximum total score along a path from S to a leaf node.

• Best Forest Crossing: Z, where Z is the maximum total score along a path connecting a leaf in the left subtree of S to a leaf in its right subtree.

All checkpoint scores along each path are included exactly once.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, you wake up inside a mysterious underground maze. Fortunately, you discover a map showing the walls, open spaces, and the exit.

The maze is represented as an M × N grid, containing four symbols:

• . : An open space you can walk through.

• x : A wall you cannot pass through (lowercase x, not uppercase X).

• S : Your starting position.

• D : The destination you want to reach.

You may move up, down, left, or right. Diagonal movement is not allowed.

Before attempting to escape, you decide to investigate the maze and discover how many possible escape routes are available.

Your task is to implement the following two functions:

1. survey_zone(row, col)

The maze may contain several disconnected areas.

A safe zone is a group of connected walkable cells. Two cells belong to the same safe zone if you can travel between them without passing through walls.

Explore the safe zone containing the given position and mark all reachable cells as visited.

• row and col represent the current position.

• Both S and D are considered walkable cells.

• Return 1 if the position belongs to a previously unexplored safe zone.

• Return 0 if the position is outside the maze, is a wall, or has already been visited.

2. count_escape_routes(row, col)

An escape route is a path that starts at S and ends at D.

Count the total number of different valid escape routes.

• row and col represent the current position.

• Each cell can be visited at most once within the same escape route.

• Different escape routes may share cells, but each route must be counted separately.

• Use the global variable paths to count the total number of valid escape routes.

• The function does not need to return a value.

Important Notes

• You may only move up, down, left, or right. Diagonal movement is not allowed.

• You cannot move outside the maze or through walls.

• The wall symbol is a lowercase x, not an uppercase X.

• The maze contains exactly one starting position S and one destination D.

• An escape route ends immediately upon reaching D.

• Two separate visited arrays are provided:

  • visited_zones tracks cells visited during safe zone exploration.

  • visited_routes tracks cells visited while exploring escape routes.

Start code

m, n = map(int, input().split())
maze = [list(input()) for _ in range(m)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited_zones = [[False] * n for _ in range(m)]
visited_routes = [[False] * n for _ in range(m)]
zones = 0
paths = 0
for i in range(m):
    for j in range(n):
        if maze[i][j] == 'S':
            start_row, start_col = i, j

def survey_zone(row, col):
    # TODO
    pass

def count_escape_routes(row, col):
    # TODO
    pass

for i in range(m):
    for j in range(n):
        zones += survey_zone(i, j)
count_escape_routes(start_row, start_col)
print("Safe Zones:", zones)
print("Escape Routes:", paths)

Input

The first line contains two integers, M and N, representing the number of rows and columns in the maze.

The next M lines each contain exactly N characters representing the maze, with no spaces between characters.

Each character is one of ., x, S, or D.

Output

Print two lines:

• Safe Zones: Z, where Z is the total number of disconnected safe zones.

• Escape Routes: P, where P is the total number of valid escape routes from S to D.

If no escape route exists, P should be 0.

Sample Input  Download

Sample Output  Download

Tags

Discuss