Coastlines
SRM 764 · 2019-08-09 · by erinn
Problem Statement
You are given a String[] map depicting the layout of several islands. A '.' indicates water, while 'X' indicates land. Two cells that are adjacent horizontally or vertically are considered part of the same island. Assume that all area outside the bounds of the given map is all water.
Any place where a land cell is adjacent, horizontally or vertically, to water, is called a coastline. A single land cell may have as many as four units of coastline. The following examples have 4, 6, 8 and 8 units of coastline, respectively:
.... .... .... .... .X.. .X.. .X.. .XX. .... .X.. .XX. .XX. .... .... .... ....
Find the total length of coastline of each island, and return the largest of these lengths.
Constraints
- map will contain between 1 and 50 elements.
- Each element of map will contain between 1 and 50 characters.
- Each element of map will contain the same number of characters.
- Each character of each element of map will be 'X' or '.'.
{"...",
".X.",
"..."}
Returns: 4
Example from the problem statement. The single land cell is bounded on all four sides by water.
{".XX",
".X.",
"..."}
Returns: 8
Similar to an example in the problem statement, the total coastline is 8.
{"."}
Returns: 0
There's no coastline at all.
{"XX"}
Returns: 6
{".XX...",
"XX...X",
"X...XX",
"......",
".XXXX."}
Returns: 12
Here, there are multiple islands, with varying coastline lengths.
{"XXX",
"X.X",
"XXX"}
Returns: 16
This island has a lake inside it, but that internal "coast" also counts.
{"XXXXX",
"X...X",
"X.X.X",
"X...X",
"XXXXX"}
Returns: 32
An island in a lake inside an island, is a separate landmass.
Submissions are judged against all 26 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Coastlines with a public method int longest(vector<string> map) · 26 test cases · 2 s / 256 MB per case