TopCoder problem "VegetableGarden" used in SRM 340 (Division I Level Three)

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.



Method signature:int[] getMinDistances(String[] garden)
(be sure your method is public)


-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 ('.').


Returns: {4 }
Walk around the periphery of the plot.
Returns: {8 }

Returns: {4, 6, 8, 10, 12, 14, 16, 18 }
An example of inspecting 8 plots is below.

Returns: {8, 10, 14 }
Returns: {4, 6, 12, 14, 20, 26, 28 }

Problem url:

Problem stats url:


Mike Mirzayanov


PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Graph Theory