Connection Status:
Competition Arena > VegetableGarden

VegetableGarden

SRM 340 · 2007-02-20 · by Mike Mirzayanov

SRM 340 · 2007-02-20 · by Mike Mirzayanov · Graph Theory
Class Name: VegetableGarden
Return Type: int[]
Method Name: getMinDistances
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Your vegetable garden forms a rectangular grid of equal square plots. You've decided to inspect some of your plots. Starting at the top left corner, you will walk through the garden and return back to your starting point. All plots that lie inside the cycle of your path will be considered inspected. You are not allowed to walk inside the plots; you can only walk along their boundaries. Your path must not intersect itself. The boundaries are wide enough that you can walk along the same boundary multiple times without intersecting your own path.

You are given a String[] garden, where the j-th character of the i-th element represents the plot at row i, column j. The plots you would like to inspect are represented by uppercase 'I' characters. '.' characters represent plots you don't care about, and uppercase 'X' characters represent plots you must never inspect. Return a int[] where the i-th element is equal to the length of the shortest path that lets you inspect exactly i+1 plots marked with the letter 'I'. The number of elements in the return value must be equal to the number of 'I's in garden. Note that it is okay for '.' plots to be inspected, but 'X' plots must never be inspected.

Constraints

  • garden will contain between 1 and 50 elements, inclusive.
  • Each element of garden will contain only periods ('.'), uppercase 'I's and uppercase 'X's.
  • Each element of garden will contain an equal number of characters.
  • Each element of garden will contain between 1 and 50 characters, inclusive.
  • garden will contain between 1 and 10 characters that are not periods ('.').
Examples
0)
{"I"}
Returns: {4 }

Walk around the periphery of the plot.

1)
{"XX", 
 "XI"}
Returns: {8 }
2)
{"III", 
 "IXI",
 "III"}
Returns: {4, 6, 8, 10, 12, 14, 16, 18 }

An example of inspecting 8 plots is below.

3)
{"X.I", 
 ".I.", 
 "I.."}
Returns: {8, 10, 14 }
4)
{"IIXIIXIXII"}
Returns: {4, 6, 12, 14, 20, 26, 28 }

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

Coding Area

Language: C++17 · define a public class VegetableGarden with a public method vector<int> getMinDistances(vector<string> garden) · 132 test cases · 2 s / 256 MB per case

Submitting as anonymous