Desafio

Andando pela Marks e Spencers, notei que eles tinham aparelhos de ar condicionado colocados aleatoriamente em torno da loja. Querendo me refrescar, me perguntei qual seria a maneira mais fácil de percorrer toda a loja sem ficar longe de um aparelho de ar condicionado por muito tempo.

Dado um mapa, você deve encontrar uma maneira de percorrer o mapa inteiro, mantendo a distância de uma unidade de ar condicionado o mais curta possível (mesmo que a unidade de CA esteja do outro lado de uma parede).

Mapa

O mapa pode ser fornecido da maneira que você quiser e usa os seguintes símbolos:

+ is a corner of a wall
| is a east/west facing wall
- is a north/south facing wall
X is an air conditioning unit
S is the start and end point

Um mapa de exemplo seria:

+------S---+
|   X      |
| ---+-+ X |
|    |X|   |
| ---+ +---+
|   X      |
+----------+

ou

+---+--+
| X |  |
|   |  +-----+------+
|   | X      | X    |
|     ---+       |  S
|   |    |  X    |  |
|   |  +-+-------+--+
| X    |
+------+

Viajar pelo mapa inteiro significa passar por todos os espaços vazios e aparelhos de ar condicionado. Você não pode viajar através de uma parede e só pode viajar ortogonalmente. Um mapa nem sempre pode ser retangular.

Manter a distância o mais curta possível de uma unidade CA é a soma de todas as etapas do tempo.

Passar significa entrar e sair.

Você pode enviar o caminho da maneira que desejar. Exemplos incluem:

• Saída do mapa com o caminho incluído
• Saída do caminho como uma sucessão de pontos de bússola (por exemplo NNSESW)

PowerShell para Windows, 376 367 bytes

Como um homem preguiçoso, não vou a todas as prateleiras, passo de ar condicionado para ar condicionado em uma loja. Acredito que viajei por toda a loja visitando todos os aparelhos de ar condicionado nela.

$f={param($m,$d,$o=@{})$w=(($l=$m-split"
")|% le*|sort)[-1]
$m=($l|% *ht $w)-join"
"
if(!$o.$m-or$o.$m-ge$d-and$m-match'(?s)X.*S|S.*X'){$o.$m=$d++
$n=-split")X(S )X(.{$w}S S)X( S.{$w})X("|%{sls "(?s)^(.*$_.*)$" -inp $m -a|% m*|%{($_.Groups-replace'S',' ')[1,2]-join'S'}}
$d=(($n+,($m-replace"(?s)(?<=S(.{$w})?) | (?=(.{$w})?S)",'S')*!$n)|%{&$f $_ $d $o}|sort)[0]}+$d}

Experimente online!

Desenrolado:

$f={
    param($map,$distance,$o=@{})
    $lines = $map-split"`n"
    $width = ($lines|% length|sort)[-1]
    $map = ($lines|% padRight $width)-join"`n"                              # to rectangle

    if(!$o.$map -or $o.$map-ge$distance -and $map-match'(?s)X.*S|S.*X'){
        $o.$map = $distance++                                               # store a map to avoid recalculations
        $n = -split")X(S )X(.{$width}S S)X( S.{$width})X("|%{               # search a nearest X in 4 directions
            select-string "(?s)^(.*$_.*)$" -InputObject $map -AllMatches|% Matches|%{
                ($_.Groups-replace'S',' ')[1,2]-join'S'                     # start a new segment (reset all S and replace the nearest X by S)
            }
        }
        $stepMore = $map-replace"(?s)(?<=S(.{$w})?) | (?=(.{$w})?S)",'S'
        $n += ,$stepMore*!$n                                                # add a step if X was not found
        $distance=($n|%{&$f $_ $distance $o}|sort)[0]                       # recursive repeat
    }

    +$distance
}