Un remplissage de chevalier est un remplissage d'inondation utilisant la connectivité de la pièce d'échecs de chevalier. Plus précisément:

 1 1
1   1
  0
1   1
 1 1

(0 est le point initial, 1s montre les cellules connectées)

Défi

Étant donné une grille 2D d'espaces et de murs et un emplacement initial, effectuez un remplissage de chevalier sur la grille. Le code le plus court gagne.

Règles

• Vous pouvez prendre des entrées et produire des sorties dans n'importe quel format que vous souhaitez (image, chaîne, tableau, peu importe). Vous pouvez prendre l'emplacement initial dans le cadre de la grille d'entrée ou comme coordonnée distincte. Aux fins de cette explication, le format suivant sera utilisé:

  ########    # = wall
  ########    x = initial location
  ## x  ##
  ##    ##
  ########
  ##    ##
  ########
  ########
  

• La sortie est une copie de la grille d'entrée avec le résultat de remplissage de chevalier ajouté

• Votre remplissage ne doit pas être de la même "couleur" que l'espace ou les murs, mais peut être le même que le marqueur d'emplacement initial. Par exemple, étant donné l'image ci-dessus, une sortie valide serait:

  ########    # = wall
  ########    @ = fill (could also have been x)
  ## @ @##
  ## @ @##
  ########
  ##@ @ ##
  ########
  ########
  

• Vous pouvez supposer que la grille d'entrée contiendra toujours un mur à 2 cellules de tous les côtés

• Vous pouvez supposer que l'emplacement initial ne sera jamais à l'intérieur d'un mur
• Vous pouvez supposer que la grille ne sera jamais supérieure à 1000 x 1000
• Les bâtis sont bien
• Le code le plus court (en octets) gagne

Cas de test

Dans tous les cas de test, #désigne un mur, indique un espace vide et xindique l'emplacement initial du remplissage. @désigne le remplissage de sortie.

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:

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

Octave, 73 octets

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

Démo en ligne!

* Certaines modifications s'appliquent pour s'exécuter dans rextester.

Une fonction qui prend un tableau 2D de 0 et 2 comme mur et un tableau de 0 et 1 comme emplacement initial et génère un tableau de 0 et 1 et 2.

JavaScript (ES6), 116 octets

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>

Basé sur ma réponse à Détecter les châteaux défaillants . Remplit en utilisant l' xart.

Python 3 , 394 387 381 356 352 347 319 313 154 139 octets

• 154 octets après avoir seulement compté la fonction principale et non la fonction concernant le formatage des E / S
• économisé 7 octets: grâce à @Jacoblaw et @ Mr.Xcoder: except:0
• sauvé 28 octets !!!: Merci à @ovs: débarrassé du try: exceptbloc et de plusieurs autres golfs
• Merci à @Dave pour le beau module de test.
• sauvé 6 octets: g[(a,b)]justeg[a,b]
• @nore a sauvé 15 octets !!! :

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

Essayez-le en ligne!

Mathematica, 117 octets

L'histoire habituelle: de puissants noms intégrés mais longs…

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

Essayez-le dans le bac à sable Wolfram!

Il prend deux entrées: d'abord la grille d'entrée sous la forme d'un tableau de 0s (pour les murs) et 1s (pour les espaces), puis un seul entier pour la position de départ, trouvé en numérotant la grille le long des lignes de haut en bas, par exemple

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

Vous pouvez appeler la fonction comme HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

La KnightTourGraphfonction construit un graphique avec des sommets correspondant à des positions dans la grille et des arêtes correspondant à des mouvements de chevalier valides, puis nous prenons Subgraphles sommets qui ne sont pas des murs, et trouvons le ConnectedComponentssommet de départ. La sortie est un graphique (représenté pivoté de 90 ° dans le sens inverse des aiguilles d'une montre) avec les sommets non muraux surlignés en rouge et les sommets pleins surlignés en jaune. Par exemple, pour le premier cas de test, la sortie ressemble à: