Connection Status:
Competition Arena > IslandInALake

IslandInALake

SRM 794 · 2020-11-24 · by misof

SRM 794 · 2020-11-24 · by misof · Graph Theory, Search
Class Name: IslandInALake
Return Type: int
Method Name: build
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given the String[] country that contains a rectangular map of a region. The map is divided into cells, and each cell is either water ('.') or land ('#'). All cells on the border of the map are water cells.

Boats can travel between water cells by moving in the four cardinal directions ("up, down, left, right"). Two water cells belong to the same body of water if a boat can reach one of those cells from the other (without going onto land). The body of water that contains the border of the map is the sea, all other bodies of water are lakes.

Rabbits can travel between land cells by moving in eight directions (not just horizontally and vertically, but also diagonally). Two land cells belong to the same island if a rabbit can reach one of those cells from the other (without going into water).

You have just inherited an unlimited amount of soil. You want to use it to build your own island somewhere in this region. You really dislike saltwater, so you want to build your island on one of the lakes (and not in the sea). Obviously, your island must be a single island (as defined above) and it must not touch any of the existing islands.

Compute and return the largest possible number of cells that can form your new island-in-a-lake. Return 0 if it's not possible to build a new island in a lake.

Constraints

  • country will contain between 1 and 50 elements, inclusive.
  • Each element of country will contain between 1 and 50 characters.
  • All elements of country will contain the same number of characters.
  • Each character in country will be either '.' or '#'.
  • Each character on the boundary of country (i.e., first+last row+column) will be '.'.
Examples
0)
{"......",
 "......",
 "......",
 "......",
 "......"}
Returns: 0

Only the sea. No islands, no lakes, nowhere to build our new island-in-a-lake.

1)
{".......",
 "..##...",
 ".##..#.",
 "..#.#..",
 "......."}
Returns: 0

Two islands in the sea. One has five cells, the other one has two. No lakes anywhere.

2)
{".......",
 ".####..",
 ".#...#.",
 ".#####.",
 "......."}
Returns: 0

One island with a lake that consists of three cells. The lake is too narrow, we cannot build any new island inside the lake.

3)
{"..........",
 ".####.....",
 ".#...#....",
 ".#...#....",
 ".#...#....",
 ".#####....",
 ".........."}
Returns: 1

This time we can build a single-cell island inside the lake. The new map would then look as follows (with the new island denoted by an asterisk): .......... .####..... .#...#.... .#.*.#.... .#...#.... .#####.... ..........

4)
{"............",
 ".####.#####.",
 ".#...#....#.",
 ".#........#.",
 ".#...#....#.",
 ".#########..",
 "............"}
Returns: 2

A bigger island, still with a single lake. There are now multiple ways to build a new island on this lake, including one way of building an island that consists of two adjacent cells. ............ .####.#####. .#...#....#. .#.....**.#. .#...#....#. .#########.. ............

5)
{"...........",
 "..#####....",
 "..#....##..",
 "..#.....#..",
 "...#.....#.",
 "..#.#....#.",
 ".#...#...#.",
 "..###.###..",
 "..........."}
Returns: 3

This map contains a single island and there are two lakes on this island. One is too small to build on, the other can contain a new island of size 3 as shown below. ........... ..#####.... ..#....##.. ..#..*..#.. ...#..*..#. ..#.#..*.#. .#...#...#. ..###.###.. ...........

6)
{"...........",
 ".#########.",
 ".#.......#.",
 ".#.#####.#.",
 ".#.#...#.#.",
 ".#.#...#.#.",
 ".#.#...#.#.",
 ".#.#####.#.",
 ".#.......#.",
 ".#########.",
 "..........."}
Returns: 1

We can build a 1-cell island in the center of this map. The lake that contains it is actually a lake on an island that is on a lake on an island, but we do not care about that. Any lake (i.e., any body of water other than the sea) can be used for building.

7)
{"...........",
 ".#########.",
 ".#.......#.",
 ".#.#####.#.",
 ".#.#...#...",
 ".#.#...#.#.",
 ".#.#...#.#.",
 ".#.###.#.#.",
 ".#.......#.",
 ".#########.",
 "..........."}
Returns: 0

This map looks similar to the previous one, but this one actually contains two separate islands, and all water is sea so we cannot build our island anywhere.

8)
{"...........",
 ".#########.",
 ".#.......#.",
 ".#.......#.",
 ".#.......#.",
 ".#.......#.",
 ".#.......#.",
 ".#.......#.",
 ".#...#...#.",
 ".#.......#.",
 ".#.......#.",
 ".#.......#.",
 ".#########.",
 "..........."}
Returns: 31

The optimal new island is shown below. Notice how it goes around the existing tiny island. ........... .#########. .#.......#. .#.*****.#. .#.*****.#. .#.*****.#. .#.*****.#. .#.*...*.#. .#.*.#.*.#. .#.*...*.#. .#.*****.#. .#.......#. .#########. ...........

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

Coding Area

Language: C++17 · define a public class IslandInALake with a public method int build(vector<string> country) · 30 test cases · 2 s / 256 MB per case

Submitting as anonymous