In a certain peaceful forest, there lives a fox and a wolf. Due to common
misconception, one might suppose that the wolf would want to hunt the
fox – however, both are in fact nice animals, and get along just fine.
Indeed, they have such nice manners that if they ever meet up, they will
have a nice little chat for
The forest that the fox and the wolf live in is a rectangle, .
),
is full of burrs (B
), is blocked by trees (T
), contains the
fox's den (F
), contains the wolf's lair (W
), currently contains
the fox (f
), or currently contains the wolf (w
).
At the end of a long day at work (consisting of solving complex computer science problems in their heads), both animals wish to get to their respective homes as soon as possible. Every minute, each of them can walk one km directly north, east, south, or west, or just stay put - however, they cannot enter squares blocked by trees, nor can they enter each other's homes (that wouldn't be very polite). They also don't want to leave the forest, seeing as humans jealous of their supreme intellect are constantly lurking just outside.
Every time the fox or the wolf goes from a square full of burrs to a
meadow, he must spend
Each animal wants to get home as soon as possible, but is also considerate of the other – as such, they will collaborate so as to minimize the time for both of them to get home. Due to their extreme intelligence, both animals will calculate this minimum time in their heads instantly – however you, the observer, will probably need to write a program to figure it out…
Input Specification
Line
The next
Output Specification
A single number – the minimum time for both the fox and the wolf to get
to their respective homes, in minutes. If it's impossible, output -1
.
Sample Input
5 6 5 1
......
BWTTTB
B.TB..
BBT..T
.FTfw.
Sample Output
17
Explanation
The wolf should wait for the first three minutes, letting the fox go
first. From then on, the fox can continue along its only possible route
home. The wolf will be
Comments