Eine Ritterfüllung ist eine Überflutungsfüllung, die die Konnektivität der Ritterschachfigur verwendet. Speziell:

 1 1
1   1
  0
1   1
 1 1

(0 ist der Anfangspunkt, 1s zeigt die verbundenen Zellen)

Herausforderung

Führen Sie bei einem 2D-Raster aus Räumen und Wänden und einer anfänglichen Position eine Ritterfüllung auf dem Raster durch. Kürzester Code gewinnt.

Regeln

• Sie können Eingaben und Ausgaben in jedem beliebigen Format (Bild, Zeichenfolge, Array, was auch immer) erstellen. Sie können die ursprüngliche Position als Teil des Eingaberasters oder als separate Koordinate verwenden. Für diese Erklärung wird das folgende Format verwendet:

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

• Die Ausgabe ist eine Kopie des Eingaberasters mit dem hinzugefügten Ritterfüllungsergebnis

• Ihre Füllung darf nicht dieselbe "Farbe" wie der Raum oder die Wände haben, sondern kann dieselbe sein wie die ursprüngliche Ortsmarkierung. In dem obigen Bild wäre eine gültige Ausgabe beispielsweise:

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

• Sie können davon ausgehen, dass das Eingabegitter immer eine 2-Zellen-Wand auf allen Seiten enthält

• Sie können davon ausgehen, dass sich der ursprüngliche Standort niemals innerhalb einer Wand befindet
• Sie können davon ausgehen, dass das Raster niemals größer als 1000x1000 ist
• Builtins sind in Ordnung
• Kürzester Code (in Bytes) gewinnt

Testfälle

#Bezeichnet in allen Testfällen eine Wand, bezeichnet einen leeren Raum und xbezeichnet den anfänglichen Ort der Füllung. @bezeichnet die Ausgabefüllung.

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:

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

Oktave, 73 Bytes

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

Online Demo!

* Einige Änderungen wurden angewendet, um in rextester ausgeführt zu werden.

Eine Funktion, die ein 2d-Array von 0 & 2 als Wand und ein Array von 0 & 1 als Anfangsposition verwendet und ein Array von 0 & 1 & 2 ausgibt.

JavaScript (ES6), 116 Byte

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>

Basierend auf meiner Antwort auf Fehlerhafte Schlösser erkennen . Füllt mit xs.

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

• 154 Bytes, nachdem nur die Kernfunktion und nicht die Funktion für die E / A-Formatierung gezählt wurde
• 7 Bytes gespart: dank @Jacoblaw und @ Mr.Xcoder: except:0
• 28 Bytes gespart !!!: Dank @ovs: try: exceptBlock und mehrere andere Golf losgeworden
• Vielen Dank an @ Dave für das schöne Testmodul.
• 6 Bytes gespart: g[(a,b)]als geradeg[a,b]
• @nore 15 Bytes gespeichert !!! :

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

Probieren Sie es online!

Mathematica, 117 Bytes

Die übliche Geschichte: Leistungsstarke Einbauten, aber lange Namen…

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

Probieren Sie es am Wolfram Sandkasten!

Es werden zwei Eingaben benötigt: Zuerst wird das Eingaberaster als Array von 0s (für die Wände) und 1s (für Leerzeichen), dann eine einzelne Ganzzahl für die Startposition, die durch Nummerieren des Rasters entlang der Zeilen von oben nach unten ermittelt wird, z

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

Sie können die Funktion wie folgt aufrufen HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

Die KnightTourGraphFunktion erstellt einen Graphen mit Scheitelpunkten, die Positionen im Gitter entsprechen, und Kanten, die gültigen Ritterbewegungen entsprechen. Dann nehmen wir Subgraphdie Scheitelpunkte, die keine Wände sind, und ermitteln die ConnectedComponentsScheitelpunkte des Startscheitelpunkts. Die Ausgabe ist ein Diagramm (um 90 ° gegen den Uhrzeigersinn gedreht), bei dem die nicht an der Wand befindlichen Scheitelpunkte rot und die ausgefüllten Scheitelpunkte gelb hervorgehoben sind. Für den ersten Testfall sieht die Ausgabe beispielsweise folgendermaßen aus: