FOXWOLF  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 \leq C \leq 9$).
The forest that the Fox and the Wolf live in can be regarded as a rectangle, $N$ km long along its East side and $M$ km wide along its North side ($1 \leq N,M \leq 20$). It is divided into a grid of squares, each with a side length of 1 km. Each such square either contains a meadow (represented 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 stand still and spend $B$ minutes ($1 \leq B \leq 9$) picking burrs off of himself. As mentioned above, they must also stop and chat if 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 with 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 minimum time in their heads instantly – however you, the observer, will probably need to write a program to figure it out...
Input
Line $1$: 4 integers, $N$, $M$, $C$, and $B$
Next $N$ lines: $M$ characters each, representing a row of the forest as described above
Output
A single integer – the minimum time for both the Fox and the Wolf to get to their respective homes, in minutes. If this is impossible, output 1 instead.
Example
Input:
5 6 5 1 ...... BWTTTB B.TB.. BBT..T .FTfw.
Output:
17
Explanation of Sample:
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 burrfilled 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.
hide comments
hodobox:
20160701 14:31:45
Nice one :)


Samuel Nacache:
20140328 02:05:48
Finally, something different than WA _ 

Federico LebrÃ³n:
20130715 19:18:33
DONE. DONE. TAKE THAT YOU "$(%&)(% PROBLEM. WHO'S LAUGHING NOW HUH? I AM. THAT'S WHO. NOT YOU. HAHAHAHAHA. HAHAHAHAHAHAHA. HA HA HA HA HA. DIE IN A FIRE.


Samuel Nacache:
20130514 22:40:12
This problem is really hard


Federico LebrÃ³n:
20130510 01:10:51
*wonders if he's reading the input correctly, since his solutions tend to give WA very quickly and with little memory used :s*


Edelweiss:
20130508 03:36:19
Uh..sorry, another case:


Edelweiss:
20130507 17:58:08
Could you please tell me what should this output:


Edelweiss:
20130507 17:58:06
Last edit: 20130507 17:58:50 

Ehor Nechiporenko:
20130507 10:42:14
First of all, what is the reason for wolf to wait for the fox, he can staight go home first and it will not change the time. And also why Fox cannot get home for 16 minutes next way:


Federico LebrÃ³n:
20130507 04:40:39
"A single integer – the minimum time ..."

Added by:  SourSpinach 
Date:  20130507 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 