3 added 182 characters in body

# Retina, 397416 bytes

T +^.*| ?¶.|.*$I # {+ (\w) d$1
+(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+m(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 # ^(.*a)(¶(.|¶)*)(\w)#$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2$5#
}^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6
sU.*

(a|d)\1\1?
$1 ss s ww w  Try it online!Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation: T +^.*| ?¶.|.*$


Fill in the border. This avoids walking around the outside of the maze (e.g. for test case 7).

I also investigated a true square grid solution i.e where the character matrix is itself square rather than being a 3×2 layout with an optional border. While probably nonconforming to the question, the ability to transpose reduced the byte count to 331350: Try it online!Try it online!

# Retina, 397 bytes

I
#
{+ (\w)
d$1 +(\w)$1a
+(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w ^ w¶ w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))$4$5$6¶$1 {^(.*d)(¶(.|¶)*)#(\w)$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# ^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)$1$6$2 $5# }^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#$1$5$2#$6 sU.* (a|d)\1\1?$1
ss
s
ww
w


Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation:

I also investigated a true square grid solution i.e where the character matrix is itself square rather than being a 3×2 layout with an optional border. While probably nonconforming to the question, the ability to transpose reduced the byte count to 331: Try it online!

# Retina, 416 bytes

T +^.*| ?¶.|.*$I # {+ (\w) d$1
+(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+m(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 # ^(.*a)(¶(.|¶)*)(\w)#$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2$5#
}^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6
sU.*

(a|d)\1\1?
$1 ss s ww w  Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation: T +^.*| ?¶.|.*$


Fill in the border. This avoids walking around the outside of the maze (e.g. for test case 7).

I also investigated a true square grid solution i.e where the character matrix is itself square rather than being a 3×2 layout with an optional border. While probably nonconforming to the question, the ability to transpose reduced the byte count to 350: Try it online!

2 bugfix

# Retina, 393397 bytes

I
#
{+ (\w)
d$1 +(\w)$1a
+(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}++m(¶^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w ^ w¶ w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))$4$5$6¶$1 {^(.*d)(¶(.|¶)*)#(\w)$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# ^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)$1$6$2 $5# }^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#$1$5$2#$6 sU.* (a|d)\1\1?$1
ss
s
ww
w


Try it online!Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation:

{+ (\w)
d$1 +(\w)$1a
+(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}++m(¶^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w  Flood fill from the exit to the entrance. At each step, use a letter to indicate the best direction to go (wasd - this might be familiar to gamers; I had also considered hjkl but I found it too confusing). Additionally, prefer to go up/down repeatedly;repeat the same direction; this avoids going left/right in the between two vertically adjacent cells. # Retina, 393 bytes I # { (\w) d$1
(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+(¶(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 # ^(.*a)(¶(.|¶)*)(\w)#$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2$5#
}^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6
sU.*

(a|d)\1\1?
$1 ss s ww w  Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation: { (\w) d$1
(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+(¶(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w


Flood fill from the exit to the entrance. At each step, use a letter to indicate the best direction to go (wasd - this might be familiar to gamers; I had also considered hjkl but I found it too confusing). Additionally, prefer to go up/down repeatedly; this avoids going left/right in the between two vertically adjacent cells.

# Retina, 397 bytes

I
#
{+ (\w)
d$1 +(\w)$1a
+(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w ^ w¶ w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))$4$5$6¶$1 {^(.*d)(¶(.|¶)*)#(\w)$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# ^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)$1$6$2 $5# }^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#$1$5$2#$6 sU.* (a|d)\1\1?$1
ss
s
ww
w


Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation:

{+ (\w)
d$1 +(\w)$1a
+(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w  Flood fill from the exit to the entrance. At each step, use a letter to indicate the best direction to go (wasd - this might be familiar to gamers; I had also considered hjkl but I found it too confusing). Additionally, prefer to repeat the same direction; this avoids going left/right in between two vertically adjacent cells. 1 # Retina, 393 bytes I # { (\w) d$1
(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+(¶(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 # ^(.*a)(¶(.|¶)*)(\w)#$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2$5#
}^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6
sU.*

(a|d)\1\1?
$1 ss s ww w  Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation: I #  Place a non-alphabetic marker at the entrance. { (\w) d$1
(\w)
$1a +(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)$1s$3 }+(¶(.)*\w.*¶(?<-2>.)*(?(2)(?!)))$1w


Flood fill from the exit to the entrance. At each step, use a letter to indicate the best direction to go (wasd - this might be familiar to gamers; I had also considered hjkl but I found it too confusing). Additionally, prefer to go up/down repeatedly; this avoids going left/right in the between two vertically adjacent cells.

^
w¶


Assume the first step is down.

w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1


But if there's a letter above, left or right of the entrance, change that to the first step.

{^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 # ^(.*a)(¶(.|¶)*)(\w)#$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2$5#
}^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6


Move the marker in the direction of the last move, reading the direction of the next move from the square that the marker is moving to, and add that to the list of directions. This repeats until the U is reached.

sU.*


Delete everything after the directions as it's not needed any more.

(a|d)\1\1?
\$1
ss
s
ww
w


The original grid is on a 3×2 layout. While moving vertically if we zig-zag horizontally the flood fill will optimise the movement and only move 3n-1 characters horizontally, so when dividing by three, we need to round up. Vertically we just divide by 2.

I also investigated a true square grid solution i.e where the character matrix is itself square rather than being a 3×2 layout with an optional border. While probably nonconforming to the question, the ability to transpose reduced the byte count to 331: Try it online!