• 51

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

You have just inherited of a small plot of land of width W and height H with some trees on it. You want to grow a forest, but you have only 1 seed to plant. Find the maximum number of trees after 33 years you can have by planting the seed at the best place.

Rules:
-Seeds need 10 years to grow into a tree.
-Trees produce 4 seeds around them after one year.
-Trees may already be present on your land. They will also produce seeds after one year.

Year 0 : X is your one and only seed and Y is a tree already present.

`.  .  .  .  .`

`.  X  .  .  .`

`.  .  .  .  .`

`.  .  .  .  .`

`.  .  .  .  Y`

Year 1 : Trees produce seeds after one year.

`.  .  .  .  .`

`.  X  .  .  .`

`.  .  .  .  .`

`.  .  .  .  X`

`.  .  .  X  Y`

Year 10 : Your seed is now a tree. Congratulations!

`.  .  .  .  .`

`.  Y  .  .  .`

`.  .  .  .  .`

`.  .  .  .  X`

`.  .  .  X  Y`

Year 11 : Your new tree starts to produce seeds after a year.

`.  X  .  .  .`

`X  Y  X  .  .`

`.  X  .  .  .`

`.  .  .  .  Y`

`.  .  .  Y  Y`

Year 12 : The old trees in the corner also keep spreading.

`.  X  .  .  .`

`X  Y  X  .  .`

`.  X  .  .  X`

`.  .  .  X  Y`

`.  .  X  Y  Y`

Year 33 : Finally you have a tiny forest of 21 trees!

`Y  Y  Y  X  .`

`Y  Y  Y  Y  Y`

`Y  Y  Y  Y  Y`

`X  Y  Y  Y  Y`

`.  Y  Y  Y  Y`

Maybe if you plant the seed at another place you can get a bigger forest in the end.
When you will find the best place, you will need to give the number of trees you get after 33 years.
Input
Line 1 : an integer W for the width of the parcel.
Line 2 : an integer H for the height of the parcel.
Next H lines : each line of the land, with trees (Y) or grass (.).
Output
Line 1 : an integer N for the number of trees you can have on your land after 33 years by planting your seed at the best place.
Constraints
1 <= W <= 40
1 <= H <= 40
Example
Input
```5
5
.....
.....
.....
.....
.....```
Output
`13`

A higher resolution is required to access the IDE