Tree Cutting

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 2.5s

Memory limit: 64M

Author:

Xyene

Problem type

Tatsumi and Mine have decided to go out and buy a nice fir tree to celebrate their first holiday season together. They've headed to a nearby forest, and are now observing a gathering of trees $R$ $R$ rows by $C$ $C$ columns $(2 \le R, C \le 10)$ $(2 \leq R, C \leq 10)$ . Each tree has a height $h$ $h$ , and they want to take the tallest one home. If multiple trees satisfy the condition of tallest, they would like to pick the one closest to them in regard to Euclidean distance. The layout of the forest is such that no pair of tallest trees will ever be equidistant to Tatsumi and Mine.

However, the trees are packed so tight that to get to the tallest tree they may have to ~~blast~~ cut their way through a number of trees. Being conscious of the environment, they wish to minimize the total heights of the trees they clear. Knowing that they can only walk in cardinal directions, how many trees must they remove to arrive at their desired tree? The sum of the heights of the trees you cut must be the minimal over all possible sets of trees to cut to get to the tallest tree. Additionally, you should also minimize the number of trees summing to that minimal height in the event of a tie.

Scoring

For $\dfrac{2}{3}$ $\frac{2}{3}$ of the test cases, all trees will have one of only two possible $h$ $h$ values. For the rest, $1 \le h \le 9$ $1 \leq h \leq 9$ .

Input Specification

The first line will contain the integers $R$ $R$ and $C$ $C$ , separated by a single space.
The next $R$ $R$ lines will contain $C$ $C$ space-delimited integers $h$ $h$ , the height of the tree at $(C, R)$ $(C, R)$ .
A . denotes that there is no tree at that position, and the couple start off at the position marked with an X.

Output Specification

One integer, the number of trees Tatsumi and Mine will have to remove to get to their desired tree.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation of Output for Sample Input 1

As in $\dfrac{2}{3}$ $\frac{2}{3}$ of the test cases, trees only come in 2 sizes: $2$ $2$ and $3$ $3$ . Therefore, the couple are after a tree where $h=3$ $h = 3$ . Two trees satisfy this condition, but the one in the top-right corner is the closest to their starting point. To arrive at it, 2 trees of $h=2$ $h = 2$ must be cut down.

Sample Input 2

Copy

4 8
1 1 1 1 1 1 1 9
. . 1 1 5 1 3 4
. . . . . . . .
X . . 8 7 6 . .

Sample Output 2

Copy

Explanation of Output for Sample Input 2

The tallest tree is that where $h=9$ $h = 9$ , and to arrive at it 3 trees of $h=1$ $h = 1$ must be cut. Alternatively, one tree of $h=4$ $h = 4$ could be cut, but that does not minimize the heights of the trees cut as $4 > 1 + 1 + 1$ $4 > 1 + 1 + 1$ .

Comments

1

nullptr commented on Dec. 26, 2014, 1:21 a.m.

In Sample Output 1 we are minimizing the number of trees cut; in Sample Output 2 we are minimizing the heights of the trees cut.

2

FatalEagle commented on Dec. 26, 2014, 1:49 a.m.

We are trying to minimize the sum of heights, but we do not actually have to output this minimal sum (it is a bit strange, I know).

Instead, after we have the minimal height, call it $X$ $X$ , we want to find the minimum number of trees on a path from the starting point to the target tree that sum to the minimum $X$ $X$ .