ConquerMap
SRM 193 · 2004-05-05 · by brett1479
SRM 193 · 2004-05-05 · by brett1479 · Simulation
Problem Statement
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.
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)
10
10
{"0 0 0","2 2 0"}
1
Returns: { "00........", "0.1.......", ".111......", "..1.......", "..........", "..........", "..........", "..........", "..........", ".........." }
After entering the map at time 0, both groups have expanded without opposition...
1)
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.
2)
21
21
{"5 5 0","5 5 3","17 17 4"}
10
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" }
3)
21
21
{"0 20 0","20 20 0","0 0 0","20 0 0","5 5 60"}
12
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" }
4)
2
2
{"0 0 0","0 0 1","0 0 2","0 0 3"}
100
Returns: { "33", "33" }
Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConquerMap with a public method vector<string> getMap(int rows, int cols, vector<string> times, int endTime) · 23 test cases · 2 s / 256 MB per case