You must have heard about the famous Macedonian king, commander, and strategist of the Argead dynasty. This story
is about Alexander of Macedon or Alexander the Great. We can talk about his deeds and victories for a long time
and you have already heard most of them.
There is an event in the codeeval.com archive that no historian can tell you. It is about a small battle near
Persia. Once, Alexander the Great sent the part of his army, led by Hephaistion—the commander and his best
friend—to patrol the area. After a while, the herald brought bad news: the detachment was ambushed; they could
hold out some time, but they needed urgent help. Alexander with the army was about to depart, but the question
was – which way would be faster: by sea or by land?
He decided to go by sea, and that was the right decision. This way was the fastest and Alexander saved the
life of his warriors and his best friend.
The following figures show a map that Alexander of Macedon had and two alternative ways. The first way is by sea,
it took 4 hours (2 steps by land) to get to the port, followed by 1 hour of getting the army on board. Then,
in 3 hours they passed 3 cells on the map, and, finally, landed in another port in 1 hour, plus 2 hours by
land (1 cell up).
Total - 4 + 1 + 3 + 1 + 2 = 11 hours.
If they decided to go by land, it would have taken them 12 hours (3 cells left and 3 cells up) and most likely
they would not have come in time to help.
We want that you rely not only on a good luck, but also on your programming skills. Your task is to write
a program that will calculate the fastest way from several alternatives.
So, write a program that will determine the shortest time for the army to come and help, knowing that you
have a map, where 'S' - Start, 'F' - Finish, 'P' - 2 ports for a trip by sea.
Why do you need it? Tripping by sea is the faster way. On the land, you should bypass mountains
'^' if there are any.
Each step in the new cell takes 2 hours by land or 1 hour by sea, getting on the ship and landing the army
also take 1 hour each. You need to calculate and print out the shortest time that the trip can take.
The first argument is a path to a file. Each line includes a test case with map, where the following
items are shown:
S - Start (This is your initial position)
F - Finish (This is the point where you need to lead the army to)
P - Port (The place where the army gets on board or lands)
^ - Mountains (Which you should bypass)
* - Empty cells (Where you can safely move by ship and by land)
For example:
**^F | P**P | **** | S*** **^F | P*^P | **** | S***
Calculate and print out the shortest time that the trip will take.
For example:
11 12
- The map is always square and can consist of 4 to 12 cells.
- Every map is passable.
- Mountains need to be bypassed.
- One cell by land – 2 hours, by sea – 1 hour.
- The number of test cases is 40.
- This story is fictional. :)