Inspector Cat vs Monster Mouse Super Villain in the City of Superior Cheese
===
Fsshhhhh!
Somewhere in a dark alley, in the City of Superior Cheese, a mysterious portal
flashes into existence.
WOOM!
A man-sized mouse, draped in dark leather clothes, jumps out of the portal,
running madly.
Tingle-tingle!
Fifteen blocks from there, Inspector Cat is enjoying a cup of milk when his
wisker-senses kick in. Someone in the city must be trying to steal cheese from
one of the few famous cheese shops of the city.
Tingle-ti?
Yes, his wiskers tell him exactly which shop it is, but it doesn't matter.
Inspector Cat needs more information!
Ting-tow tingloune tine-ti!
So the fiend will try to escape through a portal at the intersection of Cheddar
and Camembert? Then I shall wait for him there, challenge him, and bring him to
justice!
And Zoom!, Inspector Cat speeds through the streets towards the escape location.
Of course, if Inspector Cat reaches the portal first (or if they arrive at the
same time), then Monster Mouse has no chance to escape: Superheroes somehow
always manage to win over Supervillains.
But today, you're playing Monster Mouse. So you will need to plan routes which
insure that the escape portal can be reached strictly before Inspector Cat.
You will be given a map of the initial state of the city. Inspector Cat drinks
milk at pixel 'C', 4 portals are represented by '*' pixels, while '.' pixels
represent the ground. Monster Mouse, who begins in the alterworld, is not
represented.
The 4 cheese shops are represented by the numbers '1', '2', '4', and '8'. Those
numbers are also the relative value of the cheese they contain. Monster Mouse
wants to collect the maximum possible cheese value without ever getting caught
by Inspector Cat. This maximum value is the integer your program should output.
Monster Mouse first begins by picking a portal, and entering the City trough it.
At this instant, both Monster Mouse and Inspector Cat already know which portal
(not necessarily the same) will be used to exit to the alterworld. Naturally,
Inspector Cat runs toward this exit portal immediately, but Monster Mouse must
hold-up at least one cheese shop first. Otherwise, he won't have the strength to
open the exit portal.
Once Monster Mouse manages to reach the exit portal before Inspector Cat, he
escapes, and recharges the super-powers which enable him to hold-up cheese shops
in a blink of an eye, by merely touching them. Meanwhile, Inspector Cat finally
reaches the exit portal, and awaits there with another cup of milk.
Monster mouse may then pick another portal and collect more cheese, again and
again until he decides it is no longer safe to do so. Portals can be used more
than once, but not cheese shops. Since this takes place in a city, all distances
are Manhattan distances. Inspector Cat and Monster Mouse move at the same pace.