A Mouse with Dynamite

Question

You're a mouse. Your mouse friends have all been captured, and are unconscious and trapped in a maze that has only one entrance/exit. You happen to have a perfect map of the maze, so you can plot a solution to rush in and carry them all to safety. However, the maze is guarded with a security system that will trigger an alert if a threshold of 1000 is reached, causing you to be captured and fail your rescue mission.

From your previous investigations of the maze, each square you step (i.e., each horizontal or vertical movement -- mice can't move diagonally) adds 1 to the security system's counter. However, if you're carrying a weight (either a block of dynamite or an unconscious mouse friend), it instead adds 2 since it detects the additional pressure. The entrance/exit square doesn't have this security system, and so doesn't add to the counter.

You have an unlimited supply of dynamite that you've brought to the entrance, so you can simply blow up all the walls to free your friends. But you need to be cautious with doing so, since each explosion adds 50 to the counter from the concussive pressure. Additionally, you can only carry one thing at a time, either one mouse or one block of dynamite. Since each block of dynamite can only detonate one wall space, this means that if there are multiple walls in a row, you need to make an empty-handed trip back to the entrance to grab more.

Worked-through example

Suppose our maze looks like the following:

######
#M# E#
######

I'll use c for the counter. We start at the Entrance, move one square left while carrying dynamite, c=2. We detonate the dynamite to explode the wall, c=52. We move two squares left, empty-handed, to get c=54, and we're now standing on the mouse's square. We pick our friend up, and move 3 squares back to the Exit, but the last square doesn't count since it doesn't have any sensors, so that's only 2 squares with something on our back. That means that when we reach the exit with the final mouse, c=58, which is less than 1000, and therefore the mission succeeds.

Challenge

Given an input maze, output whether you, the mouse hero, can successfully rescue all trapped mice within the constraints outlined above, or whether the mission is a failure.

Input

• A 2D maze in any acceptable format (multiline string, array of strings, etc.).
• For this challenge, I will be using # for both the interior and exterior walls, M for the mouse friends, and E for the entrance.
• The entrance will never be immediately adjacent to an interior wall (there will always be at least one space in which to move freely).
• You can substitute any printable ASCII characters you wish so long as it's consistent. This does allow you to use two different symbols for interior walls vs. exterior walls, so long as you maintain consistency (e.g., if you choose to use @ for interior walls instead, and leave # for exterior, every interior wall must be @ and every exterior wall #).
• The maze will always be completely bounded by walls, but is not necessarily rectangular. If desired, you can assume that the maze is padded with spaces to make rectangular input (optional).
• The maze may have sections that are unreachable without dynamite.
• You cannot dynamite the exterior walls of the maze.

Output

A truthy/falsey value. Truthy for "Yes, the mouse can rescue every other mouse" or Falsey for "No, the alarm system will be tripped."

The Rules

• Either a full program or a function are acceptable.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

Truthy examples, separated by blank lines.

#####
#M E#
#####

######
#M# E#
######

########
#E  # M#
#   #  #
#   #  #
#      #
########

#############################
#    ##      #       #      #
#  M ## M    #       #      #
#    ##      #   M   #    E #
#M   ##      #       #      #
#############################

###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############

Falsey examples, separated by blank lines

#############################
#M   ##      ##      ##     #
#  M ## M    ##      ##     #
#    ##      ##  M   ##   E #
#M   ##      ##      ##     #
#############################
#############################
                     ########
                     ########
                     #   #  #
                     # M # M#
                     ########

              #####
              # M #
              #####
              #####
              #####
              #####
###################
# # # ##   ## # # #
#M#M#M## E ##M#M#M#
# # # ##   ## # # #
###################
#######
######
#####
####
# M#
####

###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############

Answer 1

Perl, 216 215 bytes

Includes +2 for -0p

Give input on STDIN. Use % for external walls, # for internal walls, 0 for empty spaces, 8 for mice and r for the starting position. The whole boards must be padded so it forms a rectangle. You can transform and run the examples as:

cat dynamite.txt | perl -p0e 's/.+/$a^=$&/egr;s//sprintf"%-*s",length$a,$&/eg;1while/\n/,s/^ *\K#|#(?= *$)|^ *.{@{-}}\K#|\A[^\n]*\K#|#(?=[^\n]*\n\z)|#(?=.{@{-}} *$)/%/sm;y/ EM/0x2/' | dynamite.pl

dynamite.pl:

#!/usr/bin/perl -0p
sub f{@a{@_}||=push@{$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)},@_}f$_;for(@{$%}){f y/xr|/ytx/r;{f s/\pL\d/$&^(E&$&)x2/er}{f s/(q|s|y)#/$&^"\x01\x13"/er}my$o;{$\|=/x/>/2/;$o.="
"while s/.$/$o.=$&,""/meg}f$o}$%++>999|$\||redo}{

Replace the \xhh escapes for the claimed score.

The program can't realistically handle complex cases. In particular it can't handle any of the failure cases. This is because there are just too many different ways of blowing up the internal walls or picking up mice so the search becomes too wide and uses too much memory even though it's at least smart enough to never process the same state multiple times. The pressure limit has to be lowered to 100 or so for somewhat bearable runtimes and memory usage.

Explanation

I use the bit pattern of a character to represent the state of a field:

contains victim: 0000 0010
has hero:        0100 0000
carry dynamite   0000 0001
carry mouse      0000 0100
home             0000 1000
walkable         0001 0000 (not really needed but results in shorter regexes)
make printable   0010 0000
wall             0010 xxxx (bit patterns not very important,
permawall        0010 xxxx  just avoid letters and digits)

For example the hero (01000000) carrying dynamite (00000001) must be on a place he can walk (00010000) and we want all values to be printable ASCII (00100000). Taking the bitwise or of all these bitmasks gives 01110001 which is the ASCII code for q. In total this becomes::

p: hero                     r hero on victim
q: hero carrying dynamite   s hero carrying dynamite on victim
t: hero carrying mouse      v hero carrying mouse on victim

x : hero at home
y : hero at home carrying dynamite
| : hero at home carrying mouse

0: empty  without hero
8: home   without hero
2: victim without hero

%: permanent wall
#: normal wall

The program will only consider the hero moving to the right (the rotation explained later will take care of the other directions). The bitmasks were carefully chosen such that the hero is always represented by a letter and a place he can move to by a digit (except the hero at home carrying a victim, but again this is intentional so that the hero's only move will be to drop the victim). So a hero that can move forward is matched by /\pL\d/. The matched substring has to be modified so that the hero and what he is carrying is removed from the first character and added to the second one, which can be done with a bitwise xor with the same value for both characters. The xor value consists of the hero bit (01000000), the dynamite bit (00000001) and the carry mouse bit (00000100). Together they or to 01000101 which is ASCII E. So moving the hero becomes:

s/\pL\d/$&^(E&$&)x2/e

The hero can blow up a wall if he is standing right in front of it and is carrying dynamite (q, s or y). The hero will lose his dynamite (xor with 00000001) and the wall # will change to a passage 0 (xor with 00010011), so

s/(q|s|y)#/$&^"\x01\x13"/e

To handle the other directions the whole board is rotated (rotated board ends up in $o):

my$o;$o.="\n"while s/.$/$o.=$&,""/meg

Apart from moving the hero also has a number of other choices he can make:

When at home, pick up dynamite:                   x -> y
When on victim not carrying anything pick him up: r -> t
When at home carrying a victim, drop him off:     | -> x

This is done by

y/xr|/ytx/

The board is finished if the hero is at home carrying nothing (x) and there are no more victims to rescue (no 2). This can be conveniently tested using

/x/>/2/

Once the board is solved I want to remember this state and at the end print it. For that I carry the "is solved" flag in $\ and print that at the end of the program without printing $_, so

$\|=/x/>/2/  ...   }{

The states to be processed at pressure 0 are kept in @0, at pressure 1 on @1 etc. The current pressure is kept in $%. Using $n or something like it would be shorter but the code doesn't work if the variable isn't initialized to something because autovivification will otherwise change $n to an ARRAY reference.Looping over the states at a certain pressure is done using a for and not a map because with a for you can extend the array while it is still being looped over and will pick up the new elements. This is needed because the rotations and single field choices of the hero happen in 0 time and end up in the same pressure array. So the loop for a given pressure is done by

for(@{$%}){...}

This is repeated until the pressure reaches 1000 or a solution is found:

$%++>999|$\||redo

All that is left is adding newly discovered states to their respective pressure arrays. That will be done by subroutine f. We only want to add a state if it has not been seen yet. States that have been seen before are kept in %a so:

sub f{@a{@_}||=push@$n, @_}

$n represents the new pressure for a state. I will derive that from the state that the regex variables still have as a result of the hero's action leading to this call:

if $1 is set it was from s/(q|s|y)#/$&^"\x01\x13"/e which blows a wall -> 50
else if $& is set it was from s/\pL\d/$&^(E&$&)x2/e, so the hero moves.
    if $& contains 8 the hero went home -> 0
    else if the hero has carry bits (5) -> 2
    else                                   1
else ($& was not set) it was from y/xr|/ytx/r -> 0

This leads to the following formula for $n:

$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)

All the substitutions get an r modifier so they return the changed state and leave the current state in $_ alone. f is then called on this changed state, so you get code like

f y/xr|/ytx/r;

Because the calculation of $n needs the regex variables they must default to unset in case the substitutions changes nothing (because the condition to trigger them is not fulfilled). I must also not pick up any regex variables from a previous loop. Therefore the substitutions are wrapped in {} blocks to save and restore the regex state. That's how you get statements like

{f s/\pL\d/$&^(E&$&)x2/er}

In particular the rotation is so wrapped so it calls f without regex variables and gets a pressure contribution of 0.

The only thing still to do is to prime @0 with the initial state at the start

f$_

This is in the main loop so it also tries to add $_ to later pressure arrays, but since the initial state will already be in %a nothing will happen.

Together all this basically finds the shortest solution using Dijkstra's algorithm. There is a potential problem though. The current code won't add a state if it is rediscovered with a lower pressure than the first discovery. I've not been able to construct a board that would trigger this, but have also been unable to prove it is impossible.

Answer 2

JavaScript, 863 834 785 781 bytes

Saved 29 bytes thanks to ETHproductions
Saved 53 bytes thanks to Jordan

L=[]
f=(S,r="",R="",p=0,s=S.replace(RegExp(r),R),l=`((.|\n){${s.split`
`[0].length}})`,q=p+1,o=p+2,n=p+50)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...[[/ E/,"me",q],[/ E/,"de",o],[/ME/,"ce",q],[/E /,"em",q],[/E /,"ed",o],[/EM/,"ec",q],[`E${l} `,"e$1m",q],[`E${l} `,"e$1d",o],[`E${l}M`,"e$1c",q],[` ${l}E`,"m$1e",q],[` ${l}E`,"d$1e",o],[`M${l}E`,"c$1e",q],[/ m/,"m ",q],[/m /," m",q],[`m${l} `," $1m",q],[` ${l}m`,"m$1 ",q],[/ (d|c)/,"$1 ",o],[/(d|c) /," $1",o],[`(d|c)${l} `," $2$1",o],[` ${l}(d|c)`,"$3$1 ",o],[/d#/,"m ",n],[/#d/," m",n],[`#${l}d`," $1m",n],[`d${l}#`,"m$1 ",n],[/mM/," c",q],[/Mm/,"c ",q],[`M${l}m`,"c$1 ",q],[`m${l}M`," $1c",q],[/[mc]e/," E",p],[/e[mc]/,"E ",p],[`e${l}[mc]`,"E$1 ",p],[`[mc]${l}e`," $1E",p]].map(a=>f(s,...a)))
F=s=>f(s)<1e3

Takes input as a multiline string.

This defines an anonymous function that uses a recursive function f to determine if you trip off the alarm before retrieving all the mice. f returns 1000 if the pressure is above 1000 (to avoid endless recursion), returns the pressure if there are no more mice to rescue and the mouse in the exit, and returns the minimum pressure of all possible moves from the current state otherwise. It uses an array L to keep track of already visited positions where L[pos]==0 if it is visited, and undefined if it isn't. This may not be necessary, but it prevents the mouse from doing useless moves and throwing recursion errors at the very least. (This does mean you should redefine L if you are testing this multiple times)

This uses the format in the question other than that it requires you to use a different character for the external walls. (Anything other than # MEmecd)

More readable version:

stateList = []
f=(s,regex="",replacement="",pressure=0,state=s.replace(regexp(regex),replacement),line=`((.|\n){${state.split("\n")[0].length}})`)=>{
    if (state in stateList || pressure > 999) return 1e3
    if (!/M/.test(state) && /E/.test(state)) return pressure

    stateList[state] = 0

    return [
        [/ E/,"me",pressure+1],
        [/ E/,"de",pressure+2],
        [/ME/,"ce",pressure+1],
        [/E /,"em",pressure+1],
        [/E /,"ed",pressure+2],
        [/EM/,"ec",pressure+1],
        [`E${line} `,"e$1m",pressure+1],
        [`E${line} `,"e$1d",pressure+2],
        [`E${line}M`,"e$1c",pressure+1],
        [` ${line}E`,"m$1e",pressure+1],
        [` ${line}E`,"d$1e",pressure+2],
        [`M${line}E`,"c$1e",pressure+1],
        [/ m/,"m ",pressure+1],
        [/m /," m",pressure+1],
        [`m${line} `," $1m",pressure+1],
        [` ${line}m`,"m$1 ",pressure+1],
        [/ ([dc])/,"$1 ",pressure+2],
        [/([dc]) /," $1",pressure+2],
        [`([dc])${line} `," $2$1",pressure+2],
        [` ${line}([dc])`,"$3$1 ",pressure+2],
        [/d#/,"m ",pressure+50],
        [/#d/," m",pressure+50],
        [`#${line}d`," $1m",pressure+50],
        [`d${line}#`,"m$1 ",pressure+50],
        [/mM/," c",pressure+1],
        [/Mm/,"c ",pressure+1],
        [`M${line}m`,"c$1 ",pressure+1],
        [`m${line}M`," $1c",pressure+1],
        [/[mc]e/," E",pressure],
        [/e[mc]/,"E ",pressure],
        [`e${line}[mc]`,"E$1 ",pressure],
        [`[mc]${line}e`," $1E",pressure]
    ].map(a=>f(state,...a)).reduce((a,b)=>a-b<0?a:b) //reduce used for support in more browsers.
}
s=>f(s)>1e3