Wkład:

Labirynt zawierający postacie:

• -- (ściana pozioma);
• | (ściana pionowa);
• + (połączenie);
• (przestrzeń spacerowa);
• I (wejście);
• U (wyjście).

Czyli dane wejściowe mogą wyglądać następująco:

 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+ 

Wydajność:

Najskuteczniejszym ścieżka należy iść, aby uzyskać od wejścia do wyjścia z labiryntu (przez labirynt), wskazanym przez znaki wskazujące w lewo, w prawo, w górę iw dół (tj >; <; ^; v).

Zasady konkursu:

• Możesz pobrać dane wejściowe w dowolnym rozsądnym formacie. Ciąg-tablica, pojedynczy ciąg z nowymi wierszami, tablica znaków 2D itp. To wszystkie możliwe formaty wejściowe.
• Wynik może składać się z czterech dowolnych znaków. tj ><^v; →←↑↓; ⇒⇐⇑⇓; RLUD; 0123; ABCD; itp.).
• W razie potrzeby możesz dodawać spacje lub końcowe znaki nowej linii; to jest opcjonalne.
• Kroki są liczone na kwadrat (patrz cztery +symbole kwadratów), a nie na postać.
• Labirynt może mieć wymiary od 5x5 do 15x15 i zawsze będzie kwadratem (więc nie będzie żadnych przypadków testowych dla 5x10 labiryntów).
• Możesz założyć, że każdy labirynt ma jedną lub więcej prawidłowych ścieżek od początku do końca i zawsze generujesz najkrótsze (patrz przypadki testowe 4 i 5).
• Jeśli istnieje wiele ścieżek o tej samej długości, możesz wybrać, która z nich ma zostać wydrukowana (patrz przypadek testowy 6).
• Nie możesz „wyjść” poza granice labiryntu (patrz przypadki testowe 7 i 8).

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi odnoszą się standardowe reguły , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem swojego kodu.
• W razie potrzeby dodaj również wyjaśnienie.

Przypadki testowe:

1. Input:
 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+ 

1. Output:
>v>>>vv<v>>v>v>>vvv>>>

2. Input:
 +--+--+--+--+--+ 
I   |        |  | 
 +  +--+--+  +  + 
 |        |  |  | 
 +  +--+  +  +  + 
 |  |  |     |  | 
 +  +  +--+  +  + 
 |        |     | 
 +--+  +  +--+--+ 
 |     |         U
 +--+--+--+--+--+ 

2. Output:
>vvv>>v>>>

3. Input:
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |     |     | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

3. Output:
<<<^<v<^^>>^<^<<

4. Input (test case with two valid paths):
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |           | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

4. Output:
<<^>^<^<<^<<     (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)

5. Input (test case with two valid paths):
                               I
+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+
|     |              |                    |  |
+  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +
|  |     |        |     |        |     |     |
+--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+
|     |  |  |  |     |     |           |     |
+  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +
|  |        |        |  |     |        |     |
+  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+
|  |     |     |        |  |     |     |     |
+  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +
|  |     |        |     |           |        |
+  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+
|     |     |        |        |  |     |     |
+--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +
|              |     |     |        |  |  |  |
+  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +
|     |  |     |  |  |        |        |  |  |
+--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +
|     |     |  |  |  |           |  |     |  |
+--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +
|     |        |  |  |     |        |  |  |  |
+  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +
|        |     |  |     |     |  |     |  |  |
+--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +
|  |        |        |     |        |     |  |
+  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +
|  |              |              |     |     |
+  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+
|     |                                |     |
+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+
                            U

5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v     (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)

6. Input:
 +--+--+--+--+--+
I               |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |               U
 +--+--+--+--+--+

6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)

7. Input:
 I  U
+  +  +--+--+--+
|  |        |  |
+  +--+--+  +  +
|     |     |  |
+--+  +  +--+  +
|        |  |  |
+  +--+  +  +  +
|     |        |
+--+  +--+--+  +
|     |        |
+--+--+--+--+--+

7. Output:
vv>v>^>^<<^

8. Input:
 +--+--+--+--+--+
 |     |        |
 +  +--+  +--+  +
I   |     |  |  |
 +  +  +--+  +  +
U   |     |  |  |
 +--+--+  +  +  +
 |     |     |  |
 +  +--+--+--+  +
 |               
 +--+--+--+--+--+

8. Output:
>v<

Labirynty generowane za pomocą tego narzędzia (w niektórych przypadkach nieznacznie zmodyfikowane).

Retina , 338 281 275 273 261 bajtów

¶U
¶&
+`·(\w.+)$
|$1
((.)+I.+¶.+¶(?<-2>.)+)·
$1v
+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6
·v
-v
G`1
·U
&
{`\B·\d+.(\w+)
$1K$&
(\w+)·\d+.\B
$&$1r
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v
)`\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A
^.+\d·(\w+)
&$1A
M!`&\w+
I|&

Wypróbuj online!

Notatki

• Z powodu znacznych białych znaków wszystkie spacje ( 0x20) są zastępowane interpunkcją ( ·) zarówno w tej odpowiedzi, jak i w łączu TIO. Program działa poprawnie, jeśli spacje zostaną przywrócone.
• Używa odpowiednio AvKrw górę, w dół, w lewo i w prawo. Można je zastąpić dowolnymi literami oprócz I.
• Zajmuje około 40 sekund na TIO dla przypadku testowego 15 × 15. Bądź cierpliwy. Przerobiono część, aby znaleźć najkrótszą ścieżkę, gdy ścieżka dotrze do wyjścia. Okazało się, że zajęło to dużo czasu.
• Może całkowicie złamać labirynty o szerokości 66 lub więcej komórek, ale poradzi sobie z labiryntami o dowolnej wysokości. Poprawka dla dowolnej szerokości zajmuje +1 bajt.

Wyjaśnienie

Program składa się z 3 faz:

• Etap budowy przekonwertować labirynt do kompaktowego formatu, który jest łatwiejszy do pracy z (szczegóły poniżej).
• Faza wypełniająca rzeczywiście rozwiązać labirynt używając algorytmu wypełnienia powodzi.
• Faza zwrotny powrót najkrótszą ścieżkę na wylocie.

Format

Ponieważ oryginalny format labiryntu jest dość niewygodny, pierwsza część programu konwertuje go na inny format.

Komórki

W oryginalnym formacie każda komórka jest reprezentowana jako region 2 × 3:

+               <top wall>      <top wall>
<left wall>     <data/space>    <space>

Ponieważ prawa kolumna nie zawiera żadnych informacji, program identyfikuje komórki jako dowolny region 2 × 2 ze znakiem +w lewym górnym rogu.

To pozostawia nam 3 rodzaje komórek:

• I Komórki : Komórki prawidłowo znajdujące się w labiryncie.
• Komórki R : Komórki znajdujące się na prawo od labiryntu. Są one tworzone przez wypełnienie używane do umieszczenia wejścia lub wyjścia. Na przykład wyjście Uw przypadku testowym 1 znajduje się w komórce R.
• Komórki B : Komórki poniżej labiryntu. Podobnie jak komórki R, są one tworzone przez wypełnienie.

W nowym formacie komórki są reprezentowane jako ciąg o zmiennej długości:

<left wall> <column number> <top wall/exit marker> <path>

Lewa i górna ściana są kopiowane z oryginalnego formatu. Numer kolumny jest oparty na poziomej pozycji komórki i służy do wyrównywania (identyfikacja komórek bezpośrednio nad sobą / pod sobą). Ścieżka to ciąg alfabetyczny używany podczas fazy wypełniania, aby zapisać najkrótszą ścieżkę do osiągnięcia tej komórki. Znacznik ścieżki i wyjścia zostanie dokładniej wyjaśniony.

Półkomórki

Chociaż większość labiryntu to komórki, istnieją obszary labiryntu, które nie są komórkami:

• R Półkomórki : Jeśli nie ma odpowiedniego wypełnienia, litery +s wzdłuż prawej ściany nie tworzą komórek, ponieważ znajdują się w ostatniej kolumnie.
• L Półkomórki : Jeśli pozostało wypełnienie, komórki nie mogą się tam utworzyć, ponieważ nie ma +po lewej stronie. Na przykład wejście Iw przypadku testowym 1 znajduje się w półkomórce L.

Technicznie rzecz biorąc, nad labiryntem znajdują się pół-komórki T (gdy jest górne wypełnienie) i pół-komórki B (wzdłuż dolnej ściany, gdy nie ma dolnego wypełnienia), ale nie są reprezentowane w nowym formacie.

Górny rząd połowy komórki zostałby usunięty w ramach konstruowania pełnych komórek w tym samym rzędzie, więc pół komórki są reprezentowane w nowym formacie jako

<wall/exit marker>? <path>

Pół-komórki R są po prostu |. Pół-komórki L ma tylko Iścieżkę, tylko znacznik wyjścia i pustą ścieżkę lub pustą ścianę.

Wejścia i wyjścia

Jeśli wejście znajduje się po lewej, prawej lub dolnej części labiryntu, znacznik wejścia Inaturalnie znalazłby się w (pół) komórce jako ścieżka, którą można usunąć po zwróceniu ostatniej ścieżki.

Jeśli wejście znajduje się powyżej labiryntu, pierwszy (w dół) krok jest wykonywany podczas fazy budowy, ponieważ półkomórki T są usuwane podczas budowy. To utrzymuje wykonalną ścieżkę w pełnej komórce. Górna ściana jest następnie zamykana.

Jeśli wyjście znajduje się po lewej, prawej lub dolnej części labiryntu, wówczas Unaturalnie byłoby zawarte w (pół) komórce. Aby uniknąć pomyłki jako ścieżki, &zamiast niego używany jest znacznik wyjścia inny niż alfanum U. Znacznik wyjścia jest osadzony w komórce lub półkomórce (jak określono powyżej).

Jeśli wyjście znajduje się powyżej labiryntu, byłby to jedyny otwór, który może przejść powyżej górnego rzędu komórek (ponieważ ten dla wejścia, jeśli jest obecny, byłby już zamknięty). Każda ścieżka prowadząca do tej dziury może wyjść z labiryntu, wykonując krok w górę.

Na koniec każda komórka B zawierająca wejście lub wyjście musi zamknąć lewą ścianę, aby zapobiec „rozwiązaniu” labiryntu przez spacery wzdłuż komórek B. Wejścia i wyjścia w komórkach R lub L półkomórkach nie wymagają dalszego przetwarzania, ponieważ algorytm wypełniania zalewowego nie pozwala na ruchy pionowe do / z nich.

Przykład

Na przykład pierwszy przypadek testowy

·+--+--+--+--+--+--+--+--+--+--+·
I···············|·····|········|·
·+··+--+--+--+··+··+··+··+--+··+·
·|···········|·····|··|··|·····|·
·+--+--+--+··+--+--+··+··+··+--+·
·|···········|·····|·····|·····|·
·+··+--+--+··+··+--+--+··+--+··+·
·|·····|·····|·····|·····|·····|·
·+--+··+··+--+--+··+--+--+··+··+·
·|·····|········|········|··|··|·
·+··+--+--+--+··+--+--+··+··+··+·
·|·····|·····|·····|········|··|·
·+--+··+··+--+--+··+--+--+--+--+·
·|··|··|·················|·····|·
·+··+··+--+--+--+··+--+··+··+··+·
·|·····|········|··|··|··|··|··|·
·+--+--+··+··+--+··+··+··+--+··+·
·|········|·····|·····|··|·····|·
·+··+--+--+--+··+··+··+··+··+--+·
·|···········|·····|··|·········U
·+--+--+--+--+--+--+--+--+--+--+·

jest

I·3-·6-·9-·12-·15-|18-·21-|24-·27-·30-|33·
·|3··6-·9-·12-|15··18·|21·|24·|27-·30·|33·
·|3-·6-·9-·12·|15-·18-|21··24·|27··30-|33·
·|3··6-|9-·12·|15··18-|21-·24·|27-·30·|33·
·|3-·6·|9··12-·15-|18··21-·24-|27·|30·|33·
·|3··6-|9-·12-|15··18-|21-·24··27·|30·|33·
·|3-|6·|9··12-·15-·18··21-·24-|27-·30-|33·
·|3··6·|9-·12-·15-|18·|21-|24·|27·|30·|33·
·|3-·6-·9·|12··15-|18··21·|24·|27-·30·|33·
·|3··6-·9-·12-|15··18·|21·|24··27··30-·33&

w nowym formacie. Można konwertować inne labirynty tutaj .

Faza budowy

Faza budowy składa się z pierwszych 13 linii programu.

¶U
¶&

Konwertuje wyjście w L Półkomórka, aby wyjść z markera

+`·(\w.+)$
|$1

Dodaje ściany po lewej stronie wejścia i wyjścia w komórkach B.

((.)+I.+¶.+¶(?<-2>.)+)·
$1v

Robi pierwszy krok, jeśli wejście znajduje się nad labiryntem

+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6

Dokonuje faktycznej konwersji

·v
-v

Zamyka otwór górnego wejścia

G`1

Zachowuje tylko linie z 1. Ponieważ labirynty mają szerokość co najmniej 5 komórek, a liczby kolumn występują z przyrostem 3, linia z komórkami nowego formatu musi zawierać numer kolumny między 10 a 19.

·U
&

Konwertuje wyjście w komórce R lub komórce B, aby wyjść z markera

Faza napełnienia

Faza wypełnienia tworzy kolejne 8 wierszy programu. Wykorzystuje algorytm wypełniania zalania, aby wypełnić wszystkie komórki najkrótszą ścieżką do osiągnięcia od wejścia.

{`

Umieszcza całą fazę wypełnienia w pętli, aby wypełnić cały labirynt.

\B·\d+.(\w+)
$1K$&

Robi to każda komórka zdolna do poruszania się w lewo. Komórka może się poruszać w lewo, jeśli

1. ma niepustą ścieżkę
2. ma pustą lewą ścianę; i
3. komórka lub komórka L po lewej stronie ma pustą ścieżkę

(\w+)·\d+.\B
$&$1r

Następnie robi to każda komórka, która może się poruszać w prawo. Komórka może się poruszać w prawo, jeśli

1. ma niepustą ścieżkę
2. komórka po prawej stronie ma pustą lewą ścianę; i
3. komórka po prawej stronie ma pustą ścieżkę

(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v

Następnie robi to każda komórka, która może przejść w dół. Komórka może się przesunąć w dół, jeśli

1. ma niepustą ścieżkę
2. po prawej stronie ma co najmniej jedną komórkę lub półkomórkę (tj. nie jest komórką R)
3. komórka poniżej (tj. komórka w następnym wierszu z tym samym numerem kolumny) ma pustą górną ścianę lub znacznik wyjścia; i
4. komórka poniżej ma pustą ścieżkę

Zauważ, że L Pół-komórki nie mogą się przesunąć w dół, ponieważ nie mają numerów kolumn.

\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A

Następnie robi to każda komórka, która może się przesunąć w górę. Komórka może się poruszać w górę, jeśli

1. ma niepustą ścieżkę
2. ma pustą górną ścianę
3. komórka powyżej ma co najmniej jedną komórkę lub półkomórkę po prawej stronie; i
4. komórka powyżej ma pustą ścieżkę

Faza powrotu

Faza powrotu stanowi ostatnie 5 wierszy programu. Ta faza wyszukuje i zwraca ścieżkę wypełnioną do komórki wyjściowej.

Wzór ścieżki przy wyjściu zależy od tego, gdzie jest wyjście:

1. Jeśli wyjście znajduje się w pół-komórce L, wówczas ta pół-komórka będzie & <path>
2. Jeśli wyjście znajduje się w komórce R lub komórce B, wówczas komórka będzie <left wall> <column number> & <path>
3. Jeśli wyjście znajduje się w półkomórce T, to jak wspomniano powyżej, komórka I prowadząca do wyjścia byłaby <left wall> <column number> · <path>w górnym rzędzie.

^.+\d·(\w+)
&$1A

Znajduje komórkę w górnym wierszu z pustą górną ścianą i niepustą ścieżką. Zajmuje się to ostatnim przypadkiem, dodając ostatni krok i znacznik wyjścia.

M!`&\w+

Dopasowuje i zwraca niepustą ścieżkę po znaczniku wyjścia.

I|&

Usuwa znacznik wyjścia i Iprefiks ścieżki.

Perl 6 , 259 295 bajtów

{my \a=S:g/(.)$0+/{$0 x($/.comb+.5)*2/3}/;sub f (\c,\v,*@p) {with (c ne any v)&&a.lines».comb[+c[0];+c[1]] ->$_ {for (/\s/??10011221!!/I/??a~~/^\N*I|I\N*$/??2101!!1012!!'').comb X-1 {f [c Z+$^a,$^b],(|v,c),@p,chr 8592+$++}
take @p if /U/}}
[~] (gather f a~~/(\N+\n)*(.)*I/,[]).min(+*)[1,3...*]}

Jak to działa

1. my \a = S:g/ (.) $0+ /{ $0 x ($/.chars + .5) * 2/3 }/;

To ściska labirynt, dzięki czemu wewnątrz każdej komórki jest 1x1 zamiast 2x1 znaków spacji:

 + - + - + - + - + - + + - + - + - + - + - + 
Ja | | | Ja | | |
 + + - + - + + + + + - + - + + + 
 | | | | | | | |
 + + - + + + + + + - + + + + 
 | | | | | -> | | | | |
 + + + - + + + + + + - + + + 
 | | | | | |
 + - + + + - + - + + - + + + - + - + 
 | | U | | U
 + - + - + - + - + - + + - + - + - + - + - +

2. sub f (\c,\v,*@p) {
       with (c ne any v) &&                   # If the coordinate wasn't visited yet
            lines».comb[+c[0];+c[1]] -> $_ {  # and a character exists there...
           for (                          # For each vector...
                /\s/ ?? 10011221 !!       #  from a cell: (0,-1), (-1,0), (0,1), (1,0)
                /I/  ?? a~~/^\N*I|I\N*$/
                         ?? 2101          #  from a top/bottom entrance: (1,0), (-1,0)
                         !! 1012          #  from a left/right entrance: (0,-1), (0,1)
                     !! ''                #  otherwise: none
               ).comb X-1 {
               f                       #   Recurse with arguments:
                   [c Z+ $^a, $^b],    #     c plus the vector
                   (|v, c),            #     v with c appended
                   @p, chr 8592 + $++  #     p with the correct Unicode arrow appended
           }
           take @p if /U/
       }
   }

Jest to funkcja rekurencyjnego wyszukiwania ścieżki. Przyjmuje trzy parametry: aktualną współrzędną c=(y,x), listę już odwiedzonych współrzędnych voraz przebytą pdo tej pory ścieżkę (jako listę znaków strzałek).

Jeśli postać na bieżącej współrzędnej jest spacją, powraca do czterech sąsiadów.
Jeśli znak na bieżącej współrzędnej to a I, to powraca do dwóch sąsiadów, którzy nie są „wzdłuż krawędzi”, aby wymusić rozwiązania, aby przejść przez labirynt, a nie wokół niego.
Jeśli znak na bieżącej współrzędnej to a U, to wywołuje takezgromadzony ciąg ścieżki.

3. [~] (gather f a ~~ /(\N+\n)*(.)*I/, []).min(+*)[1,3...*]

Funkcja rekurencyjna jest początkowo wywoływana ze współrzędną litery I, którą można znaleźć za pomocą wyrażenia regularnego.

gatherKluczowe zbiera wszystkie wartości, na których takezostała zwane wewnątrz funkcji, czyli wszystkich prawidłowych ścieżek Niecyklicznych przez labirynt.

Wybrano najkrótszą ścieżkę, co druga strzałka jest upuszczana, aby uwzględnić fakt, że potrzebne są dwa identyczne ruchy, aby przejść z jednej komórki do drugiej, a pozostałe strzałki są łączone w celu utworzenia łańcucha, który jest zwracany z lambda.

Python 2: 302 bajty

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1]
z=',l)for l in s]'
def f(s,b=1,o=0,n=0):
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z+"s=r([sub(' I ','+I+'%s);"%z*4)*b+"t=[sub('I  ','@@I'"+z
 if'I U'in`s`or n>3:return`o%4`+n/4*`s`
 return min(`o%4`+f(t,0,o,4*(t==s)),f(r(s),0,o+1,n+1),key=len)

Pobiera dane wejściowe jako tablicę ciągów o tej samej długości. Drukuje 0na prawo, 1na dół, 2na lewo i 3na górę.

Wyjaśnienie

Przyjąłem inne podejście niż inne odpowiedzi. Pomysł ogólny: szukaj rekurencyjnie, znajdując najkrótszą ścieżkę między przejściem do przodu a obróceniem planszy o 90 stopni.

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1] #Rotates the board counterclockwise
z=',l)for l in s]'    #Suffix for hacky exec golfing
def f(s,b=1,o=0,n=0): #b is 1 on initial call, 0 on every recursion
                      #o is orientation
                      #n is number of rotations
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z  #Squeeze the maze
      +"s=r([sub(' I ','+I+'%s);"%z*4)   #Add walls around the I to keep it in the maze
      *b                                 #Only if b is 1
      +"t=[sub('I  ','@@I'"+z            #Attempt to move right

 if'I U'in`s`or n>3:return`o%4`+n/4*`s`  #If the I is next to the U, return the orientation
                                         #If there were 4 rotations, return a long string
 return min(                             #Return the path with the shortest length:
            `o%4`+f(t,0,o,4*(t==s)),       #Moving forward if possible
            f(r(s),0,o+1,n+1),             #Rotating the board
        key=len)

Wypróbuj online!

JavaScript (ES6), 356 bajtów

a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

Pobiera dane wejściowe jako tablicę znaków 2D. Każda linia musi być wypełniona lewą spacją o jedno miejsce i nie może mieć spacji końcowej, bez względu na to, gdzie znajdują się punkty początkowe / końcowe.

Wykorzystuje pomysł smlsa, aby wycisnąć labirynt, aby każda komórka była 1x1, i usunąć powtarzające się strzały z wyniku.

Nieoznakowany i wyjaśniony

a=>(
    a=a.map(s=>s.filter((_,i)=>!i|i%3)),    // squish the maze to 1x1 cells
    g=([x,y])=>a[y]&&a[y][x],               // helper func to get maze value
    o=[],                                   // resulting movesets
    c=([x,y], m="", v=[]) =>                // recursive func to search
                                            // takes current point, moves, and visited spots
        [[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(// for each direction
            p=[x+j,y+k],
            !m & (!y | y>a[l="length"]-2) == i%2 |  // if first move, prevent moving out of maze
                v.includes(""+p) || (               // also prevent if already visited
                    g(p)<"!" ?                      // is this a space?
                        c(p, m+"v>^<"[i], [...v,""+p]) // check this spot recursively
                    : g(p)=="U" ?                   // if this the end?
                        o.push(                     // add moves to moveset
                            m.replace(/(.)\1/g,"$1")) // with double arrows removed
                    : 0
                )
        )),

    a.map((h,i)=>h.map((k,j)=>      // find the starting "I" and
        k=="I" && c([j,i])          // begin recursion at that point
    )),

    o.sort((a,b)=>a[l]-b[l])[0]     // get shortest path
)

Test Snippet

f=
a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

let tests = [" +--+--+--+--+--+--+--+--+--+--+\nI               |     |        |\n +  +--+--+--+  +  +  +  +--+  +\n |           |     |  |  |     |\n +--+--+--+  +--+--+  +  +  +--+\n |           |     |     |     |\n +  +--+--+  +  +--+--+  +--+  +\n |     |     |     |     |     |\n +--+  +  +--+--+  +--+--+  +  +\n |     |        |        |  |  |\n +  +--+--+--+  +--+--+  +  +  +\n |     |     |     |        |  |\n +--+  +  +--+--+  +--+--+--+--+\n |  |  |                 |     |\n +  +  +--+--+--+  +--+  +  +  +\n |     |        |  |  |  |  |  |\n +--+--+  +  +--+  +  +  +--+  +\n |        |     |     |  |     |\n +  +--+--+--+  +  +  +  +  +--+\n |           |     |  |         U\n +--+--+--+--+--+--+--+--+--+--+"," +--+--+--+--+--+\nI   |        |  |\n +  +--+--+  +  +\n |        |  |  |\n +  +--+  +  +  +\n |  |  |     |  |\n +  +  +--+  +  +\n |        |     |\n +--+  +  +--+--+\n |     |         U\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |     |     |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |           |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+","                                I\n +--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+\n |     |              |                    |  |\n +  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +\n |  |     |        |     |        |     |     |\n +--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+\n |     |  |  |  |     |     |           |     |\n +  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +\n |  |        |        |  |     |        |     |\n +  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+\n |  |     |     |        |  |     |     |     |\n +  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +\n |  |     |        |     |           |        |\n +  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+\n |     |     |        |        |  |     |     |\n +--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +\n |              |     |     |        |  |  |  |\n +  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +\n |     |  |     |  |  |        |        |  |  |\n +--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +\n |     |     |  |  |  |           |  |     |  |\n +--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +\n |     |        |  |  |     |        |  |  |  |\n +  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +\n |        |     |  |     |     |  |     |  |  |\n +--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +\n |  |        |        |     |        |     |  |\n +  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +\n |  |              |              |     |     |\n +  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+\n |     |                                |     |\n +--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+\n                             U"," +--+--+--+--+--+\nI               |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |               U\n +--+--+--+--+--+","  I  U\n +  +  +--+--+--+\n |  |        |  |\n +  +--+--+  +  +\n |     |     |  |\n +--+  +  +--+  +\n |        |  |  |\n +  +--+  +  +  +\n |     |        |\n +--+  +--+--+  +\n |     |        |\n +--+--+--+--+--+"," +--+--+--+--+--+\n |     |        |\n +  +--+  +--+  +\nI   |     |  |  |\n +  +  +--+  +  +\nU   |     |  |  |\n +--+--+  +  +  +\n |     |     |  |\n +  +--+--+--+  +\n |               \n +--+--+--+--+--+"];
S.innerHTML="<option>Tests"+Array(tests.length).fill().map((_,i)=>"<option>"+(i+1)).join``;

<select id=S oninput="I.value=S.selectedIndex?tests[S.value-1]:''"></select><br>
<textarea id=I rows=20 cols=50></textarea><br><button onclick="O.innerHTML=f(I.value.split`\n`.map(x=>[...x]))">Run</button>
<pre id=O>

Siatkówka , 416 bajtów

T` `+`^.*| ?¶.|.*$
I
#
{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\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

Wypróbuj online! Gdybym widział to pytanie, kiedy zostało pierwotnie opublikowane, prawdopodobnie jest to odpowiedź, którą bym udzielił, więc i tak wysyłam je, mimo że w Retinie jest znacznie lepsza odpowiedź. Wyjaśnienie:

T` `+`^.*| ?¶.|.*$

Wypełnij granicę. Pozwala to uniknąć chodzenia po labiryncie (np. W przypadku testowym 7).

I
#

Umieść nie alfabetyczny znacznik przy wejściu.

{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!))) 
$1w

Wypełnienie powodziowe od wyjścia do wejścia. Na każdym kroku użyj litery, aby wskazać najlepszy kierunek (dawniej - może to być znane graczom; zastanawiałem się również nad hjkl, ale uznałem, że jest to zbyt mylące). Ponadto wolą powtarzać ten sam kierunek; pozwala to uniknąć przechodzenia w lewo / prawo między dwiema sąsiadującymi pionowo komórkami.

^
w¶

Załóżmy, że pierwszy krok jest w dół.

w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1

Ale jeśli powyżej, po lewej lub prawej stronie wejścia znajduje się litera, zmień ją na pierwszy krok.

{`^(.*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 

Przesuń znacznik w kierunku ostatniego ruchu, odczytując kierunek następnego ruchu z kwadratu, do którego porusza się znacznik, i dodaj go do listy kierunków. To się powtarza, aż do Uosiągnięcia.

s`U.*

Usuń wszystko po wskazówkach, ponieważ nie jest już potrzebne.

(a|d)\1\1?
$1
ss
s
ww
w

Oryginalna siatka ma układ 3 × 2. Podczas ruchu w pionie, jeśli zygzakowimy w poziomie, wypełnienie zalewowe zoptymalizuje ruch i przesunie tylko 3n-1 znaki w poziomie, więc dzieląc przez trzy, musimy zaokrąglić w górę. Pionowo dzielimy przez 2.

Zbadałem również prawdziwe rozwiązanie siatki kwadratowej, tzn. Gdzie matryca znaków jest kwadratowa, a nie układem 3 × 2 z opcjonalną ramką. Prawdopodobnie niezgodna z pytaniem, możliwość transpozycji zmniejszyła liczbę bajtów do 350: Wypróbuj online!