Entrada:

Um labirinto contendo os caracteres:

• -- (parede horizontal);
• | (parede vertical);
• + (conexão);
• (espaço para caminhar);
• I (Entrada);
• U (Saída).

Ou seja, uma entrada pode ser assim:

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

Saída:

O mais eficiente caminho que deve andar para começar a partir da entrada para a saída do labirinto (através do labirinto), indicado pelos caracteres indicando esquerda, direita, para cima e para baixo (ou seja >; <; ^; v).

Regras do desafio:

• Você pode receber a entrada em qualquer formato razoável. String-array, String única com novas linhas, conjunto de caracteres 2D, etc. são todos os formatos de entrada possíveis.
• A saída pode consistir em quatro caracteres distintos. Ou seja ><^v; →←↑↓; ⇒⇐⇑⇓; RLUD; 0123; ABCD; etc.)
• Você tem permissão para adicionar espaços ou novas linhas à saída, se preferir; isso é opcional.
• Os passos são contados por quadrado (veja quatro +símbolos para os quadrados) e não por caractere.
• O labirinto pode ser do tamanho de 5x5 a 15x15 e sempre será um quadrado (portanto, não haverá casos de teste para labirintos 5x10).
• Você pode assumir que todo labirinto possui um ou mais caminhos válidos do início ao fim e sempre gera o menor (consulte os casos de teste 4 e 5).
• Se houver vários caminhos com o mesmo comprimento, você poderá escolher qual deles enviar (consulte o caso de teste 6).
• Você não pode 'andar' fora dos limites do labirinto (consulte os casos de teste 7 e 8).

Regras gerais:

• Isso é código-golfe , então a resposta mais curta em bytes vence.
  Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
• As regras padrão se aplicam à sua resposta, para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados, programas completos. Sua chamada.
• As brechas padrão são proibidas.
• Se possível, adicione um link com um teste para o seu código.
• Além disso, adicione uma explicação, se necessário.

Casos de teste:

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<

Labirintos gerados usando esta ferramenta (e em alguns casos ligeiramente modificados).

Retina , 338 281 275 273 261 bytes

¶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|&

Experimente online!

Notas

• Devido a espaços em branco significativos, todos os espaços (0x20 ) são substituídos por interpunct ( ·) nesta resposta e no link TIO. O programa funciona bem se os espaços forem restaurados.
• Usa AvKrpara cima, baixo, esquerda e direita, respectivamente. Esses podem ser substituídos por quaisquer letras, excetoI .
• Leva cerca de 40s no TIO para o caso de teste 15 × 15. Seja paciente.Retrabalhou a peça para encontrar o caminho mais curto assim que o caminho chegou à saída. Acontece que estava demorando muito tempo.
• Pode quebrar completamente em labirintos com 66 ou mais células de largura, mas que podem lidar com labirintos de altura arbitrária. Uma correção para largura arbitrária leva +1 byte.

Explicação

O programa consiste em 3 fases:

• UMA fase de construção para converter o labirinto em um formato compacto mais fácil de trabalhar (detalhado abaixo).
• Uma fase de preenchimento para resolver o labirinto usando um algoritmo de preenchimento.
• Uma fase de retorno para retornar o caminho mais curto na saída.

Formato

Como o formato do labirinto original é bastante pesado, a primeira parte do programa o converte em um formato diferente.

Células

No formato original, cada célula é representada como uma região 2 × 3:

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

Como a coluna da direita não contém informações, o programa identifica células como qualquer região 2 × 2 com um + na parte superior esquerda.

Isso nos deixa com 3 tipos de células:

• Células I : Células que estão corretamente dentro do labirinto.
• Células R : Células que estão à direita do labirinto. Eles são criados pelo preenchimento usado para abrigar a entrada ou a saída. Por exemplo, a saídaU no caso de teste 1 está em uma célula R.
• Células B : Células que estão abaixo do labirinto. Como as células R, elas são criadas por preenchimento.

No novo formato, as células são representadas como uma sequência de comprimento variável:

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

As paredes esquerda e superior são copiadas do formato original. O número da coluna é baseado na posição horizontal da célula e é usado para alinhamento (identificação de células diretamente em cima / abaixo uma da outra). Caminho é uma sequência alfabética usada durante a fase de preenchimento para salvar o caminho mais curto para alcançar essa célula. O marcador de caminho e saída será mais explicado.

Meias células

Embora a maioria do labirinto seja de células, existem regiões do labirinto que não são células:

• R Meias células : se não houver preenchimento correto, o+ s ao longo da parede direita não formarão células, pois estão na última coluna.
• L Meias células : se houver preenchimento à esquerda, as células não poderão se formar, pois não haverá +à esquerda delas. Por exemplo, a entrada Ino caso de teste 1 está em uma meia célula L.

Tecnicamente, existem meias células T acima do labirinto (quando há preenchimento superior) e meias células B (ao longo da parede inferior quando não há preenchimento inferior), mas elas não são representadas no novo formato.

A linha superior de uma meia célula seria removida como parte da construção de células completas na mesma linha, para que as meias células sejam representadas no novo formato como

<wall/exit marker>? <path>

An meias células é apenas |. An L Meia célula tem apenas Io caminho, apenas o marcador de saída e um caminho vazio, ou apenas uma parede vazia.

Entradas e saídas

Se a entrada estiver à esquerda, direita ou parte inferior do labirinto, o marcador de entrada Iseria naturalmente incluído na (meia) célula como o caminho, que pode ser removido ao retornar o caminho final.

Se a entrada estiver acima do labirinto, o primeiro passo (para baixo) é dado durante a fase de construção, pois as meias células T são removidas durante a construção. Isso mantém um caminho viável em uma célula cheia. A parede superior é fechada depois.

Se a saída for para a esquerda, direita ou parte inferior do labirinto, então Useria naturalmente incluída na (meia) célula. Para evitar ser confundido com um caminho, o marcador de saída não alfanumérico &é usado em vez de U. O marcador de saída é incorporado em uma célula ou meia célula (conforme especificado acima).

Se a saída estiver acima do labirinto, seria o único buraco que pode ir acima da linha superior das células (já que o da entrada, se presente, já estaria fechado). Qualquer caminho que alcance esse buraco pode sair do labirinto dando um passo para cima.

Por fim, qualquer célula B que contenha a entrada ou a saída deve fechar a parede esquerda para evitar "resolver" o labirinto caminhando pelas células B. Entradas e saídas em Células R ou L Meia-célula não precisam de processamento adicional, pois o algoritmo de preenchimento não permite movimentos verticais de / para elas.

Exemplo

Como exemplo, o primeiro caso de teste

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

é

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&

no novo formato. Você pode converter outros labirintos aqui .

Fase de construção

A fase de construção compõe as 13 primeiras linhas do programa.

¶U
¶&

Converte a saída em L Meia célula para sair do marcador

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

Adiciona paredes à esquerda da entrada e saída nas células B

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

Dá o primeiro passo se a entrada estiver acima do labirinto

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

Executa a conversão real

·v
-v

Fecha o orifício de entrada superior

G`1

Mantém apenas linhas com a 1. Como os labirintos têm pelo menos 5 células de largura e o número de colunas ocorre em incrementos de 3, uma linha com células de novo formato deve conter um número de coluna entre 10 e 19.

·U
&

Converte a saída na célula R ou na célula B para sair do marcador

Fase de preenchimento

A fase de preenchimento compõe as próximas 8 linhas do programa. Ele usa um algoritmo de preenchimento de inundação para preencher todas as células com o caminho mais curto a ser alcançado a partir da entrada.

{`

Coloca toda a fase de preenchimento em um loop para preencher todo o labirinto.

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

Cada célula capaz de se mover para a esquerda o faz. Uma célula é capaz de se mover para a esquerda se

1. tem um caminho não vazio
2. tem uma parede esquerda vazia; e
3. a célula ou meia célula L à sua esquerda tem um caminho vazio

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

Então, cada célula capaz de se mover para a direita o faz. Uma célula é capaz de se mover para a direita se

1. tem um caminho não vazio
2. a célula à sua direita tem uma parede esquerda vazia; e
3. a célula à direita tem um caminho vazio

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

Então, cada célula capaz de se mover para baixo o faz. Uma célula é capaz de descer se

1. tem um caminho não vazio
2. tem pelo menos uma célula ou meia célula à sua direita (ou seja, não é uma célula R)
3. a célula abaixo dela (ou seja, a célula na próxima linha com o mesmo número de coluna) tem uma parede superior vazia ou o marcador de saída; e
4. a célula abaixo dela tem um caminho vazio

Observe que L meias-células não podem se mover para baixo, pois não possuem números de coluna.

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

Então, cada célula capaz de subir faz isso. Uma célula é capaz de subir se

1. tem um caminho não vazio
2. tem uma parede superior vazia
3. a célula acima dela tem pelo menos uma célula ou meia célula à sua direita; e
4. a célula acima dela tem um caminho vazio

Fase de retorno

A fase de retorno compõe as últimas 5 linhas do programa. Essa fase procura e retorna o caminho preenchido na célula de saída.

O padrão do caminho na saída depende de onde a saída está:

1. Se a saída estiver em uma meia célula L, essa meia célula seria & <path>
2. Se a saída estiver em uma célula R ou célula B, essa célula seria <left wall> <column number> & <path>
3. Se a saída estiver em uma meia célula T, como observado acima, a célula I que leva à saída estará <left wall> <column number> · <path>na linha superior.

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

Localiza uma célula na linha superior com uma parede superior vazia e um caminho não vazio. Isso cuida do último caso, adicionando o último passo e o marcador de saída.

M!`&\w+

Corresponde e retorna um caminho não vazio após um marcador de saída.

I|&

Remove o marcador de saída e o Iprefixo do caminho.

Perl 6 , 259 295 bytes

{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...*]}

Como funciona

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

Isso comprime o labirinto para que o interior de cada célula seja 1x1 em vez de caracteres de espaço 2x1:

 + - + - + - + - + - + + - + - + - + - + - + 
Eu | | Eu | |
 + + - + - + + + + + - + - + + + 
 | | | | | | | |
 + + - + + + + + + - + + + + 
 | | | | | -> | | | | |
 + + + - + + + + + + - + + + 
 | | | | | |
 + - + + + - + - + + - + + + - + - + 
 | | U | você
 + - + - + - + - + - + + - + - + - + - + - +

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

Esta é a função de busca de caminho recursiva. São necessários três parâmetros: a coordenada atual c=(y,x), a lista de coordenadas já visitadas ve o caminho ppercorrido até o momento (como uma lista de caracteres de seta).

Se o caractere na coordenada atual for um espaço, ele retornará aos quatro vizinhos.
Se o personagem na coordenada atual é a I, ele se repete para os dois vizinhos que não estão "ao longo da borda", forçando soluções a percorrer o labirinto e não em torno dele.
Se o caractere na coordenada atual for a U, ele chamará takea cadeia de caminho acumulada.

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

A função recursiva é chamada inicialmente com a coordenada da letra I, encontrada usando um regex.

A gatherpalavra-chave coleta todos os valores nos quais takefoi chamado dentro da função, ou seja, todos os caminhos não cíclicos válidos pelo labirinto.

O caminho mais curto é escolhido, cada segunda seta é descartada para explicar o fato de que são necessários dois movimentos idênticos para passar de uma célula para a próxima e as setas restantes são concatenadas para formar a sequência retornada do lambda.

Python 2: 302 bytes

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)

Recebe entrada como uma matriz de cadeias, todas com o mesmo comprimento. Imprime 0para a direita, 1para baixo, 2para esquerda e 3para cima.

Explicação

Adotei uma abordagem diferente das outras respostas. Ideia geral: procure recursivamente encontrando o caminho mais curto entre avançar e girar a prancha 90 graus.

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)

Experimente online!

JavaScript (ES6), 356 bytes

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])

Recebe a entrada como uma matriz 2D de caracteres. Cada linha deve ser preenchida à esquerda por um espaço e não deve ter espaço à direita, não importa onde estejam os pontos de partida / chegada.

Usa a ideia de smls de o labirinto para tornar cada célula 1x1 e remover setas repetidas da saída.

Ungolfed e Explained

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
)

Snippet de teste

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>

Retina , 416 bytes

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

Experimente online! Se eu tivesse visto essa pergunta quando foi publicada originalmente, esta provavelmente é a resposta que eu daria, então estou postando mesmo assim, mesmo que haja uma resposta muito melhor na Retina. Explicação:

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

Preencha a borda. Isso evita caminhar ao redor do labirinto (por exemplo, no caso de teste 7).

I
#

Coloque um marcador não alfabético na entrada.

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

Preenchimento de inundação da saída para a entrada. Em cada etapa, use uma letra para indicar a melhor direção a seguir (wasd - isso pode ser familiar para os jogadores; eu também havia considerado o hjkl, mas achei muito confuso). Além disso, prefira repetir a mesma direção; isso evita ir para a esquerda / direita entre duas células adjacentes verticalmente.

^
w¶

Suponha que o primeiro passo esteja abaixo.

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

Mas se houver uma letra acima, esquerda ou direita da entrada, mude para a primeira etapa.

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

Mova o marcador na direção do último movimento, lendo a direção do próximo movimento a partir do quadrado para o qual o marcador está se movendo e adicione-o à lista de direções. Isso se repete até que Useja alcançado.

s`U.*

Exclua tudo após as instruções, pois não é mais necessário.

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

A grade original está em um layout 3 × 2. Ao mover verticalmente, se zig-zag horizontalmente, o preenchimento de inundação otimizará o movimento e moverá apenas 3n-1 caracteres horizontalmente; portanto, ao dividir por três, precisamos arredondar para cima. Verticalmente, apenas dividimos por 2.

Também investiguei uma solução de grade quadrada verdadeira, ou seja, onde a matriz de caracteres é ela própria quadrada, em vez de ser um layout 3 × 2 com uma borda opcional. Embora provavelmente não esteja em conformidade com a pergunta, a capacidade de transpor reduziu a contagem de bytes para 350: Experimente on-line!