Knight-fill a grid

Question

A knight fill is a flood fill using the connectivity of the knight chess piece. Specifically:

 1 1
1   1
  0
1   1
 1 1

(0 is the initial point, 1s show the connected cells)

Challenge

Given a 2D grid of spaces and walls, and an initial location, perform a knight-fill on the grid. Shortest code wins.

Rules

• You may take input and produce output in any format you like (image, string, array, whatever). You may take the initial location as part of the input grid or as a separate coordinate. For the purpose of this explanation, the following format will be used:

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

• Output is a copy of the input grid with the knight-fill result added

• Your fill must not be in the same "colour" as the space or walls, but can be the same as the initial location marker. For example given the image above, a valid output would be:

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

• You may assume that the input grid will always contain a 2-cell wall on all sides

• You may assume that the initial location will never be inside a wall
• You may assume that the grid will never be larger than 1000x1000
• Builtins are fine
• Shortest code (in bytes) wins

Test Cases

In all test cases, # denotes a wall, denotes empty space, and x denotes the initial location of the fill. @ denotes the output fill.

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:

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

Answer 1

Octave, 73 bytes

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

Online Demo!

*Some changes applied to run in rextester.

A function that takes a 2d array of 0 & 2 as wall and an array of 0 & 1 as initial location and outputs an array of 0 & 1 & 2.

Answer 2

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>

Based on my answer to Detect Failing Castles. Fills using xs.

Answer 3

Python 3, 394 387 381 356 352 347 319 313 154139 bytes

• 154 bytes after only counting the core function and not the function concerning I/O formatting
• saved 7 bytes: thanks to @Jacoblaw and @Mr.Xcoder: except:0
• saved 28 bytes!!!: Thanks to @ovs: got rid of try: except block and several other golf
• Thanks to @Dave for the beautiful test module.
• saved 6 bytes: g[(a,b)] as just g[a,b]
• @nore saved 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

Try it online!

Answer 4

Mathematica, 117 bytes

The usual story: powerful built-ins but long names…

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

Try it at the Wolfram sandbox!

It takes two inputs: first is the input grid as an array of 0s (for the walls) and 1s (for spaces), then a single integer for the starting position, found by numbering the grid along the rows from top to bottom, e.g.

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

You can call the function like HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

The KnightTourGraph function constructs a graph with vertices corresponding to positions in the grid and edges corresponding to valid knight moves, then we take the Subgraph of the vertices that aren't walls, and find the ConnectedComponents of the starting vertex. The output is a graph (shown rotated 90º anticlockwise) with the non-wall vertices highlighted red, and the filled vertices highlighted yellow. For example, for the first test case, the output looks like: