## FOXWOLF - The Fox and the Wolf

no tags

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

hide comments
 hodobox: 2016-07-01 14:31:45 Nice one :) One testcase I had WA on while AC on all others posted here: 3 3 1 10 f.w TBT W.F answer is 15, with both fox and wolf never staying put when they can move Samuel Nacache: 2014-03-28 02:05:48 Finally, something different than WA -_- Federico LebrÃ³n: 2013-07-15 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. I'm sorry. That needed to happen. Last edit: 2013-08-08 04:46:41 Samuel Nacache: 2013-05-14 22:40:12 This problem is really hard Edit: It is just because the multitasking, just think in a bigger solution than the actual board they give you. Last edit: 2013-05-15 05:01:47 Federico LebrÃ³n: 2013-05-10 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* RE: Perhaps, using getchar across newlines may be more risky than simply using scanf or cin. Last edit: 2013-05-10 06:47:58 Edelweiss: 2013-05-08 03:36:19 Uh..sorry, another case: 1 6 5 9 WfB.wF Please tell me how much time they'll take respectively. Thanks a lot :) RE: The Fox walks right twice, then spends 5 minutes both picking off burrs and talking to the Wolf, then spends another 4 minutes still talking to the Wolf, and then walks right twice more for a total of 13 minutes. Meanwhile, the Wolf walks left twice, talks to the Fox for 9 minutes, walks left once, picks off burrs for 5 minutes, and finally gets home after 18 minutes. EDIT: I've found a terribly stupid mistake in my code...Now I've got TLE rather than WA. Maybe I should think of another algorithm. Anyway, thank you very much for your help! ^^ RE: Haha, no problem. These are good cases to clarify. Last edit: 2013-05-08 10:55:26 Edelweiss: 2013-05-07 17:58:08 Could you please tell me what should this output: 1 6 5 1 Wf..wF RE: The answer is 9. Each animal takes 4 steps, and they also stop to chat for 5 minutes (when they meet in the middle). EDIT: Thanks! Last edit: 2013-05-08 03:17:04 Edelweiss: 2013-05-07 17:58:06 Last edit: 2013-05-07 17:58:50 Ehor Nechiporenko: 2013-05-07 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: Up->Up->picking burrs->Up->Up-> Right->Right->Right->Right->Down->Down-> Picking burrs->Left->Down->Left->Down This way takes 16 minutes. Wolf goes first, he will take 11 minutes. Am I wrong somewhere? RE: It looks like you've gotten the animals' starting positions and homes reversed - 'F' is the Fox's den, while 'f' is its initial location. Last edit: 2013-05-07 13:28:02 Federico LebrÃ³n: 2013-05-07 04:40:39 "A single integer – the minimum time ..." "... 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." Is it the minimum or the maximum? RE: You want to minimize the time at which both animals have made it home (which is the larger of their two times). EDIT: Got it, thanks :) Last edit: 2013-05-07 05:23:35

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