TopCoder problem "Orchard" used in SRM 167 (Division II Level Three)

Problem Statement

     My orchard is arranged in a square, with the rows and columns numbered 1, 2, ..., n. I need software to choose the location where the next tree should be planted.

I want the next tree not to be interfered with by existing trees or by the activities of the neighboring landowners. Therefore, I want to choose the location for which the shortest orthogonal path that goes either to a tree or out of the orchard is as long as possible. By an orthogonal path I mean a sequence of steps that go along rows and/or columns (not diagonally). If there are several locations that have the same shortest orthogonal path, break the tie by choosing the smallest row number, and, if necessary, break any remaining tie by choosing the smallest column number.

The existing layout of the orchard is shown by a String[] orchard in which the elements correspond to rows 1, 2, ..., n. Within each element of orchard, the characters correspond to columns 1, 2, ..., n. The character 'T' indicates an existing tree at that row and column, while '-' indicates an available location.

Create a class Orchard that contains a method nextTree that is given a String[] orchard and returns a int[] with two elements giving the row and column of the chosen location. The first element of the return should give the row, and the second element should give the column.



Method signature:int[] nextTree(String[] orchard)
(be sure your method is public)


-orchard contains n elements, where n is between 1 and 50 inclusive
-each element of orchard contains exactly n characters
-each element of orchard contains only the characters 'T' and '-'
-at least one element of orchard contains a character '-'


{ "----" , "T---" , "----" , "----" }
Returns: { 2,  3 }
    ----  row 1
    T---  row 2
    ----  row 3
    ----  row 4
The edge locations all have a path of length 1 out of the orchard. The four central locations have a shortest path of 2 out of the orchard. Among these four, the one in row 2 column 2 has a path of 1 to the tree. Among the other 3 locations, the one in row 2 is preferred to the ones in row 3.
Returns: { 3,  3 }
The location at row 3, column 3 has a shortest orthogonal path of 3. In fact it has paths of length 3 to each of the 2 existing trees and also to the outside of the orchard.
Returns: { 6,  6 }
Returns: { 2,  3 }
The location at row 2, column 3 has a shortest path of length two both to the outside of the orchard and to several trees.

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Simple Math, Simple Search, Iteration