• 14

## Learning Opportunities

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

## Goal

You just inherited 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
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