An smart mouse always obtains the cheese without being detected.
You are an office mouse, and you're very lucky because in every office of the building where you live there is always one piece of cheese.
You have worked hard to make one mousehole in every office.
Now what remains is the easy part: go out from the mousehole and run until the cheese.
The only problem is that in the offices there are clerks, they are not looking for you but you better keep as far as you can from the clerks.
Show to the mouse the path he has to take:
- The path has to be the safest one.
- The path has to be the shortest path that fulfills the previous statement.
- You move only horizontally and vertically, not diagonal.
- You only can walk in an empty tile.
The one which exposes you to the least risky tiles.
The risky of any tile is inversely proportional to the minimum distance for this tile to any of the clerks.
The risky of a tile is exponential not lineal, which means that the risky of a tile that is 1 tile distance for a clerk is infinitely bigger than other that is 2 tiles distance for a clerk. So it is always safer to cross through a path that exposes you several times to a 2 tiles distance of a clerk rather than other that exposes you only once to a 1 tile distance of a clerk.
The risky of a tile is not accumulative which means that a tile which is 2 tiles distance from two clerks is the same than other that is 2 tiles distance from only one clerk. The only number that means is the minimum of all clerk distances.
Well, just comparing the number of steps :)
It is not necessary since we are only asking for the number of steps.
You have all the offices maps in your building in a plain text file.
Each map is separated with an empty line.
The file looks like this:
---------
| #|
| * * |
| |
| |
----U----
---------
| * |
U * |
| |
| |
| * |
| # |
---------
Where:
#: is the cheese*: is a clerkU: is the mousehole-,|: are walls
Just the number of steps of the path you have chosen of every map in the file.
Every number in a line.
The mousehole position DOES count.
The cheese position DOES count.
8
11
Se how the mouse keep as far from the clerk as it can.
---------
| #|
| |
| |
| * |
| |
| |
-------U-
19
Even when the shortest way would be this (wrong):
---------
| #|
| .|
| .|
| *.|
| .|
| .|
-------U-
The most important thing is remains as safest as possible so this is because the mouse takes a very longer way (correct):
---------
|......#|
|. |
|. |
|. * |
|. |
|.......|
-------U-
This map has a solution that doesn't look correct because it looks like the mouse is going directly to the risk. But at the end you will understand that this solution is the best one.
---------
| #|
| * * |
| |
| |
----U----
8
There are multiple paths those carry us until the cheese but the safest and shortest one is this (correct):
---------
| #|
| * *.|
| .|
| ....|
----U----
Let's see another paths that are not the correct one (wrong):
---------
|......#|
|. * * |
|. |
|.... |
----U----
This one looks safer because you are taking a detour and instance of going directly to one of the clerks you are trying to keep far from them. But this is only working in the beginning because as far you achieve the top corner you are taking as much risks as in the correct solution and not only once but twice.
In this example the mouse looks like it is going too far, but you will realize that is safer that the short way.
-------------
| |
| U
|* * * * *|
| |
| # |
| |
| |
-------------
22
This is the safest and shortest way (correct):
-------------
| .........|
| . .U
|* . * * * *|
| . |
| . # |
| . . |
| .... |
-------------
You can think that once you are almost close to the cheese why not just turn to its direction like this (wrong):
-------------
| .........|
| . .U
|* . * * * *|
| . |
| ...# |
| |
| |
-------------
Which is only 18 steps. You are taking a very shorter way but this new two steps are more risky than every one of the extra steps in the correct path.