Labirinto pode ser resolvido?

20

O quebra-cabeça

  • Imprima 0 se um labirinto n * m não puder ser resolvido
  • Imprima 1 se um labirinto n * m puder ser resolvido (de 1 ou mais maneiras)

(por isso não estou pedindo caminhos, mas se é possível resolver !!!)

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

Regra A posição inicial é 0,0 e a posição final é n, m Você só pode se mover horizontalmente e verticalmente.

dwana
fonte
A entrada deve ser uma sequência ou uma matriz?
Apsillers
3
Se houver 1 (parede) em (n, m), o código retornará 0?
Trichoplax
3
(Mesmo para uma parede em (0,0)?))
Martin Ender
3
Você diz que é um labirinto × m, mas sua indexação implica que é um labirinto (n + 1) × (m + 1).
Nick Matteo
3
Estou ansioso para a solução regex =)
flawr

Respostas:

7

CJam, 42 41 39 36 35 bytes

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

Com base nas idéias nesta resposta .

4 bytes graças ao 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
fonte
@ Optimizer Obrigado por isso. Mas então eu encontrei um caminho mais curto ...
jimmy23013
11
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Embora assuma que os três primeiros caracteres da entrada serão[[0
Otimizador
7

Dyalog APL, 27 caracteres

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

entrada avaliada. APL distingue entre uma matriz e um vetor de vetores. Este programa assume que a entrada é uma matriz.

(~×⍳∘⍴)Aé um garfo equivalente a (~A) × ⍳⍴A. É necessário evitar mencionar duas vezes ou introduzir uma variável.

⍴Aé a forma de A. Para uma matriz de 4 por 7, a forma é 4 7.

é o gerador de índice. ⍳4é 1 2 3 4. ⍳4 7são os vetores (1 1)(1 2)...(4 7)dispostos em uma matriz de 4 por 7.

~Avira os bits de A.

×multiplicando ⍳⍴Apelos bits invertidos, preservamos as coordenadas de todas as células livres e transformamos todas as paredes em 0 0.

,percorre a matriz de pares de coordenadas, ou seja, a lineariza em um vetor. Nesse caso, o vetor será composto por pares.

∘.-⍨Aou A∘.-Asubtrai elementos de Apares. Observe que aqui os elementos de Asão eles próprios pares.

| valor absoluto

+/¨somar cada par de valores absolutos. Isso nos dá as distâncias da grade entre cada par de células no labirinto, exceto as paredes.

1≥estamos interessados ​​apenas nos vizinhos a uma distância não superior a 1, isso também exclui muros. Agora temos a matriz de adjacência de um gráfico.

∨.∧⍨⍣≡ Floyd - algoritmo de fechamento transitivo de Warshall

(f⍣n)A(não usado aqui) onde num número inteiro é o operador de energia. Aplica-se fa A ntempos: f f ... f A.

(f⍣g)AOnde gé uma função, é o operador de ponto fixo, também conhecido como "limite de potência". Ele continua a calcular a série A, f A, f f A, ... até que ((f⍣i)A) g ((f⍣(i+1))A)retorna true para alguns i. Nesse caso, usamos match ( ) como g.

∨.∧⍨Aou A∨.∧Aé um passo no algoritmo de Floyd. f.gé uma generalização da multiplicação de matrizes ( +.×), aqui usamos conjunção ( ) e disjunção ( ) no lugar de +e ×.

⊃⌽ Depois de ⍣≡aplicar a etapa várias vezes e atingir um estado estável, devemos procurar o canto superior direito da matriz para obter o resultado, então giramos ( ) e pegamos o primeiro item superior esquerdo ( ).

Visualização das ⍣≡etapas

ngn
fonte
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

Eu relutava em postar isso porque é praticamente como eu normalmente faria o preenchimento de inundação, apenas um pouco de golfe. Mas aqui está, de qualquer forma.

Sp3000
fonte
4

Perl, 73 bytes

69 bytes de código + 4 bytes para -n0E(não tenho certeza de como as tags eram contadas em 2014, então eu as contei para 4 em vez de 2, mas isso não importa muito).

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

Experimente online! (e se você substituir a 1111011linha por 1111111, o labirinto não poderá mais ser solucionado e a saída será em 0vez de 1: Experimente on-line! )

Explicações:

Este código encontrará todas as células acessíveis do labirinto (e marque-as com a A): se uma célula toca uma célula marcada com a A, é alcançável e também a marcamos A; e fazemos isso de novo ( redo). Isso é feito graças a duas expressões regulares: s/(^0|A)(.{@{+}})?0/A$2A/sverifica se um espaço está à direita ou na parte inferior de a A, enquanto s/0(.{@{+}})?A/A$1A/sverifica se há um espaço à esquerda ou na parte superior de a A. No final, se a última célula contém um A, é alcançável, caso contrário, não é (é isso que say/A$/+0verifica; o +0está aqui para garantir que o resultado será 0ou em 1vez de uma string vazia e 1).
Observe que /.*/corresponderá a uma linha inteira, configurando assim@+ao índice do final da primeira linha, que passa a ser o tamanho de uma linha, que permite usar .{@{+}}para combinar exatamente o número de caracteres que há em uma linha. ( @{+}é equivalente a @+, mas apenas o primeiro pode ser usado no regex)

dada
fonte
Para este caso de teste , seu código considera o labirinto solucionável mesmo que a posição final seja 1.
Jitse 7/11
@Jitse Boa captura. Na verdade, era porque os links do TIO não estavam usando o código correto (acho que era uma versão anterior e não o localizei). A resposta ainda é válida e atualizei os links do TIO. Seu exemplo funciona bem: experimente online!
Dada
Oh, certo! Obrigado pelo esclarecimento, eu gosto dessa abordagem.
Jitse 7/11
@Jitse obrigado, esse é um dos meus favoritos golfe :)
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 em STDIN, saídas 1ou 0em STDOUT.

Irritantemente longo. Ele simplesmente faz uma inundação de 1s de (0, 0)e depois verifica se o quadrado "final" é a 1.

Maçaneta da porta
fonte
Isso tratará o labirinto como solucionável se ele já contiver 1 em (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);}}}

Meu primeiro código de golfe. Não sei por que escolhi o Java - é tão ruim para o golfe xD

Um exemplo de labirinto seria inserido via stdin assim:

......#;.....#.;....#..;#......
bace1000
fonte
11
Pro dica: nomear sua classe algo um caractere, abandonar o espaço entre String[]e a, e pegar as informações de argumentos de linha de comando em vez de StdIn, o que é 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))

Isso ficou muito mais longo do que eu pensava :( De qualquer forma, adicionarei uma explicação quando não puder mais jogar golfe.

FryAmTheEggman
fonte
1

J, 75 caracteres

Alimentação da matriz de adjacência (muito tempo e memória ineficientes). (É chamado de alimentação em inglês?)

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

Alguns casos de teste:

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

Experimente online!

Matthew Jensen
fonte