AddUmbrella

2022 HF Final · 2022-03-16 · by misof

2022 HF Final · 2022-03-16 · by misof · Brute Force, Simple Search, Iteration, String Manipulation

Show categories

Class Name: AddUmbrella

Return Type: int

Method Name: solve

Arg Types: (vector<string>)

Problem Statement

This is an ASCII-art party umbrella standing on the ground:

     ---+---
        |
        |
==================

The handle (the vertical line depicted using '|') can be arbitrarily long, but it must have at least one character and its bottom must touch the ground.

The canopy (the two horizontal lines depicted using '-') can be arbitrarily wide, but it must have at least one character and it must be the same length on both sides.

The second figure below shows another valid umbrella. Additionally, the letters 'X' show the area the umbrella protects from the rain: everything that is directly below a part of the canopy of the umbrella.

    --+--
    XX|XX
    XX|XX
    XX|XX
==============

You are given the String scene that contains a rectangular array of characters. These characters represent an ASCII-art view of a two-dimensional scene.

The last element of scene consists of '=' characters only and represents the ground.

All other elements consist of '.' and 'B' characters only. The character '.' represents an empty space and the character 'B' represents a bee that is hovering on the spot in that location. For example, below is a scene with three bees:

..........
...B......
..B.......
........B.
==========

Your task is to add an umbrella to the scene so that as many bees as possible are protected from the rain. The whole umbrella must fit into the scene, and it cannot overlap any bees. (In other words, each character changed when adding the umbrella must be a period.)

Return the maximum number of bees that can be protected from the rain. If there is no way of adding an umbrella into the given scene, return 0.

Constraints

scene will contain between 3 and 30 elements, inclusive.
Each element of scene will contain the same number of characters.
That number will be between 3 and 30, inclusive.
Each character in the last element of scene will be '='.
Each character in the rest of scene will be '.' or 'B'.

Examples

{"..........",
 "...B......",
 "..B.......",
 "........B.",
 "=========="}
Returns: 3

This is the scene from the problem statement. Below is one of several ways in which we can add an umbrella that protects all three bees. ..---+---. ...B.|.... ..B..|.... .....|..B. ==========

{"BBBBBBBBBB",
 "...B......",
 "..B.......",
 "........B.",
 "=========="}
Returns: 1

The bees in the top row now block many ways of building the umbrella. The best we can do is to protect one bee. Two different ways of doing so are shown below. BBBBBBBBBB BBBBBBBBBB -+-B...... ...B...... .|B....... ..B---+--- .|......B. ......|.B. ========== ==========

{"B.B.B.B.B.",
 ".B.B.B.B.B",
 "=========="}
Returns: 0

There is no way to add an umbrella to this scene, so we cannot protect any bees from the rain.

{"BBBBB.BBBB",
 "...B......",
 "..........",
 "..........",
 "=========="}
Returns: 0

Here we can add an umbrella, but regardless of how we do it, it won't protect any of these bees. Note that we are not allowed to add extra rows (or columns) to the scene.

{"..........",
 "BBBBB.BBBB",
 "...B......",
 "..........",
 "..........",
 "=========="}
Returns: 9

With an extra row of free cells (compared to the previous example) we now can build an umbrella. Remember that both sides of the umbrella's canopy must have the same length. Here it implies that we cannot protect the leftmost bee. .----+---- BBBBB|BBBB ...B.|.... .....|.... .....|.... ==========

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

Coding Area

Language: C++17 · define a public class AddUmbrella with a public method int solve(vector<string> scene) · 125 test cases · 2 s / 256 MB per case