DevuAndPlantingTrees
2015 TCO 1C · 2015-04-08 · by praveen123
Problem Statement
Devu has a garden in his back yard.
The garden can be seen as a grid with 2 rows and N columns.
You are given a description of the garden: a
Two cells are considered adjacent if they share a side or a corner. As you may know, whenever two trees grow in adjacent cells, they hinder each other's growth. Therefore, Devu would never plant a tree into a cell that is already adjacent to a cell with a tree. (This is also true for all the trees already present in his garden.)
Given the above rule, Devu wants to plant as many additional trees as possible. Return the largest possible number of trees Devu can have in his garden at the end.
Constraints
- N will be between 1 and 50, inclusive.
- garden will contain exactly 2 elements.
- Each element of garden will contain exactly N characters.
- Each character of each element of garden will be either '.' or '*'.
- No two of the already planted trees are in adjacent cells.
{"..", ".."}
Returns: 1
You can plant a single tree in either of the four available cells.
{"..", ".*"}
Returns: 1
You cannot plant any additional trees.
{"...",
"..*"}
Returns: 2
The garden already contains one tree in a corner. One optimal solution is to plant one additional tree in the opposite corner.
{".....*..........",
".*.......*.*..*."}
Returns: 7
{"....*.*.*...........*........",
"*..........*..*.*.*....*...*."}
Returns: 13
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DevuAndPlantingTrees with a public method int maximumTreesDevuCanGrow(vector<string> garden) · 67 test cases · 2 s / 256 MB per case