Mushrooms#5438
Masha is planning a visit to her grandmother and is bringing two baskets: one filled with pies and another empty, intended for collecting mushrooms along her journey.
To reach her grandmother's house, Masha must traverse a forest represented as an m \times n grid. Some cells in this grid contain trees, while others have mushrooms. Masha begins her journey at cell and aims to reach her grandmother's village located at cell . She can move either right or down, meaning she can increase either her row or column coordinate by with each move. However, she cannot move into a cell that contains a tree. If both the right and down cells are blocked by trees, Masha will be unable to proceed and is considered lost.
Your task is to determine whether Masha can successfully reach her grandmother without getting lost. If she can, you should also calculate the maximum number of mushrooms she can collect on her path.
The first line of the input contains four integers: , , , and (2 \leq m, n \leq 100, 0 \leq g, t \leq g + t \leq m n - 2). The following lines each contain two numbers, representing the and -coordinates of each mushroom. After these, lines follow, each describing the coordinates of a tree in the same format. No cell will contain more than one mushroom, nor will it contain both a mushroom and a tree, or more than one tree. Additionally, the starting cell and the destination cell are free of any obstacles.
If Masha can reach her grandmother, the first line of the output should display the maximum number of mushrooms she can collect. The subsequent m+n-1 lines should list the coordinates of the cells Masha visits in order, formatted as x_i y_i, for the path that allows her to collect the maximum number of mushrooms. If there are multiple paths with the same maximum number of mushrooms, output the path that prioritizes downward moves (prefer down over right moves when there is a choice).
If Masha cannot reach her grandmother, the output should be a single number .
Example 1
Example 2