The Fox and the Wolf
In a certain peaceful forest, there live 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 C minutes (1 ≤ C ≤ 9).
The forest that the fox and the wolf live in is a rectangle, N km long along its east side and M km wide along its north side (1 ≤ N, M ≤ 20). It is divided into a grid of squares, each with a side length of 1 km. Each such square either contains a meadow (marked by a '.'), 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 B minutes (1 ≤ B ≤ 9) picking burrs off of himself. As mentioned above, they must also stop and chat every time they meet up. Though each square is quite big, the animals always walk to its exact centre before moving on. This means that they will meet up if they either occupy the same square at the same time, or if they pass each other while walking between squares (which would happen if they switched positions in the space of a minute). Once the animals have chatted once, they never have to chat again, having already satisfied the demands of etiquette. Both animals are great multitaskers, and can pick burrs while chatting to each other.
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 minimium time in their heads instantly - however you, the observer, will probably need to write a program to figure it out…
Input
| Line 1: | Four integers — N, M, C, and B |
| The next N lines: | M characters, representing a row of the forest as described above |
Output
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 2 squares behind the fox most of the time, except for when it enters the burr-filled square, when it will temporarily be 1 behind. With this strategy, the wolf will take 14 minutes to get home, while the fox will take 17, and since we only care about the larger, the total time is 17 minutes.
All Submissions
Best Solutions
Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Mar 11, 2009
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Sorry to Foundation for lots of time wasted trying to debug his correct program.