Wyzwanie

Spacerując po Markach i Spencerach, zauważyłem, że mają klimatyzatory rozmieszczone losowo wokół sklepu. Chcąc zachować spokój, zastanawiałem się, jaki był najłatwiejszy sposób poruszania się po całym sklepie bez zbyt długiego przebywania w pobliżu klimatyzatora.

Biorąc pod uwagę mapę, musisz znaleźć sposób na poruszanie się po całej mapie, utrzymując możliwie jak najkrótszą odległość od klimatyzatora (nawet jeśli klimatyzator znajduje się po drugiej stronie ściany).

Mapa

Mapa może być dostarczana w dowolny sposób i wykorzystuje następujące symbole:

+ 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

Przykładowa mapa to:

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

lub

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

Podróżowanie po całej mapie oznacza przechodzenie przez każdą pustą przestrzeń i klimatyzator. Nie możesz podróżować przez ścianę i możesz podróżować tylko ortogonalnie. Mapa nie zawsze może być prostokątna.

Utrzymywanie możliwie krótkiej odległości od urządzenia prądu przemiennego to suma wszystkich kroków czasowych.

Przejście oznacza wejście i wyjście.

Możesz wyprowadzić ścieżkę w dowolny sposób. Przykłady zawierają:

• Tworzenie mapy wraz ze ścieżką
• Wyprowadzanie ścieżki jako szeregu punktów kompasu (np. NNSESW)

PowerShell dla Windows, 376 367 bajtów

Jak leniwy człowiek, nie chodzę na każdą półkę, przechodzę od klimatyzatora do klimatyzatora w sklepie. Wydaje mi się, że podróżowałem po całym sklepie, odwiedzając wszystkie klimatyzatory.

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

Wypróbuj online!

Rozwinięty:

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