Simple, eh?

It gets simpler after you look up @-, $`, $&, $', \l modifier, add a couple of data dumps, think through the regex greediness and backtracking, dig into precedence..

/#.*#/ and next;       # same row
[download]

That is pretty easy to see how it works, without the /s modifier, . does not match newline, so two #s in the same line. Your comment spells it out, but it makes your intent clear for the next couple lines which are a little bit harder to see how they work.

  /#(?:.{$gap}..)*.{$gap}.#/s and next; # same column
[download]

The greediness of the first portion (?:.{$gap}..)* marches the regex all the way to the end of the grid while .{$gap}.# backtracks so it tries to make a match.

Then of course the best line and, also would like to mention that, I super searched for 'while /$&/g' just to see if it was somewhere else, and only this node came up making it pretty unique.

push @queue, "$`#$'" =~ s/$&/\l$&/gr while /$&/g;
[download]

That line makes me love and hate perl at the same time. Creating and pushing the partial solutions to @queue in one line. It iterates through the grid, for the letter it has matched earlier [A-Z], adds this grid with the instance of the letter changed to #, and all other instances of the letter lowercased with \l.

The alternation operator in /#(.{$gap,$egap}|)#/s is not used or maybe I don't understand, I think perl should not compile that, but

print 'yes' if 'a' =~ /(b|)/;
[download]

works and matches, so back to the books, seems that empty alternations always match, so that means this alternative is checking for two '#'s in a row, which would already be matched by that point. In other search result coincidences, exactly one year ago today, someone tried to get perl critic to disallow empty alternations.

Very neat solution to a fun problem, easy enough to dig into and understand a little bit more perl. Thanks for sharing.