Desafío

Caminando por Marks and Spencers, noté que tenían unidades de aire acondicionado ubicadas al azar alrededor de la tienda. Con ganas de mantenerme fresco, me preguntaba cuál era la forma más fácil de moverse por toda la tienda sin estar demasiado tiempo alejado de una unidad de aire acondicionado.

Dado un mapa, debe encontrar una manera de recorrer todo el mapa manteniendo la distancia desde una unidad de aire acondicionado lo más corta posible (incluso si la unidad de CA está del otro lado de una pared).

Mapa

El mapa se puede suministrar de la forma que desee y utiliza los siguientes 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

Un mapa de ejemplo sería:

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

o

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

Viajar por todo el mapa significa pasar por cada espacio vacío y aire acondicionado. No puede viajar a través de una pared y solo puede viajar ortogonalmente. Un mapa puede no ser siempre rectangular.

Mantener la distancia lo más corta posible de una unidad de CA es la suma en todos los pasos de tiempo.

Pasar a través significa entrar y salir.

Puede generar la ruta de la forma que desee. Ejemplos incluyen:

• Salida del mapa con la ruta incluida
• Salida de la ruta como una sucesión de puntos cardinales (p NNSESW. Ej. )

PowerShell para Windows, 376 367 bytes

Como un hombre perezoso, no voy a todos los estantes, me cambio de aire acondicionado a aire acondicionado en una tienda. Creo que viajé por toda la tienda visitando todos los acondicionadores de aire.

$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}

Pruébalo en línea!

Desenrollado:

$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
}