Practice Optimization and Simulation with the exercise "Tiny Forest"

Learning Opportunities

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

Statement

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

Solve it

A higher resolution is required to access the IDE