Connection Status:
Competition Arena > AddFlowers

AddFlowers

2022 TCO Parallel 2B · 2022-04-14 · by misof

2022 TCO Parallel 2B · 2022-04-14 · by misof · Greedy
Class Name: AddFlowers
Return Type: String[]
Method Name: add
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You have a rectangular lawn.

The lawn is divided into a grid of unit square cells. Some cells contain a flower, others contain only grass.

You are given the String[] lawn that describes the current lawn. Each character in lawn represents one cell: 'F' is a flower, '.' is grass.


Two flowers are friends if they grow in cells that are horizontally or vertically adjacent.

A flower looks alone if it has fewer than two friends.


Plant zero or more additional flowers so that no flower looks alone.

Note that this requirement also applies to the new flowers planted by you: on the final lawn the new flowers must not look alone either.

You may not remove or relocate any of the existing flowers. You are not required to plant the smallest possible number of new flowers, but there is an upper bound: you may not plant more than 3*N new flowers, where N is the current number of flowers on the lawn.


Return a String[] with the final arrangement of flowers on your lawn.

Notes

  • You are not allowed to plant new flowers outside the lawn. The returned String[] must have the same dimensions as lawn.
  • You may assume that for the given constraints a solution always exists.

Constraints

  • lawn will contain between 2 and 50 elements, inclusive.
  • Each element of lawn will contain between 2 and 50 characters, inclusive.
  • Each element of lawn will contain the same number of characters.
  • Each character in lawn will be 'F' or '.'.
Examples
0)
{"..........",
 "...FFFF...",
 "..FF......",
 "..F...F...",
 "..FFFFF...",
 ".........."}
Returns: {"..........", "...FFFF...", "..FF..F...", "..F...F...", "..FFFFF...", ".........." }

There are two flowers that look alone: both ends of the "chain". We can easily stop that by placing one more flower between them. The new flower does not look alone either, so everything is in order. (There are many other valid solutions that add more than one new flower.)

1)
{"F.F.F.",
 ".F.F.F",
 "F.F.F."}
Returns: {"FFFFFF", "FFFFFF", "FFFFFF" }

As there are 9 flowers on this lawn, we may plant up to 3*9 = 27 new ones. This gives us enough leeway to simply fill the whole lawn with flowers. On the full lawn each flower has at least two friends.

2)
{"..........",
 "...FFFF...",
 "..FF.FFF..",
 "..F.F.F...",
 "..FF.FF...",
 "....F....."}
Returns: {"..........", "...FFFFF..", "..FF.FFF..", "..FFF.FF..", "..FFFFF...", "...FF....." }
3)
{"......",
 "......"}
Returns: {"......", "......" }

Here the only valid solution is to leave the lawn untouched.

4)
{
"F...........F...........F",
".........................",
".........................",
".........................",
".........................",
".........................",
"F...........F...........F",
".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
"F...........F...........F"}
Returns: {"FF..........FF.........FF", "FF..........FF.........FF", ".........................", ".........................", ".........................", ".........................", "FF..........FF.........FF", "FF..........FF.........FF", ".........................", ".........................", ".........................", ".........................", "FF..........FF.........FF", "FF..........FF.........FF" }

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

Coding Area

Language: C++17 · define a public class AddFlowers with a public method vector<string> add(vector<string> lawn) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous