TopCoder problem "DogField" used in TCHS SRM 44 (Division I Level Three)

Problem Statement


d dogs and d dog-houses are located on a rectangular field of n * m squares. It is raining now, so each dog wants to get into a dog-house as soon as possible, but each dog-house can accomodate only 1 dog. To make the task harder, some squares of the field contain rocks which make those squares impassable. Dogs cannot pass through squares with dog-houses either, but they can enter empty dog-houses. Once a dog enters a dog-house, it can never leave it. Dogs are very friendly, so a dog can pass through an empty square even if there are other dogs on it.

A String[] field will give you the map of the field. Each character of field will be an uppercase 'D' (representing an empty square with a dog on it), an uppercase 'H' (a dog-house), an uppercase 'R' (a rock) or a '.' (an empty square). Dogs can only move between neighboring squares (two squares are neighboring if they share a side), and it takes 1 second to move from one square to another. At most one dog can move at the same time. The dogs may never leave the field. Return the minimal total time required for all the dogs to end up in dog-houses. If at least one dog cannot reach an empty dog-house, return -1 instead.



Method signature:int saveDogs(String[] field)
(be sure your method is public)


-Initially, every dog is on an empty square (i.e., not on a square containing a dog-house, rock, or another dog).


-field will contain between 1 and 50 elements, inclusive.
-Each element of field will contain between 1 and 50 characters, inclusive.
-All elements of field will contain same number of characters.
-Each character in each element of field will be an uppercase 'R', an uppercase 'H' , an uppercase 'D' or a '.'.
-field will contain between 1 and 10 'D' characters, inclusive.
-The number of 'D' and 'H' characters in field will be the same.


Returns: 7
The dog at row 0, column 0 will move three squares right. The dog at row 1, column 1 will move one square down. The dog at row 1, column 5 will move one square left and one square down. The dog at row 1, column 6 will move one square up. The total time needed to save all the dogs is 3 + 1 + 2 + 1 = 7.
Returns: -1
The dog cannot reach the dog-house because it is surrounded by rocks.
Returns: 14
The only dog will move to the only dog-house by the path marked by 'U' characters:
Returns: 1
The dog only needs to move one square to reach the dog-house.
Returns: 96

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Graph Theory