Cavaleiro-preenche uma grade

15

Um preenchimento de cavaleiro é um preenchimento de inundação usando a conectividade da peça de xadrez do cavaleiro. Especificamente:

 1 1
1   1
  0
1   1
 1 1

(0 é o ponto inicial, 1s mostra as células conectadas)

Desafio

Dada uma grade 2D de espaços e paredes, e uma localização inicial, execute um preenchimento de cavaleiro na grade. O menor código vence.

Regras

  • Você pode receber e produzir saída em qualquer formato que desejar (imagem, string, array, qualquer que seja). Você pode usar o local inicial como parte da grade de entrada ou como uma coordenada separada. Para os fins desta explicação, o seguinte formato será usado:

    ########    # = wall
    ########    x = initial location
    ## x  ##
    ##    ##
    ########
    ##    ##
    ########
    ########
    
  • Saída é uma cópia da grade de entrada com o resultado de preenchimento do cavaleiro adicionado

  • Seu preenchimento não deve ter a mesma "cor" que o espaço ou as paredes, mas pode ser o mesmo que o marcador de local inicial. Por exemplo, dada a imagem acima, uma saída válida seria:

    ########    # = wall
    ########    @ = fill (could also have been x)
    ## @ @##
    ## @ @##
    ########
    ##@ @ ##
    ########
    ########
    
  • Você pode supor que a grade de entrada sempre contenha uma parede de duas células em todos os lados

  • Você pode assumir que o local inicial nunca estará dentro de uma parede
  • Você pode supor que a grade nunca será maior que 1000 x 1000
  • Builtins are fine
  • O código mais curto (em bytes) vence

Casos de teste

Em todos os casos de teste, #denota uma parede, indica espaço vazio e xindica a localização inicial do preenchimento. @indica o preenchimento da saída.

Input 1:

########
########
## x  ##
##    ##
########
##    ##
########
########

Output 1:

########
########
## @ @##
## @ @##
########
##@ @ ##
########
########

Input 2:

############
############
## ##    x##
## ##     ##
#####     ##
##        ##
############
############

Output 2:

############
############
## ##@@@@@##
##@##@@@@@##
#####@@@@@##
## @@@@@@@##
############
############

Input 3:

####################
####################
##  ##            ##
##  ##            ##
##  ##  ########  ##
##  ##  ########  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ########  ##
##  ##  ########  ##
##  ##        ##  ##
##  ##       x##  ##
##  ############  ##
##  ############  ##
##                ##
##                ##
####################
####################

Output 3:

####################
####################
##@@##@@@@@@@@@@@@##
##@@##@@@@@@@@@@@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@@@@@@@##@@##
##@@##@@@@@@@@##@@##
##@@############@@##
##@@############@@##
##@@@@@@@@@@@@@@@@##
##@@@@@@@@@@@@@@@@##
####################
####################

Input 4:

################
################
##           ###
##     x     ###
##  #######  ###
##  #######  ###
##  ##   ##  ###
##  ##   ##  ###
##  ##   ##  ###
##  ########  ##
##  ########  ##
##        ##  ##
##        ##  ##
################
################

Output 4:

################
################
##   @   @   ###
## @   @   @ ###
##  #######  ###
##@ ####### @###
##  ##   ##  ###
## @##   ##@ ###
##  ##   ##  ###
##@ ########@ ##
##  ########  ##
## @   @  ## @##
##   @   @##  ##
################
################

Input 5:

##############
##############
##         ###
##         ###
##         ###
##   ###   ###
##   #x#   ###
##   ###   ###
##         ###
##         ###
##         ###
##############
##############

Output 5:

##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############
Dave
fonte

Respostas:

4

Oitava, 73 bytes

function a=F(s,a)do;b=a;until(a=~s&imdilate(a,de2bi(")0#0)"-31)))==b;a+=s

Demonstração Online!

* Algumas alterações aplicadas para execução no rextester.

Uma função que recebe uma matriz 2d de 0 e 2 como parede e uma matriz de 0 e 1 como localização inicial e gera uma matriz de 0 e 1 e 2.

rahnema1
fonte
Parece bom, mas isso não é necessário pkg load ...quando executado fora da estrutura de teste? Se imdilate& de2biestiver disponível sem importações explícitas, tudo bem.
Dave
@Dave Nas versões anteriores do oitava, incluindo a versão instalada no tio, era possível instalar um pacote para que ele pudesse carregar automaticamente, mas agora notei que esse recurso foi removido da oitava! por favor veja isto .
rahnema1
Justo. Contanto que você esteja direcionando uma versão anterior à -autoremoção, não há problema, e acho que essa resposta não usa novos recursos.
Dave
3

JavaScript (ES6), 116 bytes

f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\\1)[x ]/`),'x$2x'))=>s==t?s:f(t)

v=(s,l=s.search`
`)=>!/^(#+)\n\1\n[^]*x[^]*\n\1\n\1$/.test(s)|s.split`
`.some(s=>s.length-l|!/^##.+##$/.test(s))&&`Invalid Input`
textarea{font-family:monospace}
<textarea rows=11 cols=33 oninput=o.value=v(this.value)||f(this.value)></textarea><textarea rows=11 cols=33 id=o reaodnly></textarea>

Com base na minha resposta para Detectar falha de castelos . Preenche usando xs.

Neil
fonte
Você pode adicionar um snippet / link de teste?
officialaimm
2

Python 3 , 394387381356352 347 319 313 154 139 bytes

  • 154 bytes depois de contar apenas a função principal e não a função referente à formatação de E / S
  • salvou 7 bytes: graças a @Jacoblaw e @ Mr.Xcoder: except:0
  • salvou 28 bytes !!!: Graças a @ovs: se livrou do try: exceptbloco e de vários outros campos de golfe
  • Obrigado a @Dave pelo belo módulo de teste.
  • salvou 6 bytes: g[(a,b)]comog[a,b]
  • @nore salvou 15 bytes !!! :
def x(g,a,b,m):
 if(a,b)in g and"!">g[a,b]or m:
  g[a,b]="@"
  for i in 1,2,-1,-2:
   for j in 3-abs(i),abs(i)-3:g=x(g,a+i,b+j,0)
 return g

Experimente online!

officialaimm
fonte
1
você pode fazer except:pass?
jacoblaw
1
Eu tenho certeza que isso pode ser muito
golfe
2
@jacoblaw ainda melhor:except:0
Mr. Xcoder
1
319 bytes
ovs 24/06
1
Aqui está uma versão ligeiramente mais fácil de testar do TiO: Experimente online!
Dave
1

Mathematica, 117 bytes

A história de sempre: poderosos embutidos, mas nomes longos…

HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&

Experimente na sandbox Wolfram!

São necessárias duas entradas: a primeira é a grade de entrada como uma matriz de 0s (para as paredes) 1es (para espaços) e, em seguida, um único inteiro para a posição inicial, encontrada numerando a grade ao longo das linhas de cima para baixo, por exemplo

1  2  3  4  5
6  7  8  9  10
11 12 13 14 ...

Você pode chamar a função como HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

A KnightTourGraphfunção constrói um gráfico com os vértices correspondentes às posições na grade e as arestas correspondentes aos movimentos válidos dos cavaleiros, depois pegamos Subgraphos vértices que não são paredes e encontramos o ConnectedComponentsvértice inicial. A saída é um gráfico (mostrado girado 90º no sentido anti-horário) com os vértices que não são de parede destacados em vermelho e os vértices preenchidos em amarelo. Por exemplo, para o primeiro caso de teste, a saída se parece com:

Saída para o caso de teste 1: um gráfico com algumas áreas destacadas

Não é uma árvore
fonte
Bem, isso certamente parece o mais difícil de testar! Você poderia adicionar um exemplo de como invocá-lo na sandbox, para aqueles que não tocam no Mathematica desde os dias de universidade? Minhas tentativas f=... f[{0,...,0;0,...,0}, 19]e similares falharam miseravelmente.
21417 Dave
@ Dave, você pode chamar a função com HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&[{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}},20](para o primeiro caso de teste). Eu editei isso na pergunta - desculpe, não estava lá para começar!
Não é uma árvore