Desertification | Topcoder Archive

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

```
{"FFF",
 "FDF",
 "FFF"}
```
```
1
```
```
Returns: 5
```
After one year, the island will be: FDF DDD FDF
```
{"FFF",
 "FDF",
 "FFF"}
```
```
2
```
```
Returns: 9
```
All cells will be desert after two years.
```
{"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.

{"FFFFFF",
 "FFFFFF",
 "FFFFFF",
 "FFFFFF"}

1000000000

Returns: 0

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

Returns: 90

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

98765432

Returns: 100

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.