¿Se puede resolver el laberinto?

20

El rompecabezas

  • Imprima 0 si no se puede resolver un laberinto n * m
  • Imprima 1 si se puede resolver un laberinto n * m (de 1 o más formas)

(¡así que no estoy pidiendo caminos, pero si es posible resolverlos!)

Matriz de entrada (2d):

[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]

XXXXXXXXX
XS     XX
X     X X
X    X  X
XX     FX
XXXXXXXXX

0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line

Regla La posición inicial es 0,0 y la posición final es n, m Solo puede moverse horizontal y verticalmente El código más corto gana

dwana
fuente
¿Debería la entrada ser una cadena o una matriz?
apsillers
3
Si hay un 1 (muro) en (n, m), ¿debería el código devolver 0?
trichoplax
3
(¿Lo mismo para una pared a (0,0)?)
Martin Ender
3
Dices que es un laberinto × m, pero tu indexación implica que es un laberinto (n + 1) × (m + 1).
Nick Matteo
3
Estoy deseando que llegue la solución regex =)
error

Respuestas:

7

CJam, 42 41 39 36 35 bytes

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=

Basado en las ideas de esta respuesta .

4 bytes gracias a Optimizer.

Formato de entrada:

[[0 0 0 0 0 0 1] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0] [1 0 0 0 0 0 0]]
jimmy23013
fuente
@Optimizer Gracias por eso. Pero luego encontré un camino más corto ...
jimmy23013
1
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Aunque se supone que los primeros tres caracteres de la entrada serán[[0
Optimizer
7

Dyalog APL, 27 caracteres

⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕

entrada evaluada APL distingue entre una matriz y un vector de vectores. Este programa supone que la entrada es una matriz.

(~×⍳∘⍴)Aes un tenedor equivalente a (~A) × ⍳⍴A. Es necesario evitar mencionar dos veces o introducir una variable.

⍴Aes la forma de A. Para una matriz de 4 por 7 la forma es 4 7.

Es el generador de índice. ⍳4es 1 2 3 4. ⍳4 7son los vectores (1 1)(1 2)...(4 7)dispuestos en una matriz de 4 por 7.

~Avoltea los pedazos de A.

×Al multiplicar ⍳⍴Apor los bits invertidos, conservamos las coordenadas de todas las celdas libres y convertimos todas las paredes 0 0.

,deshilacha la matriz de pares de coordenadas, es decir, la linealiza en un vector. En este caso, el vector consistirá en pares.

∘.-⍨Ao A∘.-Aresta elementos de Apairwise. Tenga en cuenta que aquí los elementos de Así mismos son pares.

| valor absoluto

+/¨suma cada par de valores absolutos. Esto nos da las distancias de la cuadrícula entre cada par de celdas en el laberinto, excepto para las paredes.

1≥solo estamos interesados ​​en vecinos a una distancia no mayor a 1, esto también excluye paredes. Ahora tenemos una matriz de adyacencia de un gráfico.

∨.∧⍨⍣≡ Floyd: algoritmo de cierre transitivo de Warshall

(f⍣n)A(no se usa aquí) donde nes un número entero es el operador de potencia. Se aplica fa A nlos tiempos: f f ... f A.

(f⍣g)Adonde ges una función, es el operador de punto fijo, también conocido como "límite de potencia". Se mantiene en el cálculo de la serie A, f A, f f A, ... hasta ((f⍣i)A) g ((f⍣(i+1))A)Devuelve verdadero para algunos i. En este caso usamos match ( ) como g.

∨.∧⍨Ao A∨.∧Aes un paso en el algoritmo de Floyd. f.ges una generalización de la multiplicación de matrices ( +.×), aquí usamos conjunción ( ) y disyunción ( ) en lugar de +y ×.

⊃⌽ Después de ⍣≡haber aplicado el paso suficientes veces y alcanzado un estado estable, debemos mirar hacia arriba en la esquina superior derecha de la matriz para obtener el resultado, así que lo volteamos ( ) y tomamos el primer elemento, arriba a la izquierda ( ).

Visualización de ⍣≡los pasos de

ngn
fuente
5

Python, 164 bytes

def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

Era reacio a publicar esto porque es prácticamente la forma en que normalmente haría el relleno de inundación, simplemente jugando al golf. Pero aquí está de todos modos.

Sp3000
fuente
4

Perl, 73 bytes

69 bytes de código + 4 bytes para -n0E(no estoy seguro de cómo se contaron las etiquetas en 2014, así que las conté por 4 en lugar de 2, pero no importa mucho).

/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0

Pruébalo en línea! (y si reemplaza la 1111011línea con 1111111, el laberinto ya no se puede resolver, y la salida será en 0lugar de 1: ¡ Pruébelo en línea! )

Explicaciones:

Este código encontrará todas las celdas accesibles del laberinto (y las marcará con un A): si una celda toca una celda marcada con un A, es accesible y nosotros también la marcamos con un A; y lo hacemos de nuevo ( redo). Eso se hace gracias a dos expresiones regulares: s/(^0|A)(.{@{+}})?0/A$2A/scomprueba si hay un espacio a la derecha o en la parte inferior de a A, mientras que s/0(.{@{+}})?A/A$1A/scomprueba si hay un espacio a la izquierda o en la parte superior de a A. Al final, si la última celda contiene un Aes accesible, de lo contrario no lo es (eso es lo que say/A$/+0verifica; +0está aquí para asegurarse de que el resultado sea 0o en 1lugar de una cadena vacía y 1).
Tenga en cuenta que /.*/coincidirá con una línea completa, configurando así@+al índice del final de la primera línea, que resulta ser el tamaño de una línea, lo que permite usar para .{@{+}}que coincidan exactamente tantos caracteres como haya en una línea. ( @{+}es equivalente a @+, pero solo el primero se puede usar en expresiones regulares)

Dada
fuente
Para este caso de prueba , su código considera que el laberinto tiene solución incluso si la posición final es 1.
Jitse
@Jitse Buena captura. En realidad, fue porque los enlaces TIO no estaban usando el código correcto (supongo que era una versión anterior y no lo vi). La respuesta sigue siendo válida, y he actualizado los enlaces TIO. Su ejemplo funciona bien: ¡ Pruébelo en línea!
Dada
¡Correcto! Gracias por la aclaración, me gusta este enfoque.
Jitse
@Jitse gracias, ese es uno de mis campos de golf favoritos :)
Dada
3

Ruby, 133 130 129 caracteres

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]

Entrada en STDIN, salidas 1o 0en STDOUT.

Molestamente largo. Simplemente realiza un relleno de 1s desde (0, 0), y luego verifica si el cuadrado "final" es a 1.

Pomo de la puerta
fuente
¿Tratará esto el laberinto como solucionable si ya contiene un 1 en (n, m)?
trichoplax
2

Java, 418 bytes

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

Mi primer código de golf. No sé por qué elegí Java, es tan malo para jugar al golf xD

El laberinto de ejemplo se ingresaría a través de stdin de esta manera:

......#;.....#.;....#..;#......
bace1000
fuente
1
Consejo profesional: asigne a su clase un nombre de un carácter, elimine el espacio entre String[]y a, y tome la entrada de los argumentos de la línea de comandos en lugar de StdIn, lo cual está permitido.
Pavel
1

Python 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

Esto se hizo mucho más largo de lo que pensé que sería :( De todos modos, agregaré una explicación una vez que ya no pueda jugar más golf.

FryAmTheEggman
fuente
1

J, 75 caracteres

Alimentación de la matriz de adyacencia (muy poco tiempo y memoria ineficientes). (¿Se llama potencia en inglés?)

   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Algunos casos de prueba:

   m1=. 0 0 0 0 0 0 1,. 0 0 0 0 0 1 0,.  0 0 0 0 1 0 0,. 1 0 0 0 0 0 0
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0
randomra
fuente
0

Python 3 , 184 bytes

f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))

Pruébalo en línea!

Matthew Jensen
fuente