Tiny Forest
Difficulty : Medium
Community success rate: 72%
Approved by Timinator llllllllllllllllllllllllllllll FredericLocquet
A higher resolution is required to access the IDE
- 40
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 onlyRules:
-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 (. ).
Line 2 : an integer H for the height of the parcel.
Next H lines : each line of the land, with trees (
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
1 <= H <= 40
Example
Input
5 5 ..... ..... ..... ..... .....
Output
13
A higher resolution is required to access the IDE