ConquerMap | Topcoder Archive

Problem Statement

Various groups are occupying territory in a local region. We are going to record which group owns which land on a map. This map will be represented by a String[] with rows elements, each element containing cols characters. As time passes, the map will change based on troop movements. At the very beginning, our map will only contain '.' characters denoting lack of ownership. As time passes and land is acquired, the map will contain numerals ('0'-'9') denoting which group owns a particular piece of territory. At each time t, starting with time 0, the following actions occur in order:

1) Each character c of the map that is orthogonally adjacent to a numeral at the beginning of time t should become that numeral, unless there is a conflict. A conflict occurs when c is a numeral different from one of its orthogonal neighbors at the beginning of time t, or when at least 2 distinct numerals are orthogonally adjacent to c at the beginning of time t. In such a case, a battle occurs to determine the owner of the land. For each adjacent numeral i, compute
```
 battleScore(i) = t-entranceTime(i),
```
where entranceTime(i) is the entranceTime of numeral i (see next item). If c was not '.', also compute the battleScore for the numeral at c. The lowest battleScore determines the winner. If there is a tie for lowest, choose the lower numeral. The winning numeral is placed at c on the map.
2) times will denote when the numerals enter the map. Each element of times has the format (quotes for clarity) "row col entranceTime". If the entranceTime component of element k (0-based) of times is equal to t, place the numeral k in element row, character col of the map. This occurs regardless of the contents of the map at the given position.

Note that the entranceTime of a numeral never changes (regardless of position or time). Return the map after time endTime is complete.

Definition

Class:: ConquerMap
Method:: getMap
Parameters:: int, int, String[], int
Returns:: String[]
Method signature:: String[] getMap(int rows, int cols, String[] times, int endTime)
(be sure your method is public)

Constraints

rows will be between 2 and 50 inclusive.
cols will be between 2 and 50 inclusive.
endTime will be between 0 and 100 inclusive.
times will contain between 1 and 10 elements inclusive.
Each element of times will have the format (quotes for clarity) "row col entranceTime" where row is between 0 and rows-1 inclusive with no extra leading zeros, col is between 0 and cols-1 inclusive with no extra leading zeros, and entranceTime is between 0 and 100 inclusive with no extra leading zeros.
times will contain no duplicate entries.

Examples

{"0 0 0","2 2 0"}

Returns: { "00........",  "0.1.......",  ".111......",  "..1.......",  "..........",  "..........",  "..........",  "..........",  "..........",  ".........." }

After entering the map at time 0, both groups have expanded without opposition...

```
10
```
```
10
```
```
{"0 0 0","2 2 0"}
```
```
2
```
```
Returns: { "000.......",  "0011......",  "01111.....",  ".111......",  "..1.......",  "..........",  "..........",  "..........",  "..........",  ".........." }
```
The first battle has occurred at row 1 col 1, and 0 has won. The exact computation made was: battleScore(0) = 2 - 0 = 2 battleScore(1) = 2 - 0 = 2 battleScore(0) equals battleScore(1) but 0<1 so 0 takes the area.

{"5 5 0","5 5 3","17 17 4"}

Returns: { "00011111000..........",  "001111111000.........",  "0111111111000........",  "11111111111000.......",  "111111111111000......",  "1111111111111000.....",  "111111111111000......",  "11111111111000.......",  "0111111111000........",  "001111111000.........",  "00011111000..........",  ".000111000.......2...",  "..0001000.......222..",  "...00000.......22222.",  "....000.......2222222",  ".....0.......22222222",  "............222222222",  "...........2222222222",  "............222222222",  ".............22222222",  "..............2222222" }

{"0 20 0","20 20 0","0 0 0","20 0 0","5 5 60"}

Returns: { "222222220000000000000",  "222222222000000000000",  "222222222200000000000",  "2222222222.0000000000",  "222222222...000000000",  "22222222.....00000000",  "2222222.......0000000",  "222222.........000000",  "22222...........00000",  "2222.............0000",  "222...............000",  "2233.............1100",  "23333...........11110",  "333333.........111111",  "3333333.......1111111",  "33333333.....11111111",  "333333333...111111111",  "3333333333.1111111111",  "333333333311111111111",  "333333333111111111111",  "333333331111111111111" }

{"0 0 0","0 0 1","0 0 2","0 0 3"}

Returns: { "33",  "33" }

{"0 0 1","10 0 2","20 0 3","0 10 2","10 10 2","0 20 3",
 "10 20 4","20 10 4","20 20 5"}

Returns: { "000003333333333355555",  "000000333333333..5555",  "00000..3333333....555",  "0000....33333......55",  "000......333........5",  "10........3..........",  "11.......444.........",  "111.....44444.......6",  "1111...4444444.....66",  "11111.444444444...666",  "1111114444444444.6666",  "11111.444444444...666",  "1111...4444444.....66",  "111.....44444.......6",  "11.......444.........",  "1.........4..........",  "2....................",  "22........7..........",  "222......777........8",  "2222....77777......88",  "22222..7777777....888" }

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.