Estás en una mazmorra de un piso. Hay un tesoro protegido por puertas cerradas. Las puertas se pueden abrir buscando las llaves correspondientes. Su objetivo es encontrar el camino más corto hacia el tesoro.

Entrada

La entrada será una cuadrícula bidimensional que representa el diseño inicial de la mazmorra.

###########
#$   #   g#
#    # ####
###G##    #
#    ####C#
#c  @     #
###########

Este es usted: @
Estas son paredes: #
Este es el tesoro: Las $
puertas cerradas son letras mayúsculas: A... Z
Cada puerta tiene su correspondiente llave en minúscula: a...z

• Siempre habrá uno @y uno $.
• La mazmorra siempre será rectangular.

• No se garantiza que el borde exterior de la mazmorra sea una pared. Esta es una mazmorra válida:

    $ 
  A## 
  @ a
  

• No se garantiza que el tesoro sea accesible. Algunas mazmorras pueden no tener solución.
• Puede haber puertas sin llave y puede haber llaves que no abren ninguna puerta.
• Nunca habrá puertas o llaves duplicadas.

Salida

Su programa debe imprimir una secuencia de R, L, U, D(u otros símbolos distintos 4) para representar el más corto camino posible hacia el tesoro. Aquí, RLUDsignifica derecha, izquierda, arriba y abajo, respectivamente. Si hay varias rutas más cortas, su programa solo necesita imprimir una de ellas.

• No puedes moverte hacia una pared.
• No puedes moverte fuera de los límites de las mazmorras.
• No se puede pasar a una puerta sin recoger la llave.
• Muévete a una tecla para recogerla.
• No es necesario abrir todas las puertas.

Si no es posible alcanzar el tesoro a través de una secuencia válida de movimientos, entonces su programa debe finalizar sin imprimir nada. (Se permite una nueva línea final).

Tanteo

Este es el código de golf, por lo que gana la respuesta con el conteo de bytes más bajo.

Casos de prueba

Cada caso de prueba tendrá la altura y el ancho de la mazmorra en la primera línea, y una ruta posible, con el número óptimo de movimientos, en la última línea.

1 2
@$
R (1)

3 3
  $
#Z#
@ z
RRLUUR (6)

3 5
c#d#$
 #C#D
@    
UUDDRRUUDDRRUU (14)

7 16
c   # b #  ###@ 
###     #       
  A #####  #### 
d #           e 
  B    ## ##### 
###    C   ##   
       # a DE $ 
RDDDDDDL (8)

16 37
#####################################
#    #ijk #a M   ##m##   #    #  R  #
#    #    #  #           #       ####
###J#### ############# ###    #  P b#
#e                       N  h #  ####
##########  ###########  ######     #
#        #  #    $    #  #    #  ####
#  D     H  #         #  #       Q f#
# EcF    #  #####A#####  ######  ####
#  G     #  #####B#####  #          #
#        K  #####C#####  ############
#        #                          #
########### #         #### ##### ####
#     # p   #         # n    #      #
# d         #    @    #     o#   r  #
#################Z###################
UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU (172)

No es posible alcanzar el tesoro en las siguientes mazmorras. Para estos casos de prueba, no debería haber salida.

1 3
@#$

7 11
#a#j#$#i#f#
# #E#F#c#H#
# #K#D#A#G#
#         #
#C#J# #I#B#
#h#d# #L#g#
#l#e#@#b#k#

10 25
#########################
   # fgh  #  # c B b #  #
 $ #      #  #   #   #  #
   ###### #  ##H###E##  #
   #                    #
   #     #########  ##e##
   Z @   D     y #  #   #
   #     #########  F  C#
   #     G          # Ad#
#########################

El siguiente fragmento se puede utilizar para validar respuestas.

function run() {var dungeonText = document.getElementById("dungeon").value;var dungeonLines = dungeonText.split("\n");var height = dungeonLines.length;var width = dungeonLines[0].length;var dungeon = new Array(height);for (i = 0; i < dungeon.length; i++) {var dungeonLine = dungeonLines[i];if (dungeonLine.length != width) {return error("The dungeon is not rectangular");} dungeon[i] = dungeonLines[i].split("");} var movesText = document.getElementById("moves").value;var moves = movesText.trim().split("");var moveCount = moves.length;var rowAt, colAt;for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == '@') {rowAt = r;colAt = c;}}} var treasure = false;while (moves.length > 0) {var move = moves[0];var row = rowAt,col = colAt;switch (move) {case 'R':col++;break;case 'L':col--;break;case 'U':row--;break;case 'D':row++;break;default:return print(dungeon, moves, "Invalid move");} if (row < 0 || col < 0 || row >= height || col >= width) {return print(dungeon, moves, "Out of bounds");} var target = dungeon[row][col];if (target.match(/[A-Z#]/)) {return print(dungeon, moves, "Path blocked");} if (target.match(/[a-z]/)) {var door = target.toUpperCase();for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == door) {dungeon[r][c] = ' ';}}}} if (target == '$') {treasure = true;} dungeon[row][col] = '@';dungeon[rowAt][colAt] = '.';rowAt = row;colAt = col;moves.shift();} if (treasure) {print(dungeon, moves, "Got the treasure in " + moveCount + " moves!");} else {print(dungeon, moves, "Failed to reach treasure");}} function error(message) {var result = document.getElementById("result");result.innerHTML = message;} function print(dungeon, moves, message) {var output = message + "\n";for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {output += dungeon[r][c];} output += "\n";} for (i = 0; i < moves.length; i++) {output += moves[i];} var result = document.getElementById("result");result.innerHTML = output;}

Dungeon:<br/><textarea id="dungeon" name="dungeon" rows="20" cols="40"></textarea><br/>Moves:<br/><textarea id="moves" name="moves" cols="40"></textarea><br/><button id="run" name="run" onclick="run();">Start</button><br/><br/>Result:<br/><textarea id="result" name="result" rows="20" cols="40" disabled></textarea><br/>

Perl, 157 152 151 bytes

Incluye +4 para -p0(no se puede contar solo como una extensión de -eporque se usa 'en varios lugares)

Corre con el laberinto en STDIN:

./keymaze.pl < maze.txt

keymaze.pl:

#!/usr/bin/perl -p0
1until$n{map/\n/&&"L1R-1U@+D-@+"=~s%\pL%$t=$1{$_}.$&;pos=$^H=-$'+s'@' '*"@-",s/\G[a-z\$ ]/\@/+s/$&/ /i?/\$/?$1{$_}:$\||=$t:0for"$_"%reg,$_,%1}++.$\}{

Reemplazar \ny ^Hpor sus versiones literales para la puntuación reclamada. Necesita alrededor de 1 hora y un poco menos de 2 Gigabytes en mi máquina para resolver el gran laberinto.

Java 8-1282 1277 1268 1259 1257 bytes

Esto pasa todas las pruebas. Sin embargo, para algunos de ellos da resultados ligeramente diferentes (cuando hay más de una forma óptima, lo cual no es un problema).

Para la cuarta prueba, da esto:

RDDDDDLD

En lugar de esto:

RDDDDDDL

Para la quinta prueba, da esto:

LLLLUUULLDDLLLLDLLLLLRRRRRRURRRUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLDDLLLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU

En lugar de esto:

UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU

Versión de golf:

import java.util.*;class G{int y,w,h,p;String C="",S,o,v;Map m=new HashMap();String q(int a){return a<1?"":"#"+q(a-1);}public static void main(String[]a)throws Exception{new G(new String(java.nio.file.Files.readAllBytes(new java.io.File(a[0]).toPath())));}G(String a){w=(a+"\n").indexOf(10)+3;String t=q(w)+a.replace("\n","##")+q(w);for(char j=65,k=97;j<91;j++,k++){if(t.indexOf(j)*t.indexOf(k)<0)t=t.replace(j,'#').replace(k,' ');}h=t.length()/--w;S=v=q(w*h);t=g(t);if(t!=v)System.out.print(t);}String g(String t){o=(String)m.get(t);if(o!=null)return o;if(t.indexOf(36)<0){if(S.length()>C.length())S=C;return"";}String d="";int f=t.indexOf(64),M[]=new int[w*h],N[]=new int[w*h];Queue<Integer>s=new ArrayDeque();s.add(f);while(!s.isEmpty()){y=s.poll();int[]P={y+1,y-1,y+w,y-w};for(int v:P){char j=t.replaceAll("[A-Z]","#").charAt(v);if(v!=f&j!=35&(N[v]<1|M[y]+1<M[v])){M[v]=M[y]+1;N[v]=y;s.add(v);if(j>32)d+=j;}}}o=d.chars().distinct().mapToObj(e->{String z="",c=C;for(y=t.indexOf(e);y!=f;y=N[y]){p=y-N[y];z=(p==w?"D":p==-w?"U":p==1?"R":"L")+z;}if(S.length()<=(C+z).length())return v;C+=z;String u=g(t.replace('@',' ').replace((char)e,'@').replace((char)(e-32),' '));C=c;return u==v?v:z+u;}).reduce(v,(a,b)->a.length()<b.length()?a:b);m.put(t,o);return o;}}

Versión sin golf

caracteristicas:

• Nombres de variables informativas;
• Comentarios explicativos y detallados;
• Ideación adecuada.

import java.util.*;

/**
 * @author Victor Stafusa
 */
class TreasureHunt {

    // Note: on normal (non-golfing programming) those variables should have been scoped properly.
    // They are instance variables just for golfing purposes.
    // On the golfed version, nextCellIndex and waypointCellIndex are the same variable. The same also happens to cachedValue and result. This happens is for golfing purposes.

    int nextCellIndex,
            width,
            height,
            waypointCellIndex,
            cellIndexDifference;

    String previousPath = "",
            bestSolutionSoFar,
            cachedValue,
            result,
            failureFlag;

    // This should be Map<String, String>, but the generics were omitted for golfing.
    // It is needed to avoid recomputing long partial dungeons (i.e. dynamic programming).
    Map cachedResults = new HashMap();

    // Returns a lot of hashes. Like aLotOfHashes(7) will return "#######".
    String aLotOfHashes(int howMany) {
        return howMany < 1 ? "" : "#" + aLotOfHashes(howMany - 1);
    }

    // Here is where our program starts.
    public static void main(String[] args) throws Exception {
        // Read all the content of the file from args[0] and put it into a string.
        // Pass that string as a parameter to the constructor.
        // The instance itself is useless - it is just a golfing trick.
        new TreasureHunt(new String(java.nio.file.Files.readAllBytes(new java.io.File(args[0]).toPath())));
    }

    // Pre-processs the source in order to format it in the way that we want:
    // * No separators between rows. It uses the (row * width + column) formula, so no separators are needed.
    // * An extra layer of wall is added in all sides. This naturally fix up problems about walking out of the edges of the board, wrapping-around or acessing invalid array indexes.
    // This is a constructor just for golfing purposes. Its instances are worthless.
    TreasureHunt(String originalSource) {

        // Finds the width by searching the first line-feed.
        // If there is just one line and no line-feed, the [+ "\n"] will ensure that it will not break.
        // The [+ 3] is because we will add a layer of walls around, so it will be widen by one cell in the left and one in the right (which is +2).
        // We still get one more in the width that will be decremented later to use that in the aLotOfHashes method below.
        // 10 == '\n'.
        width = (originalSource + "\n").indexOf(10) + 3;

        // Add a layer of walls in the top and in the bottom (using a lot of hashes for that).
        // Replaces the line-feed by a pair of walls, representing the rightmost wall of a row and the leftmost row of the following row.
        // Since there is no line-feed before the first line nor after the last line, we add more two walls to fill those.
        String newSource = aLotOfHashes(width) + originalSource.replace("\n", "##") + aLotOfHashes(width);

        // Remove the keys without door (replaces them as blank spaces) and the doors without keys (replaces them with walls.
        // This way, the resulting dungeon will always have matching keys and doors.
        // 65 == 'A', 97 == 'a', 91 == 'z'+1
        for (char door = 65, key = 97; door < 91; door++, key++) {

            // Now a little math trick. For each key or door, we find an index. If the key or door exist, it will be a positive number. Otherwise it will be negative.
            // The result will never be zero, because the zeroey position is filled with part of the layer of wall that we added.
            // If only one of the key and the door exist, the multiplication will be the product of two numbers with opposite signals, i.e. a negative number.
            // Otherwise (both exists or both don't), then the product will be positive.
            // So, if the product is negative, we just remove the key and the door (only one of them will be removed of course, but we don't need to care about which one).
            if (newSource.indexOf(door) * newSource.indexOf(key) < 0) {
                newSource = newSource.replace(door, '#').replace(key, ' ');
            }
        }

        // Knowing the source length and the width (which we fix now), we can easily find out the height.
        height = newSource.length() / --width;

        // Creates a special value for signaling a non-existence of a path. Since they are sorted by length, this must be a sufficiently large string to always be unfavoured.
        bestSolutionSoFar = failureFlag = aLotOfHashes(width * height);

        // Now, do the hard work to solve the dungeon...
        // Note: On the golfed version, newSource and solution are the same variable.
        String solution = solvingRound(newSource);

        // If a solution is found, then show it. Otherwise, we just finish without printing anything.
        // Note: It is unsafe and a bad practice to compare strings in java using == or != instead of the equals method. However, this code manages the trickery.
        if (solution != failureFlag) System.out.print(solution);
    }

    // This does the hard work, finding a solution for a specific dungeon. This is recursive, so the solution of a dungeon involves the partial solution of the dungeon partially solved.
    String solvingRound(String dungeon) {
        // To avoid many redundant computations, check if this particular dungeon was already solved before. If it was, return its cached solution.
        cachedValue = (String) cachedResults.get(dungeon);
        if (cachedValue != null) return cachedValue;

        // If there is no treasure in the dungeon (36 == '$'), this should be because the adventurer reached it, so there is no further moves.
        if (dungeon.indexOf(36) < 0) {
            if (bestSolutionSoFar.length() > previousPath.length()) bestSolutionSoFar = previousPath;
            return "";
        }

        String keysOrTreasureFound = ""; // Initially, we didn't found anything useful.
        int adventurerSpot = dungeon.indexOf(64), // 64 == '@', find the cell index of the adventurer.
                cellDistance[] = new int[width * height],
                previousWaypoint[] = new int[width * height];

        // Use a queue to enqueue cell indexes in order to floodfill all the reachable area starting from the adventurer. Again, screw up the proper user of generics.
        Queue<Integer> floodFillQueue = new ArrayDeque();
        floodFillQueue.add(adventurerSpot); // Seed the queue with the adventurer himself.

        // Each cell thies to populate its neighbours to the queue. However no cell will enter the queue more than once if it is not featuring a better path than before.
        // This way, all the reachable cells will be reached eventually.
        while (!floodFillQueue.isEmpty()) {
            nextCellIndex = floodFillQueue.poll();

            // Locate the four neighbours of this cell.
            // We don't need to bother of checking for wrapping-around or walking into an invalid cell indexes because we added a layer of walls in the beggining,
            // and this layer of wall will ensure that there is always something in each direction from any reachable cell.
            int[] neighbourCells = {nextCellIndex + 1, nextCellIndex - 1, nextCellIndex + width, nextCellIndex - width};

            // For each neighbouring cell...
            for (int neighbourCellIndex : neighbourCells) {
                // Find the cell content. Considers doors as walls.
                char neighbourCellContent = dungeon.replaceAll("[A-Z]", "#").charAt(neighbourCellIndex);

                if (neighbourCellIndex != adventurerSpot // If we are not going back to the start ...
                        & neighbourCellContent != 35 // ... nor walking into a wall or a door that can't be opened (35 == '#') ...
                        & (previousWaypoint[neighbourCellIndex] < 1 // ... and the neighbour cell is either unvisited ...
                            | cellDistance[nextCellIndex] + 1 < cellDistance[neighbourCellIndex])) //  ... or it was visited before but now we found a better path ...
                { // ... then:
                    cellDistance[neighbourCellIndex] = cellDistance[nextCellIndex] + 1; // Update the cell distance.
                    previousWaypoint[neighbourCellIndex] = nextCellIndex; // Update the waypoint so we can track the way from this cell back to the adventurer.
                    floodFillQueue.add(neighbourCellIndex); // Enqueue the cell once again.
                    if (neighbourCellContent > 32) keysOrTreasureFound += neighbourCellContent; // If we found something in this cell (32 == space), take a note about that.
                }
            }
        }

        // Brute force solutions chosing each one of the interesting things that we found and recursively solving the problem as going to that interesting thing.
        // Warning: This has an exponential complexity. Also, if we found something interesting by more than one path, it will compute that redundantly.
        result = keysOrTreasureFound.chars().distinct().mapToObj(keyOrTreasure -> {
            String tracingWay = "", savedPreviousPath = previousPath;

            // From our keyOrTreasure, trace back the path until the adventurer is reached, adding (in reverse order) the steps needed to reach it.
            for (waypointCellIndex = dungeon.indexOf(keyOrTreasure); waypointCellIndex != adventurerSpot; waypointCellIndex = previousWaypoint[waypointCellIndex]) {

                // Use the difference in cell indexes to see if it is going up, down, right or left.
                cellIndexDifference = waypointCellIndex - previousWaypoint[waypointCellIndex];
                tracingWay = (cellIndexDifference == width ? "D" : cellIndexDifference == -width ? "U" : cellIndexDifference == 1 ? "R" : "L") + tracingWay;
            }

            // If this path is going to surely be longer than some other path already found before, prune the search and fail this path.
            if (bestSolutionSoFar.length() <= (previousPath + tracingWay).length()) return failureFlag;

            // Prepare for recursion, recording the current path as part of the next level recursion's previous path.
            previousPath += tracingWay;

            // Now that we traced our way from the adventurer to something interesting, we need to continue our jorney through the remaining items.
            // For that, create a copy of the dungeon, delete the door of the key that we found (if it was a key),
            // move the adventurer to the thing that we just found and recursively solve the resulting simpler problem.
            String nextRoundPartialSolution = solvingRound(dungeon
                        .replace('@', ' ') // Remove the adventurer from where he was...
                        .replace((char) keyOrTreasure, '@') // ... and put him in the spot of the key or treasure.
                        .replace((char) (keyOrTreasure - 32), ' ')); // ... and if it was a key, delete the corresponding door ([- 32] converts lowercase to uppercase, won't do anything in the case of the treasure).

            // Recursion finished. Now, get back the previous path of the previous recursion level.
            previousPath = savedPreviousPath;

            // If the subproblem resulted in a failure, then it is unsolvable. Otherwise, concatenates the subproblem solution to the steps that we took.
            return nextRoundPartialSolution == failureFlag ? failureFlag : tracingWay + nextRoundPartialSolution;

        // From all the paths we took, choose the shorter one.
        }).reduce(failureFlag, (a, b) -> a.length() < b.length() ? a : b);

        // Now that we have the result of this recursion level and solved this particular dungeon instance,
        // cache it to avoid recomputing it all again if the same instance of the dungeon is produced again.
        cachedResults.put(dungeon, result);
        return result;
    }
}

Tomando entrada

Para ejecutarlo, intente esto:

javac G.java
java G ./path/to/file/with/dungeon.txt

O si está ejecutando la versión sin golf, reemplace la Gcon TreasureHunt.

El archivo debe contener la mazmorra. La entrada no debe terminar con un avance de línea. Además, solo acepta finales de línea en el \nformato. No funcionará con \r\no con \r.

Además, no valida ni desinfecta la entrada. Si la entrada tiene un formato incorrecto, el comportamiento no está definido (es probable que arroje una excepción). Si no se puede encontrar el archivo, se generará una excepción.

Observaciones

Mi primera implementación en algún lugar cerca de 1100 bytes no pudo resolver el quinto caso de prueba en un tiempo razonable. La razón de esto es porque mi implementación obliga a todas las permutaciones posibles de objetos coleccionables (es decir, las llaves y el tesoro) que son accesibles (es decir, no están encerrados en una habitación inaccesible).

En el peor de los casos, con las 26 llaves y el tesoro, ¡serían 27! = 10,888,869,450,418,352,160,768,000,000 permutaciones diferentes.

El OP no especificó que la respuesta debería ser algo que se ejecutara en un tiempo razonable. Sin embargo, considero que esta es una laguna que no me gustaría explotar. Entonces, decidí hacerlo funcionar en un tiempo aceptable para todos los casos de prueba. Para lograr eso, mi programa revisado presenta poda en las rutas de búsqueda que han demostrado ser peores de lo que algunos ya saben. Además, también almacena soluciones en caché (es decir, programación dinámica) para evitar volver a calcular muchas mazmorras idénticas que puedan surgir. Con eso, es capaz de resolver el quinto caso de prueba en poco más de un minuto en mi computadora.

La solución es recursiva. La idea es primero llevar al aventurero a algún objeto (una llave o el tesoro). En el caso de una llave, después de que el aventurero la alcanza, se genera una nueva mazmorra similar con la llave y la puerta borradas y el aventurero se mueve a donde estaba la llave. Con eso, la mazmorra más simple generada se resuelve de forma recursiva hasta el momento en que se alcanza el tesoro o el algoritmo concluye que no hay ningún elemento accesible. El orden de los artículos a visitar es forzado por la fuerza bruta con poda y almacenamiento en caché como se explicó anteriormente.

La búsqueda del camino entre el aventurero y los elementos se realiza con un algoritmo que se asemeja tanto a Dilkstra como a Dilkstra.

Finalmente, sospecho que este problema es NP-completo (bueno, la versión generalizada del mismo sin limitación en el número de puertas / llaves). Si esto es cierto, no espere soluciones que resuelvan óptimamente mazmorras muy grandes con miríadas de puertas y llaves en un tiempo razonable. Si se permitieran caminos subóptimos, entonces sería fácilmente manejable con algunas heurísticas (solo vaya al tesoro si es posible, de lo contrario, vaya a la tecla más cercana).