MedievalCity

TCO07 Round 1C · 2007-03-07 · by Mike Mirzayanov

TCO07 Round 1C · 2007-03-07 · by Mike Mirzayanov · Graph Theory

Show categories

Class Name: MedievalCity

Return Type: int

Method Name: getDangerousBlocks

Arg Types: (vector<string>, int)

Problem Statement

A medieval city consists of square blocks, each of equal size, situated on a grid. The blocks form a connected figure with no holes. An example of such a city is shown in the picture below.

The red line shows the boundary of the city. Each block has a danger value that is assigned as follows. Blocks that have the city boundary as a side are called 0-dangerous. Blocks that are adjacent to 0-dangerous blocks and have not yet been assigned a danger value are called 1-dangerous. Two blocks are considered adjacent if they share a side. Blocks that are adjacent to 1-dangerous blocks and have not yet been assigned a danger value are called 2-dangerous blocks, and so on. In the picture above, all 0-dangerous and 1-dangerous blocks are colored dark gray.

We can represent a city as a string of letters 'R', 'L', 'U', 'D' (right, left, up, down) describing a walk along its boundary in the clockwise or counter-clockwise direction. Each letter represents the length of a single block's side. Multiple consecutive equal letters can be written using a simple compression method. An integer K that immediately follows a letter means that the letter is repeated K times. For example, the city in the picture above can be described by the string "LUUR7D4RDLDDDL7UURU2UU". Obviously there can be multiple strings that describe the same city.

You are given a String[] boundary and an int dangerBound. Concatenate all the elements of boundary to get the string description of a city. Return the number of i-dangerous blocks in the city where i <= dangerBound.

Constraints

boundary will contain between 1 and 50 elements, inclusive.
Each element of boundary will contain between 1 and 50 characters, inclusive.
The 0-th element of boundary will start with a letter.
Each element of boundary will contain only the letters 'R', 'L', 'U', 'D', and digits ('0'-'9').
Each sequences of digits in the concatenation of all the elements of boundary will be an integer without leading zeroes between 1 and 50, inclusive.
boundary will describe a correct closed boundary that does not touch or intersect itself.
dangerBound will be between 0 and 10, inclusive.

Examples

{"LURD"}
0
Returns: 1

This city contains only a single square block.

{"LUUR7D4RDLDDDL7UURU2UU"}
1
Returns: 44

The example from the problem statement.

{"L50U50R50D50"}
10
Returns: 1716

{"L50U50U50U50U50R50D50D50D50D50"}
7
Returns: 3744

{
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50L50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50D50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50R50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50",
"U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50U50"
}
10
Returns: 421916

Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MedievalCity with a public method int getDangerousBlocks(vector<string> boundary, int dangerBound) · 47 test cases · 2 s / 256 MB per case