EnlargeTheCave

SRM 775 · 2020-01-15 · by misof

SRM 775 · 2020-01-15 · by misof · Graph Theory, Recursion

Show categories

Class Name: EnlargeTheCave

Return Type: String[]

Method Name: enlarge

Arg Types: (vector<string>, int)

Problem Statement

You are given the String[] cave with the map of a cave: '.' is cave floor, '#' is rock, and 'K' is a kobold hiding in the rock. The cave is 4-connected: a person who can move only up, down, left or right can go from any '.' to any other '.'. Kobolds can also move up, down, left, or right, and they can only step onto cave floor (they cannot walk through rocks). Currently, no kobold can enter the cave floor.

You are also given the int desiredArea. Your task is to enlarge the cave by excavating some rocks (i.e., changing some '#'s into '.'s) so that its new area becomes exactly desiredArea. You must not let any kobold enter your cave. The new cave must still be 4-connected.

Return a String[] with the map of the excavated cave. Any valid solution will be accepted. If there is no solution, return an empty String[].

Constraints

cave will contain between 1 and 50 elements, inclusive.
All elements of cave will have the same number of characters, and that number will be between 1 and 50, inclusive.
Each character in cave will be '.', '#', or 'K'.
There will be at least one '.' in cave.
desiredArea will be between the current number of '.'s in cave and the total number of characters in cave, inclusive.
As described in the statement, the cave in cave will be 4-connected and no kobold will be able to enter it.

Examples

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

Currently there is only a cave with area 1. The example output shows one possible way how to enlarge it into a cave with area 7. ... ..# ..#

{".##",
 "##K",
 "###"}
5
Returns: {"..#", ".#K", "..#" }

..# .#K ..#

{".##",
 "##K",
 "###"}
6
Returns: { }

We cannot make a cave with area 6 without releasing the kobold into it.

{"###K########",
 "#.#K########",
 "..#K########",
 "############"}
10
Returns: { }

Even though there is a lot of rock on the right, we have to extend the cave we already have, and we cannot extend it into the right part without releasing the kobolds. The largest area we can produce here is 9.

{"###############",
 "###############",
 "##K###..####K##",
 "######..#######",
 "###############",
 "##K#########K##",
 "###############",
 "###############"}
82
Returns: {"...............", "..#.........#..", ".#K#.......#K##", "###.........###", "###.........###", "##K#.......#K##", "###.........###", "#............##" }

............... ..#.........#.. .#K#.......#K## ###.........### ###.........### ##K#.......#K## ###.........### #............##

{"#K#K###..###K#K##"}
6
Returns: {"#K#K#......#K#K##" }

This is the largest cave we can make in this particular setting. Excavating any more rock would release a kobold into the cave.

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

Coding Area

Language: C++17 · define a public class EnlargeTheCave with a public method vector<string> enlarge(vector<string> cave, int desiredArea) · 114 test cases · 2 s / 256 MB per case