Laberinto (5) - BFS P33254

Se te da el mapa de un laberinto, donde las casillas marcadas con un ‘#’ son paredes, y las marcadas con un ‘.’ son espacios vacíos. Partiendo de una casilla inicial vacía ‘A’, se te pide que explores por el laberinto siguiendo el siguiente proceso, conocido como BFS (Breadth-First Search, o búsqueda en anchura):

• Partiendo de la casilla inicial, avanza un paso en cualquier dirección. Las, como mucho, cuatro casillas vacías que encuentres son las casillas que están a 1 paso de distancia.

• Partiendo de cualquiera de las casillas que están a 1 paso de distancia, avanza un paso en cualquier dirección posible. Las casillas vacías que encuentres que no has visitado con anterioridad son las casillas que están a 2 pasos de distancia.

• En general, partiendo de cualquierda de las casillas que están a $n$ pasos de distancia y avanzando un paso en cualquier dirección posible, las casillas vacías que encuentres que no has visitado con anterioridad son las casillas que están a $n+1$ pasos de distancia.

Se te pide que hagas un programa que encuentre a qué distancia en pasos está cada casilla. Para hacerlo, te resultará útil utilizar una estructura de datos como una cola (‘queue’), donde puedes acumular las casillas que encuentres a distancia $n+1$ mientras estudias las casillas que están a distancia $n$.

Entrada

La entrada consiste de una línea con un número $k\geq 0$, seguido de $k$ casos. Cada caso empieza con una línea con las dimensiones $n$ (filas) y $m$ (columnas) del mapa, seguida de $n$ filas de $m$ caracteres ‘#’ y ‘.’ con la descripción del mapa, y un único carácter ‘A’ con la posición inicial.

Salida

Para cada caso, escribe el mapa usando exactamente $d$ caracteres para cada casilla, donde $d$ es el mínimo número de dígitos necesario para representar todos los números de pasos posibles (por ejemplo, si la casilla más lejana a la que llegas está a 103 pasos de distancia, entonces $d=3$). Si la casilla es una pared, escribe ‘X’ $d$ veces; si la casillas está vacía pero no es posible llegar a ella, escribe ‘.’ $d$ veces; de otro mod, escribe el número de pasos necesarios para llegar a ella usando exactamente $d$ dígitos (añade ceros a la izquierda si es necesario). Por último, escribe un espacio entre cada par de casillas de la misma fila. Fíjate en los ejemplos para salir de dudas.

Separa dos casos de pruebas con una línea con 3 asteriscos (‘**’).

Puntuación

• TestA:

  Entradas con $k\le 100$ y $n,m \le 10$, y donde todas las casillas situadas en los bordes del mapa son paredes (‘#’), como el Ejemplo 1.

• TestB:

  Entradas con $k\le 10$ y $n,m \le 200$, con mapas de todo tipo, como el Ejemplo 2.