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 s`U.* (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.
s`U.*
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!
