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 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

Solve it

A higher resolution is required to access the IDE