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.
|