Statistics

Problem Statement for "Desertification"

Problem Statement

Desertification (the process of good land turning into desert) is a severe problem on Bob's island. Bob's island is a rectangular grid of cells. You are given a String[] island that shows the current state of Bob's island. The j-th character of the i-th element of island is 'D' if cell in row i, column j of the grid is desert and is 'F' if this cell is forest.

The desert spreads each year as follows:
  • If a cell is desert, it remains desert forever.
  • If a cell is forest and it is adjacent to at least one desert cell (in one of the four orthogonal directions), it becomes desert after one year.
  • Otherwise the cell remains forest for another year.
Return the number of desert cells after T years.

Definition

Class:
Desertification
Method:
desertArea
Parameters:
String[], int
Returns:
int
Method signature:
int desertArea(String[] island, int T)
(be sure your method is public)

Constraints

  • island will contain between 1 and 10 elements, inclusive.
  • Each element of island will contain between 1 and 10 characters, inclusive.
  • Each character in island will be 'D' or 'F'.
  • Each element of island will contain the same number of characters.
  • T will be between 1 and 1,000,000,000, inclusive.

Examples

  1. {"FFF", "FDF", "FFF"}

    1

    Returns: 5

    After one year, the island will be: FDF DDD FDF

  2. {"FFF", "FDF", "FFF"}

    2

    Returns: 9

    All cells will be desert after two years.

  3. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF"}

    3

    Returns: 90

  4. {"FFFFFFFFFD","FFFFFFFFFF","FFFFFFDFFF","FDFFFFFFFF","FFFDFFFFFF","FFFDFFFDFF","FFFFFFFFFF","FFFFFFFFFF","DDFFFFFDFF","FFFFDFFFFF"}

    3

    Returns: 96

  5. {"FD","DD","FF","FF","FD","DD","FF","DF","FF"}

    3

    Returns: 18

  6. {"FFFFFFFFFF","FFFFFFDFFF","DFDDFFFFFD","FFFFFFFFFF","FFFFFFFFFF","DFFFFFFDFF","FFFDFFFDFF","FFFDFFDDFF","DDFFFFFDDF","FDFDDDFFFD"}

    1

    Returns: 64

  7. {"FFFDFDF","DFFFFFF","FFFFFFF","FFDFFDF","FFFFFFF","FFFFFFF","FDFDDFF","FFFDDFF"}

    2

    Returns: 54

  8. {"FFFFFFFFFF","FDFFFFFDFD","FFFFFDFDFF","FDFDDFFFDF","DFFFFDDFFF","DFDDDDDDFF","FFFFFDDDDF","DFFFFFFDFF","FFDFDDDFFF","FDFFFFDFDD"}

    789630848

    Returns: 100

  9. {"DFFFFFFFFF","FFFFFFFFFF","FFFFFFFFFD","FFFFFFFFDF","FFFFFFFFFF","FFFFFDFFFF","FFFFFFFFFF","FFFFFFFFFF","FFFFFFFFFF","FFFFFFFFFF"}

    10

    Returns: 100

  10. {"D","F","D"}

    584975153

    Returns: 3

  11. {"FFDFDDDFFF","DDDFDDFDFF","FDDFFFFDDD","FFFDFDFDDF","FFFFDDDFDF","DFFDFFDDFD","DDFDFDFDFD","FFDFFFFDDD","FFDFDDFDFF","DFDFFFDFDF"}

    10

    Returns: 100

  12. {"FDFDFDDDDD","DDFDDDFDFD","DDFFDFDDFF","FFDDDDDDDF","DFFDDDDFDD","FDDDDFDDFD","DFDDDDDDDF","DDFFFDDDDD","DFFDFFDDDD","DDDDDDFDDF"}

    9

    Returns: 100

  13. {"FDFDFFDFDF","DDFFFFDDFD","FDDFFDFDFF","FDFFFFFDFF","DFDFFFFFFF","FFDDFFDDFD","FDFFDFDFDD","FDFFFFDFFF","FDFFFDDDFF","DFFFDFFFFD"}

    11

    Returns: 100

  14. {"DDDDDFDDDD","FDDFFDDFDD","DDDDDDFFDD","DDDFDDDDDF","DDFFDFFDDD","DDDDDDDDDD","FDDDDDDFDD"}

    6

    Returns: 70

  15. {"FFFFF","FFFFF","FFFFF","FFFFF","FFFFF","FFFFF"}

    979193317

    Returns: 0

  16. {"FFFFFFFFFF","FFFFFFFFFF","FFFFFFFFFF","FFFFFDDFFF","FFFFFFFFFF","FFFFFFFFFF","FFFFFFFFFD","FFFDDFFFFF","FFFFFFFFFF","FDFFFFFFFF"}

    9

    Returns: 100

  17. {"F","F","F","F","F"}

    2

    Returns: 0

  18. {"FDFFF","FFFFF","FFFFF","FFFFF"}

    1

    Returns: 4

  19. {"DFFFFDFFFD","FDFDFDFFFF","DFDFFFFDFF","DDFFFDFDFF","FFFDDDDDFD","DDFFDFFFFF","DFFDDFFDFF","FFFDFDFFFD","FFDFDFFFFF","DFFDFFFDFD"}

    7

    Returns: 100

  20. {"DFDDFFDDDD","DDFFFDDFDD","DDFDFFDFFF","FFFDFFDDFD","FDDDDDDDFD","DDDFFFDFDD","DDDDDDDFDF","DDDDDDDDDD","DDFFFDFDDF","DFDFDFDFDF"}

    74026839

    Returns: 100

  21. {"D"}

    2

    Returns: 1

  22. {"F","F","F","F","F","F"}

    1

    Returns: 0

  23. {"FF"}

    1

    Returns: 0

  24. {"FDFFFDDDDF","DDDDDFFFDD","DDDDDDFDFD","FFDDDDDDFF","FDDFDDDDDF","DDDDDFDDFD","FDFFFFFDDF","FDDFDFDDDD","FDDDFDDDDF","DDFFDFDDFD"}

    488786973

    Returns: 100

  25. {"FF","FF","DF","FD"}

    3

    Returns: 8

  26. {"F","F","F","F","D","F","F","D","F"}

    2

    Returns: 7

  27. {"FFFF","FFFF"}

    1

    Returns: 0

  28. {"FFFFFFF","FFFFFFF","FFFDFFF","FFFFFFF","FFFFFFF"}

    2

    Returns: 13

  29. {"FFFFFF","FFFFFF","FFFFDD"}

    2

    Returns: 9

  30. {"DFFDDDFFFF","DDDFFFDDFD","FFFFDFFFFD","FFFFFDFFFF","FDFDFDDFFF","FFFFFFDFFD","FDFFDDDFFF","FDFDDDFFFF","FFDFDDFFDD","FFFDDDFFFF"}

    890892108

    Returns: 100

  31. {"FFDFFFFFFF","FFDFFFFFFF","FFFFDFFFFF","FFFFDDFFFF","FFFFFFFFFF","FFFFFFDFFF","FFFFFFFFFF","FFDFFFFFFF","FFFFFFFFFF","FFFFFFFFFF"}

    88198027

    Returns: 100

  32. {"FFFFFFFDFF","FFFFDFFFFF","FFFFFFFFFF","FFFDFFFDFF","DFFFFFFFFF","FFFFFFFDFD","FFFFFFFFFF","FFFFFFFFFF","FDFFFFFFFF","FFFFFFFFFF"}

    688303277

    Returns: 100

  33. {"FFF"}

    1

    Returns: 0

  34. {"DFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF"}

    17

    Returns: 99

  35. {"FFFFF", "FFDFF", "FFFFD", "FFFFF", "FFFFF"}

    2

    Returns: 17

    In this example, the picture on the left represents the initial state for Bob's island. After two years, the island state will become the picture on the right (dark green represents forest and pale yellow represents desert). Thus, the number of desert cells after 2 years is 17.

  36. {"FFFFFF", "FFFFFF", "FFFFFF", "FFFFFF"}

    1000000000

    Returns: 0

  37. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF"}

    3

    Returns: 90

  38. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF"}

    98765432

    Returns: 100

  39. {"FFFFFF", "FFFFFF", "FFFFFF", "FFFFFF" }

    1000000000

    Returns: 0

  40. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFDFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    98765432

    Returns: 100

  41. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    3

    Returns: 90

  42. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    1000000000

    Returns: 0

  43. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    99765432

    Returns: 100

  44. {"FFFFF", "FFFFF", "FDFDF", "FDDDF", "FDDDD" }

    1000000000

    Returns: 25

  45. {"DFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    1000000000

    Returns: 100

  46. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    98765432

    Returns: 100

  47. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    1000000000

    Returns: 100

  48. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    1000000000

    Returns: 0

  49. {"DFFFFF", "FFFFFF", "FFFFFF", "FFFFFF" }

    1000000000

    Returns: 24

  50. {"FFFFF", "FFFDF", "DFFFF" }

    2

    Returns: 14

  51. {"FFFFF", "FFFFF", "FFFFF", "FFFFF", "FFFFF", "FFFDF", "FFFFF", "FFFFF", "FFFFF" }

    1000000000

    Returns: 45

  52. {"DDDDDDDDDD", "FFFFFFFFFF", "DDDDDDDDDD", "FFFFFFFFFF", "DDDDDDDDDD", "FFFFFFFFFF", "DDDDDDDDDD", "FFFFFFFFFF", "DDDDDDDDDD", "FFFFFFFFFF" }

    1000000000

    Returns: 100

  53. {"FFDDD" }

    6

    Returns: 5

  54. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFD" }

    1000000000

    Returns: 100

  55. {"FFDD" }

    10

    Returns: 4

  56. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    98765432

    Returns: 90

  57. {"DDDDD", "DDDDD", "DDDDD", "DDDDD" }

    1000000000

    Returns: 20

  58. {"FFFFFFFFF", "FFFFFDFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF" }

    1000000000

    Returns: 90

  59. {"FFFFFF", "FFFFDF", "FFFFFF" }

    1000000000

    Returns: 18

  60. {"FFF", "FFF", "FFF" }

    100000000

    Returns: 0

  61. {"FDFF" }

    30

    Returns: 4

  62. {"FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF", "FFFFFFFFF" }

    1000000000

    Returns: 0

  63. {"FFFFF", "FFFFF", "FFFFF", "FFFFF", "FFFFF" }

    1000000000

    Returns: 0

  64. {"DFD", "FDF", "DFD" }

    1000000000

    Returns: 9

  65. {"FDDDDD" }

    1

    Returns: 6

  66. {"FFFFFFFD", "FFFFFFFD", "FFFFFFFD" }

    10000000

    Returns: 24

  67. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    98765432

    Returns: 100

  68. {"FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    1000000000

    Returns: 100

  69. {"DF" }

    1000000000

    Returns: 2

  70. {"DFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    13

    Returns: 85

  71. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    998765432

    Returns: 100

  72. {"FFD", "FFD" }

    1000

    Returns: 6

  73. {"DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD" }

    2

    Returns: 50

  74. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFD" }

    10

    Returns: 64

  75. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "DFFFFFFFFF" }

    1000

    Returns: 100

  76. {"FFFFF", "FFFFD" }

    100

    Returns: 10

  77. {"FFFFF", "FFDFF", "FFFFD", "FFFFF", "FFFFF" }

    2

    Returns: 17

  78. {"DFF", "FDF", "FFD", "FFF", "FFF", "FFF", "DDD" }

    1000000000

    Returns: 21

  79. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFD" }

    100

    Returns: 100

  80. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFD" }

    10000

    Returns: 100

  81. {"DFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    98765432

    Returns: 100

  82. {"FFFF", "FDFD", "FFFD" }

    1

    Returns: 9

  83. {"FFFD", "FFDD", "FFFD", "DFFF", "DDDD", "DDDD", "FFDD" }

    100000

    Returns: 28

  84. {"DFFF", "DFFF", "DFFF" }

    1

    Returns: 6

  85. {"D" }

    1000000000

    Returns: 1

  86. {"FFFF", "FFFF" }

    300

    Returns: 0

  87. {"FFFFFFFFFD", "FFFFFFFFFF" }

    1

    Returns: 3

  88. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    98765432

    Returns: 0

  89. {"FFFDFFFDF" }

    1

    Returns: 6

  90. {"DFFFD", "DFFFD", "FFFFF" }

    1

    Returns: 10

  91. {"FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF" }

    100000000

    Returns: 100

  92. {"DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF", "DDDDDFFFFF" }

    100000000

    Returns: 100

  93. {"DDDD", "DDDD" }

    1000000000

    Returns: 8

  94. {"FFF", "FDF", "FDF" }

    1000000000

    Returns: 9

  95. {"FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD", "FFFFD" }

    2

    Returns: 30

  96. {"DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD", "DDDDDDDDD" }

    999999999

    Returns: 81

  97. {"FFFDF", "FFDFF", "FDFDF" }

    2

    Returns: 14

  98. {"DFFF", "FFFF", "FFFF", "FFFF" }

    1

    Returns: 3

  99. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFD" }

    10000000

    Returns: 100

  100. {"FFF", "FFF", "FFF" }

    1

    Returns: 0

  101. {"DFFFF", "FFFFF", "FFFFF", "FFFFF", "FFFFF" }

    6

    Returns: 22

  102. {"FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "FFFFFFFFFF", "DFFFFFFFFF" }

    20

    Returns: 90

  103. {"DFF", "FFF", "FFF" }

    5

    Returns: 9

  104. {"FFFFFDFFFF", "FDFDFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "DDFFFFFFFF", "FFFFFFFFFD", "FFFFFFFFFF", "FFFFFFFDFF", "FFFFFFFDFF", "FFFFDDFFFF" }

    100000000

    Returns: 100

  105. {"FF", "FD", "DD" }

    100

    Returns: 6

  106. {"FFFD" }

    98765432

    Returns: 4

  107. {"D", "F", "F", "F", "F", "F", "F", "F", "F", "F" }

    7

    Returns: 8

  108. {"DDDDDDDDDD", "DDDDDDDDDD", "DDDDDDDDDD", "DDDDDDDDDD", "DDDDDDDDDD" }

    2

    Returns: 50

  109. {"FDFDFDFDFD", "FDFDFDFDFD", "FDFDFDFDFD", "FDFDFDFDFD" }

    1000000000

    Returns: 40

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: