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
x
indica 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:
##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############
Respostas:
Oitava, 73 bytes
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.
fonte
pkg load ...
quando executado fora da estrutura de teste? Seimdilate
&de2bi
estiver disponível sem importações explícitas, tudo bem.-auto
remoção, não há problema, e acho que essa resposta não usa novos recursos.JavaScript (ES6), 116 bytes
Com base na minha resposta para Detectar falha de castelos . Preenche usando
x
s.fonte
Python 3 ,
394387381356352 347 319 313 154139 bytesexcept:0
try: except
bloco e de vários outros campos de golfeg[(a,b)]
comog[a,b]
Experimente online!
fonte
except:pass
?except:0
Mathematica, 117 bytes
A história de sempre: poderosos embutidos, mas nomes longos…
Experimente na sandbox Wolfram!
São necessárias duas entradas: a primeira é a grade de entrada como uma matriz de
0
s (para as paredes)1
es (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 exemploVocê pode chamar a função como
HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20]
.A
KnightTourGraph
funçã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 pegamosSubgraph
os vértices que não são paredes e encontramos oConnectedComponents
vé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:fonte
f=...
f[{0,...,0;0,...,0}, 19]
e similares falharam miseravelmente.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!