Connection Status:
Competition Arena > Potatoes

Potatoes

SRM 831 · 2022-06-06 · by misof

SRM 831 · 2022-06-06 · by misof · Graph Theory
Class Name: Potatoes
Return Type: String[]
Method Name: plant
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

You have a small rectangular field. The field is somewhere in the mountains. The soil isn't that good and there's a lot of rocks in the soil.

The only thing that will grow in these conditions are potatoes. You now want to plant some.

For this purpose, you divided the field into a grid of unit squares. Some contain soil ('.'), others contain rocks ('#'). You are given the map of the field in the String[] field. You can only plant potatoes into soil.

Potatoes need some room to grow. Thus, no two potatoes can share the same square and no two potatoes can share squares that have a common side (i.e., horizontally and vertically adjacent squares).


Plant exactly N potatoes. Return the field with 'P' used for cells that now contain potatoes. Any valid solution will be accepted. If there is no valid solution, return an empty String[] instead. (That is, a String[] with zero elements.)

Notes

  • You are not allowed to (re)move any of the rocks on the field. That is, each '#' must remain a '#', you may only change some '.'s into 'P's.

Constraints

  • field will have between 1 and 50 elements, inclusive.
  • Each element of field will have between 1 and 50 characters, inclusive.
  • Each element of field will have the same number of characters.
  • Each character in field will be '.' or '#'.
  • N will be between 0 and 2,500, inclusive.
Examples
0)
{"........",
 "........",
 "........",
 "........"}
3
Returns: {"P.P.P...", "........", "........", "........" }

A nice field with no rocks. We want to plant three potatoes. There are plenty of ways to do it.

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

A field almost full of rocks, there is only room for at most four potatoes.

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

There are five soil squares, but planting potatoes on all five of them is not a valid solution. (Two potatoes would be in horizontally adjacent squares.)

3)
{".........",
 ".........",
 ".........",
 ".........",
 "........."}
23
Returns: {"P.P.P.P.P", ".P.P.P.P.", "P.P.P.P.P", ".P.P.P.P.", "P.P.P.P.P" }

The maximum number of potatoes one can plant onto an empty 5 x 9 field.

4)
{".........",
 ".........",
 ".........",
 ".........",
 "........."}
24
Returns: { }

The minimum number of potatoes that doesn't fit into this field.

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 Potatoes with a public method vector<string> plant(vector<string> field, int N) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous