Statistics

Problem Statement for "DevuAndPlantingTrees"

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 String[] garden with 2 elements, each containing N characters. The character '.' represents an empty grid cell, and the character '*' a cell that contains a tree.

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.

Definition

Class:
DevuAndPlantingTrees
Method:
maximumTreesDevuCanGrow
Parameters:
String[]
Returns:
int
Method signature:
int maximumTreesDevuCanGrow(String[] garden)
(be sure your method is public)

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.

Examples

  1. {"..", ".."}

    Returns: 1

    You can plant a single tree in either of the four available cells.

  2. {"..", ".*"}

    Returns: 1

    You cannot plant any additional trees.

  3. {"...", "..*"}

    Returns: 2

    The garden already contains one tree in a corner. One optimal solution is to plant one additional tree in the opposite corner.

  4. {".....*..........", ".*.......*.*..*."}

    Returns: 7

  5. {"....*.*.*...........*........", "*..........*..*.*.*....*...*."}

    Returns: 13

  6. {".....*..*..........*............................*", "*..*.............*...*.*.*.*..*.....*.*...*...*.."}

    Returns: 23

  7. {".","."}

    Returns: 1

  8. {"..",".."}

    Returns: 1

  9. {"*..","..."}

    Returns: 2

  10. {"....","*..."}

    Returns: 2

  11. {"*....","....*"}

    Returns: 3

  12. {"....*.",".*...."}

    Returns: 2

  13. {".......","*......"}

    Returns: 4

  14. {"*.......","...*...."}

    Returns: 4

  15. {"*........","...*.*.*."}

    Returns: 4

  16. {"..*.......","......*.*."}

    Returns: 5

  17. {"....*.....*","..*........"}

    Returns: 6

  18. {".....*...*..",".......*...*"}

    Returns: 6

  19. {"..*....*.....",".....*......."}

    Returns: 6

  20. {"..*..*........","..........*..*"}

    Returns: 6

  21. {"..*...*.*.*....","*...*.......*.*"}

    Returns: 8

  22. {"..............*.",".....*..*..*...."}

    Returns: 6

  23. {"...*.*.*.........","*.........*..*.*."}

    Returns: 7

  24. {"*.*....*.....*.*..","...........*......"}

    Returns: 9

  25. {"....*..*...........",".*.......*..*.*...."}

    Returns: 8

  26. {"..*.*.*.*...*.......","...............*.*.."}

    Returns: 10

  27. {".....*...........*.*.","..*....*.*...*.*....."}

    Returns: 10

  28. {"........*.......*....*",".*.*..*....*.........."}

    Returns: 9

  29. {"...*.*..............*..","........*...*.*.*......"}

    Returns: 11

  30. {".....*..................","*.*....*....*.*..*...*.*"}

    Returns: 11

  31. {"...........*......*......","..*...........*.....*..*."}

    Returns: 11

  32. {"......*.....*.*..*.*......",".*......*.............*.*."}

    Returns: 11

  33. {".*.*......*..*......*.....*","......*.*........*....*.*.."}

    Returns: 12

  34. {"..*...*........*...*..*.*.*.","........*..*.*.............."}

    Returns: 13

  35. {".*............*...*..*.....*.","...*.*.*....*..........*....."}

    Returns: 13

  36. {"..........*.*.......*......*..","*.*.*.........*...*.....*....."}

    Returns: 15

  37. {"*.*........*..*..........*....*","....*....*......*.*..*........."}

    Returns: 14

  38. {"...*........*..*...........*....","*.....*..........*...*.*.*...*.*"}

    Returns: 15

  39. {".*...*.*......*......*...........",".................*.*...*.....*..."}

    Returns: 15

  40. {".......*.*.*.*.......*...*.*...*..","*.*..............*................"}

    Returns: 17

  41. {".*.............*...*..........*..*.","....*..*..*..*...*......*..*......."}

    Returns: 13

  42. {"...*....*..*........*...*.....*....*",".*...*.......*..............*......."}

    Returns: 16

  43. {"..*.....*.*..............*...*.....*.","....*.*.....*.....*....*........*...."}

    Returns: 17

  44. {"*...*....*.*.....*.*....*.....*....*.*","..*...........*......*..........*....."}

    Returns: 17

  45. {".*...*.....*.*........*........*.....*.","...*.....*.....*.*..*......*.*...*.*..."}

    Returns: 18

  46. {"...*..............*..*.............*....","......*.*.*..*.................*......*."}

    Returns: 17

  47. {"..*.......*...*.....*.*.....*.*..........","......*.........*..................*.*.*."}

    Returns: 20

  48. {".........*..*...*........*......*.........",".*...*.*......*...*....*....*.*..........*"}

    Returns: 19

  49. {"...*...*..*...*.*.*.....................*.*",".*...*..............*.*..........*..*......"}

    Returns: 20

  50. {"*...........*..............*..*..........*..","...*..*.*.*....*...*..*..*.............*...*"}

    Returns: 19

  51. {".........................*.*.........*.......","*.*.*..*.....*.*...*...*.......*.*.*.....*..*"}

    Returns: 22

  52. {"*...*...*...*.*.............*.*...*.*..*.*..*.","..*...*...*.....*.*...*......................."}

    Returns: 22

  53. {"....*...*...*...*..*............*.....*..*..*..","*.*...................*..*.*..*...*.*.........."}

    Returns: 21

  54. {"...*..*.*.*...*......*..*.....*..*.......*.*....","*...........*...*.*........*........*.........*."}

    Returns: 19

  55. {"........*.*.*..*....*.*.*.........*..*....*......","*..*.............*..........*.*.........*......*."}

    Returns: 21

  56. {".*..*.....*................*..................*...",".............*..*..*.*..*.....*...*...*.*...*...*."}

    Returns: 21

  57. {".", "." }

    Returns: 1

  58. {"*", "." }

    Returns: 1

  59. {"....*.*.*...........*........", "*..........*..*.*.*....*...*." }

    Returns: 13

  60. {"...", "*.." }

    Returns: 2

  61. {".....*..*..........*............................*", "*..*.............*...*.*.*.*..*.....*.*...*...*.." }

    Returns: 23

  62. {".*", ".." }

    Returns: 1

  63. {".", "*" }

    Returns: 1

  64. {"...", "..*" }

    Returns: 2

  65. {"...", "..." }

    Returns: 2

  66. {"*..", "..." }

    Returns: 2

  67. {"...*", "...." }

    Returns: 2

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: