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:
##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############

• Martin Ender: Somewhat related.

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.

• Dave: Looks good, but doesn't this need pkg load ... when run outside the test framework? If imdilate & de2bi are available without explicit imports then that's fine.
• rahnema1: @Dave In previous versions of octave ,including the version installed in tio, it was possible to install a package so that it could load automatically but now I noticed that this feature is removed from octave! please see this.
• Dave: Fair enough. As long as you're targeting a version before -auto was removed it's no problem, and I'm guessing this answer doesn't use any new features.

Answer 2

JavaScript (ES6), 116 bytes

f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\1円)[x ]/`),'x2ドルx'))=>s==t?s:f(t)
v=(s,l=s.search`
`)=>!/^(#+)\n1円\n[^]*x[^]*\n1円\n1円$/.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.

• 0xffcourse: Can you add a test snippet/link?

Answer 3

Python 3, (削除) 394 387 381 356 352 347 319 313 154 (削除ここまで)139 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!

• jacoblaw: can you do except:pass instead?
• Mr. Xcoder: I am pretty sure that this can be heavily golfed
• Mr. Xcoder: @jacoblaw even better: except:0
• ovs: 319 bytes
• Dave: Here's a slightly easier-to-test version of the TiO: 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 90o 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:

Output for test case 1: a graph with some areas highlighted

• Dave: Well this certainly looks like the hardest to test! Could you add an example of how to invoke it in the sandbox, for those of us who haven't touched Mathematica since our university days? My attempts of f=... f[{0,...,0;0,...,0}, 19] and similar have failed miserably.
• Not a tree: @Dave, you can invoke the function with 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] (for the first test case). I've edited that into the question — sorry it wasn't there to begin with!