Reglas:
En este juego comienzas en la parte superior de una cuadrícula rectangular de tamaño N x M compuesta de paredes y espacios abiertos. La entrada es N líneas de M caracteres, donde a .
especifica un espacio abierto y a x
especifica un muro. Su programa debería generar el número K más pequeño de manera que exista una ruta desde la esquina superior izquierda a la esquina inferior derecha (sin diagonales) que cruza las paredes K.
Por ejemplo, dada la entrada:
..x..
..x..
xxxxx
..x..
..x..
su programa debería salir 2
.
Otros ejemplos:
salida 4
:
xxxxx
x.x.x
x.x.x
x..xx
salida 0
:
.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.
salida 6
:
xx
xx
xx
xx
xx
Cositas extra:
Si le facilita la vida, puede especificar N y M como parámetros de línea de comando.
Crédito adicional si puede hacer que su programa imprima la ruta de una forma u otra.
Respuestas:
Rubí 1.9
(235)(225)(222)(214)No sé si esto es más corto que un programa basado en Dijkstra, pero pensé que probaría un enfoque diferente. Esto usa expresiones regulares en un bucle para marcar cada espacio con el número mínimo de paredes requeridas para alcanzarlo.
La entrada se especifica como un archivo en la línea de comando, es decir
Sin golf:
fuente
Perl 5.10 (164)
Muy similar a la solución de migimaru, solo con ese toque adicional de Perl. 5.10 es necesario para
\K
adentros///
.fuente
Python
406378360348418 caracteresDijkstra simplificado, ya que los movimientos con peso están en el
x
campo. Se realiza en "ondas", primer bucle con encontrar.
campos tocando el frente y establecerlos en el mismo peso, que una vez encontrarx
campos tocando el frente y establecerlos en el+1
peso. Repita mientras no haya más campos no visitados.Al final sabemos el peso de cada campo.
La entrada se especifica como un archivo en la línea de comando:
Actualización: imprime la ruta.
fuente
Versión C ++ (
610607606584)Implementa el algoritmo de Dijkstra.
Sin golf:
fuente