TopCoder problem "Trainyard" used in SRM 376 (Division I Level One , Division II Level Two)

Problem Statement


You've been given the blueprint for a trainyard which was laid out on a grid. Some grid cells have East-West track segments (marked with '-'), some have North-South track segments (marked with '|'), and others are intersections (marked with '+'). Cells with no track are marked with a '.' character. A train may enter an intersection square from any direction and may leave in any direction. Trains may enter a North-South track segment from either the North or South, and must exit the square moving in the same direction. Thus if a train enters a North-South segment from the South, it must leave to the North. East-West tracks work the same way, except with directions East and West. Squares without track may not be entered, and the train may not leave the area covered by the grid. The train always occupies a single grid location, and each square moved requires one unit of fuel.


The train's starting location is marked on the map with an 'S' character. Trains may exit this location going any direction. Given the trainyard map in layout and the fuel available in fuel, you want to determine how many grid squares may be reached. You do not need to construct one route that reaches all these squares; rather, you are determining which squares could be reached using any legal route beginning at the 'S' location. A legal route may use some, all, or none of the fuel. Return the number of distinct grid squares that can be reached, including the initial 'S' location.



Parameters:String[], int
Method signature:int reachableSquares(String[] layout, int fuel)
(be sure your method is public)


-layout will contain between 1 and 10 elements, inclusive.
-Each element of layout will contain between 1 and 10 characters, inclusive.
-Each element of layout will contain the same number of characters.
-Each element of layout will contain only the characters '-','|','+','.', and 'S'.
-layout will contain exactly one 'S' character.
-fuel will be between 1 and 10, inclusive.


Returns: 4
The train can reach the initial 'S', as well as one square to the West. It could also reach two squares to the East (but not the third, as there's only 2 units of fuel). It can't move North to start, as it can't enter an East-West segment from the South.
Returns: 10
All 9 of the track segments are reachable, plus 1 for the 'S' square. Be sure not to count squares twice!
Returns: 15
All of the track segments are reachable except for the two at the North end that seem to be oriented the wrong way.
Returns: 6
The track segment on the far East side is not reachable - as you can't enter a North-South segment from the West.

Problem url:

Problem stats url:




PabloGilberto , Olexiy , misof , ivan_metelsky

Problem categories:

Search, Simulation