Minha prisão está segura?

58

Seu desafio recebe uma entrada de um layout da prisão para determinar se algum dos presos pode escapar.

Entrada

A entrada pode estar em qualquer formato razoável, como uma sequência, matriz, matriz de matrizes etc. A entrada será composta por três caracteres, neste caso #, Pe espaço. A entrada não conterá necessariamente os três caracteres.

  • #: Uma parede
  • P: Um prisioneiro
  • espaço: um espaço vazio

Um exemplo de entrada será semelhante a:

#####
#   #
# P #
#   #
#####

Resultado

Um valor verdadeiro / falso de se a prisão é segura ou não. A prisão só é segura se puder conter todos os presos. Se qualquer prisioneiro puder escapar, não é seguro.

Um prisioneiro pode escapar se não estiver totalmente cercado por um muro. Uma junção diagonal é totalmente fechada.

Casos de teste

############# Truthy
# P #  P#   #
#   #   # P #
#############

############# Truthy
# P    P    #
#   #   # P #
#############

############# Falsey
# P #  P#   #
#   #   # P #
########## ##

####          Truthy
#   #
 #   #
  # P ####
  ####

P             Falsey

###           Falsey
# #
# #
### P
TheLethalCoder
fonte
8
Sinto que isso é uma duplicata ou pelo menos um desafio semelhante. Bom desafio de qualquer maneira.
John Dvorak
2
@JanDvorak Pode ser, mas com meu Google Fu limitado, não consegui encontrar uma duplicata.
TheLethalCoder
2
relacionado (Preencha uma grade em 2D)
Esolanging Fruit
3
Seria bom ter exemplos de Falsey, nos quais os movimentos horizontal e vertical são necessários para escapar.
xnor
2
@tfbninja Não é realmente uma duplicata. Aquele pede para tentar extrapolar o programa dos dados fornecidos para determinar se a palavra está na caixa. Este é um floodfill BFS para verificar se há espaços não fechados mantendo valores marcados.
HyperNeutrino

Respostas:

54

Caracóis , 13 bytes

!(t\P(o\ ),o~

Experimente online!

Imprime 0para prisões inseguras e o tamanho da caixa delimitadora da entrada para prisões seguras.

A idéia é garantir que não possamos encontrar um caminho de uma Pcélula para fora dos limites ( ~) movendo-se apenas ortogonalmente ( o) pelos espaços. O té um teletransporte para que, independentemente de onde tentemos a partida, tente todas as posições iniciais possíveis para encontrar a P.

Martin Ender
fonte
23
A ferramenta certa.
Jonathan Allan
16

C # (.NET Core) , 485 480 474 470 421 408 bytes

A ferramenta e abordagem absolutamente erradas, mas mesmo assim ...

  • 7 bytes (e mais) salvos com as dicas úteis do TheLethalCoder.
  • 4 bytes salvos retornando um número inteiro.
  • Mais 4 bytes salvos graças (mais uma vez) ao TheLethalCoder, substituindo ' 'por 32nas comparações.
  • MUITOS bytes salvos refatorando o código.
  • Mais 13 bytes graças a (adivinhem quem?) TheLethalCoder. :) Eu continuo esquecendo suas dicas e ele continua me lembrando delas.
m=>{var p='P';int a=m.Length,b=m[0].Length,i=0,j,x,y;var c=new System.Collections.Stack();for(;i<a;i++)for(j=0;j<b;j++)if(m[i][j]==p)c.Push(new[]{i,j});while(c.Count>0){var t=(int[])c.Pop();x=t[0];y=t[1];if(x<1|x>a-2|y<1|y>b-2)return 0;foreach(var v in new[]{-1,1}){var z=x>0&x<a-1&y>0&y<b-1;if(z&m[x+v][y]==32){m[x][y]=p;c.Push(new[]{x+v,y});}if(z&m[x][y+v]==32){m[x][y]=p;c.Push(new[]{x,y+v});}}}return 1;}

Experimente online!

Basicamente, expanda as posições dos Ps sempre que houver um espaço em branco até atingir (ou não) a borda do layout.

Algumas licenças:

  • Eu uso a char[][]como entrada para o layout.
  • Retorna 0como inseguro e 1seguro.
Charlie
fonte
Você não pode fornecer informações adicionais para a função e assumir as dimensões ... A menos que você encontre uma meta post para me convencer do contrário.
TheLethalCoder
1>0e 1<0são mais curtos que truee false.
TheLethalCoder
11
Pode ==0se tornar <1? Você tem pelo menos 1 byte de espaço em branco irrelevante. Você pode remover os new[]? (Nem sempre funciona, mas às vezes gosta de int[] n = {1,2,3};).
TheLethalCoder
11
{m[x][y]= p; c.Push(new[]->{m[x][y]=p;c.Push(new[]
TheLethalCoder
11
Você pode comparar chars de ints então eu acredito que você pode substituir as ==' 'de ==32bytes para salvar. Você também deve fazer isso em comparações semelhantes.
TheLethalCoder
15

Perl 5 , 69 bytes

-10 bytes graças a @Grimy .

-2 bytes graças a @Neil .

77 bytes de código + -p0sinalizadores.

/
/;$_=s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s?redo:!/\A.*P|P.*\Z|^P|P$/m

Experimente online!

Algumas breves explicações:
A idéia é colocar um Plugar onde os prisioneiros possam ir. Se houver algum Pna primeira / última linha, ou na primeira / última coluna, os presos podem ir até lá e fugir, o que significa que a prisão não é segura.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/ssubstitui um espaço à direita de ou abaixo de a Ppor a P, ou um espaço à esquerda ou em cima de a P.
Por fim, /\A.*P|P.*\Z|^P|P$/mverifica se uma linha começa ou termina com a Pou se existe uma Pna primeira ou na última linha.

dada
fonte
abordagem legal usando regexps! (mas provavelmente muito caro quando o espaço cresce)
Olivier Dulac
Na verdade, não é que ineficiente. Em particular, não requer muito retorno, não existe *ou +, a correspondência mais longa que pode ser feita é o tamanho de uma linha ... Agora, é claro, se você comparar com uma abordagem mais manual, baseada em matrizes, por exemplo , sim, é bastante ineficiente!
Dada
11
Bytes -6 por fusão das duas substituições: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.
Grimmy
11
-2 bytes de golfe a substituição resultante da fusão: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.
Grimmy
2
@ Grimy muito bom golfe do regex! Obrigado :)
Dada
7

JavaScript (ES6), 134 133 bytes

Recebe a entrada como uma matriz de matrizes de caracteres. Devoluções 0(inseguras) ou 1(seguras).

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

Casos de teste

Arnauld
fonte
Os &&s podem ser apenas &?
TheLethalCoder
@TheLethalCoder Não é o primeiro, mas o segundo pode ser substituído por |. Obrigado!
precisa
Não sabia que o operador de propagação trabalhava em strings. Legal!
aebabis
6

JavaScript (ES6), 121 bytes

f=s=>s==(s=s.replace(eval('/( |P)([^]{'+s.search`
`+'})?(?!\\1)[ P]/'),'P$2P'))?!/^.*P|P.*$/.test(s)&!/^P|P$/m.test(s):f(s)

Recebe a entrada como uma string retangular delimitada por nova linha. Retorna 0 para inseguro e 1 para seguro. Com base na minha resposta para Detectar castelos fracassados , embora fosse mais eficiente testar um prisioneiro escapado a cada passo, em vez de eles terminarem de explorar a prisão.

Neil
fonte
2

Oitava, 64 55 bytes

@(a,z=padarray(a,[1 1]))~nnz(bwfill(z==35,1,1,4)&z>35);

Experimente online!

ou

Verifique todos os casos de teste!

Explicação:

z=padarray(a,[1 1])       %add a boundary(of 0s) around the scene
F = bwfill(z==35,1,1,4)   %flood fill the prison starting from the boundary
~nnz(F&z>35);             %if position of at least a prisoner  is filled then the prison is not secure 
rahnema1
fonte
2

APL (Dyalog Classic) , 40 bytes

{⊃2≠(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡(⌽1,⍉)⍣4'# '⍳⍵}

Experimente online!

'# '⍳⍵codificar '#', ' ', 'P'como 0 1 2

(⌽1,⍉)⍣4 surround com 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ número máximo de vizinhos de preenchimento de células diferentes de zero

⊃2≠ não temos um 2 no canto superior esquerdo?

ngn
fonte
1

Stax , 35 bytes CP437

ä¬my■╡╤▲l@┤êr*⌠\¶ƒläå─▄¶√¿ [Uy⌠Só4↔

Experimente online!

Certamente, uma linguagem de golfe sem um interno para lidar com a localização de caminhos também pode fazer isso!

Explicação

Usa o formato descompactado para explicar.

zLz]Y+Mys+y+{{{" P|P ""PP"Rm}Y!My!Mgphh' =
zLz]Y+Mys+y+                                  Surround the original matrix with four borders of whitespaces
            {                      gp         Iterate until a fixed point is found, return the single fixed point
             {              }Y!               Store the block in register Y and execute it
              {" P|P ""PP"Rm                  For each row, flood every space adjacent to a P with P.
                               My!            Transpose the matrix and do the flooding again
                                     hh' =    The final matrix has a space on the upper left corner that has not been flooded by P 
Weijun Zhou
fonte
1

SmileBASIC, 154 146 bytes

Eu esperava que uma resposta usando preenchimento fosse mais curta que isso.

DEF S P
FOR J=0TO 1X=1Y=1FOR I=0TO LEN(P)-1GPSET X,Y,-(P[I]=="#")GPAINT X,Y,-1,-J*(P[I]>@A)X=X*(P[I]>"31")+1INC Y,X<2NEXT
NEXT?!GSPOIT(0,0)GCLS
END

Substitua 31pelo caractere ASCII correspondente.

12Me21
fonte