# Challenge description

Let's call a two-dimentional, rectangular array (meaning its every subarray has the same length), a grid. Every unit of a grid is either an empty space or a border. In a grid of characters, empty space is represented by a single whitespace; any other character is treated as a border. Sample grids (+'s, |'s and -'s added for readability - they are not part of the grid):

+----+
|    |
|    |
|    |
|    |
|    |
+----+  an empty 4x5 grid

+------+
|      |
|  #   |
|  #   |
+------+  a 6x3 grid with 2 borders

+----------+
|          |
|          |
|  #####   |
|  #   #   |
| ##   # <------ enclosed area
| #    #   |
| ######   |
|          |
+----------+  a 10x8 grid with an enclosed area


Given a 2D grid and a pair of coordinates, fill the enclosed area surrounding the point represented by the coordinates.

# Sample inputs / outputs

1)

0 0
+----------+      +----------+
|          |      |XXXXXXXXXX|
|          |  ->  |XXXXXXXXXX|
|          |      |XXXXXXXXXX|
+----------+      +----------+


2)

6 5
+-----------------+      +-----------------+
|                 |      |                 |
|                 |      |                 |
|    ########     |      |    ########     |
|    #       #    |      |    #XXXXXXX#    |
|    #    ####    |      |    #XXXX####    |
|    #    #       |      |    #XXXX#       |
|    #    #       |  ->  |    #XXXX#       |
|    #    #       |      |    #XXXX#       |
|     ####        |      |     ####        |
|                 |      |                 |
|                 |      |                 |
+-----------------+      +-----------------+


3)

4 6
+-----------------+      +-----------------+
|                 |      |XXXXXXXXXXXXXXXXX|
|    ####         |      |XXXX####XXXXXXXXX|
|   #    #        |  ->  |XXX#    #XXXXXXXX|
|    ####         |      |XXXX####XXXXXXXXX|
|                 |      |XXXXXXXXXXXXXXXXX|
+-----------------+      +-----------------+


4)

4 5
+-----------------+      +-----------------+      +-----------------+
|                 |      |                 |      |                 |
|                 |      |                 |      |                 |
|    ####         |      |    ####         |      |     XXXX        |
|    ####         |  ->  |    ####         |  or  |     XXXX        |
|    ####         |      |    ####         |      |     XXXX        |
|                 |      |                 |      |                 |
+-----------------+      +-----------------+      +-----------------+


5)

2 6
+----------------+      +----------------+
|                |      |XXXXXXXXXXXXXXXX|
|                |      |XXXXXXXXXXXXXXXX|
|                |      |XXXXXXXXXXXXXXXX|
|                |  ->  |XXXXXXXXXXXXXXXX|
|                |      |XXXXXXXXXXXXXXXX|
|BBBBBBBBBBBBBBBB|      |BBBBBBBBBBBBBBBB|
|                |      |                |
|                |      |                |
+----------------+      +----------------+


# Notes

• An empty grid is considered enclosed, i.e. borders are implicitly situated along the edges of the grid as well (see examples 1. and 5.),

• A corner of an enclosed area doesn't need to be L-shaped. The following two areas are therefore equivalent:

####         ##
#  #        #  #
#  #   ==   #  #
#  #        #  #
####         ##

• If a unit under the coordinates happens to be a border you can either leave the grid unchanged (as in example 4.) or treat it as an empty space,

• You can choose any character for filler / empty space as long as you include this information in the submission,

• If using a type other than char suits your purposes better, you can use ints (0 for empty space, 1 for border) or booleans (true and false respectively) or any other type - just make sure to include this information in your submission,

• Coordinates used in the examples above are 0-indexed (row, column) coordinates, as it's more convenient for two-dimensional array. If you want to use (column, row) (cartesian) system and/or non-0-indexed coordinates, specify it in your submission.

• If you don't know where to start, check out Wikipedia article on flood fill

• Remember that this is a challenge, so make your code as short as possible!

• Related: 1, 2, 3, 4, possibly more. Jun 25, 2016 at 21:49
• Might be worth having a test case with a single border unit at the position of the coordinates, to show that there are two valid outputs: Either the grid is all filled or the grid is unchanged. (If I have understood your 3rd note correctly.) Jun 25, 2016 at 22:39
• See ex. 4) update Jun 25, 2016 at 23:04
• I don't get how you get your alternative example 4. That appears to be destroying border cells other than the specified input square. Jun 26, 2016 at 0:39

# MATLAB, 30 7 bytes

As we can use logical inputs instead of strings, we can use the bare function, as it is:

@imfill


This is an anonymous function. For the usage, we have to assume a name, e.g. f=@imfill. Then we can just evaluate it as f(input,point), where input is a logical matrix, e.g. [0,0;0,1], and point is a 2d-vector with 1-based coordinates, e.g. [1,2].

Old version working on strings:

@(a,p)[imfill(a>32,p)*3+32,'']


This anonymous function accepts the input as well as a vector with the coordinates (1-based index). The function imfill does exactly what we need, but operates only on binary images. That is why we convert the input matrix to a logical array (where # are the boundaries, and   (spaces) are the void), performs the filling and is then converted back. (again # is filled, space is not filled).

Thanks @LuisMendo for -1 byte.

• For the string version, you can replace ~=32 by >32 Jun 26, 2016 at 14:19

# C, 162 bytes

w,l;char*d;f(z){z<0||z>l||d[z]^32||++d[z]&&f(z+1)+f(z-1)+f(z+w)+f(z-w);}main(c,v)char**v;{l=strlen(d=v[3]),w=strchr(d,10)-d+1,f(atoi(v[2])*w+atoi(v[1]));puts(d);}


Takes input from arguments (./floodfill X Y grid). Grid must contain \n or \r\n between each line, final newline is optional. Simplest way I've found to invoke from shell:

./floodfill 1 0 "$(printf " \n###\n \n")" # or ./floodfill 1 0 "$(cat gridfile)"


Outputs to stdout, using ! for the fill character. If the start position coincides with a #, makes no change.

### Breakdown:

                                    // GCC is happy enough without any imports
w,l;                                // Globals (line width, total length)
char*d;                             // Global grid pointer
f(z){                               // "Fill" function - z=current cell
z<0||z>l||                      // Check if out-of-bounds...
d[z]^32||                       // ...or not empty
++d[z]&&                    // Fill cell...
f(z+1)+f(z-1)+f(z+w)+f(z-w);// ...and continue in "+" pattern
}
main(c,v)char**v;{                  // K&R style function to save 2 bytes
l=strlen(d=v[3]),               // Store grid & length
w=strchr(d,10)-d+1,             // Store width of grid (including newlines)
f(atoi(v[2])*w+atoi(v[1]));     // Parse X & Y arguments and invoke fill

puts(d);}                       // Print the result


Note that this relies on modifying the input argument string, which is forbidden, so this may not work on all platforms (implicit declarations also make this non-standard).

• You can save 4 bytes by changing int w, l; to simply w, l; - gcc defaults it to int type Jun 26, 2016 at 19:12
• @Jacajack good point! Thanks
– Dave
Jun 28, 2016 at 17:27

# C - 263247240 238 bytes

This is first second third version, I believe code can be shrinked too.

m[99][99],x,y,a,b,c,n;f(v,w){if(m[v][w]==32){m[v][w]=88;f(v,w+1);f(v+1,w);f(v,w-1);f(v-1,w);}}main(){scanf("%d %d\n",&a,&b);for(;~(c=getchar());m[x++][y]=c,n=x>n?x:n)c==10&&++y&&(x=0);f(b+2,a+1);for(a=-1;++a<y*n+n;)putchar(m[a%n][a/n]);}


m[99][99], x, y, a, b, c, n;

/*
a, b - flood fill start coordinates
v, w - recursive function start coordinates
x, y - iterators
m - map
n - maximum map width found

*/

//Recursive flood function
f( v, w )
{
if ( m[v][w] == 32 ) //If field is empty (is ' '?)
{
m[v][w] = 88; //Put 'X' there
f(v,w+1);f(v+1,w); //Call itself on neighbour fields
f(v,w-1);f(v-1,w);
}
}

main( )
{
scanf( "%d %d\n", &a, &b );

//Read map (put character in map, track maximum width)
for ( ; ~( c = getchar( ) ); m[x++][y] = c, n = x > n ? x : n )
c == 10 && ++y && ( x = 0 );

//Flood map
f( b + 2, a + 1 );

//Draw
for ( a = -1; ++a < y * n + n; )
putchar( m[a % n][a / n] );

}


Compile and run:
gcc -o flood floodgolf.c && cat 1.txt | ./flood

Resources:

Note: I'm working on int values. Every   (32) is treated as empty space. Any other value is treated as border. Coordinates are in format (row, column)

• Don't forget you can save semicolons by putting statements inside the for (scanf here), and using the first parameter of main as a cheap int declaration will work in most compilers. Also you might be able to save a bit by flattening your array (should certainly help the print loop)
– Dave
Jun 28, 2016 at 17:38
• @Dave That's right. I've learned a bit since I wrote this code. I think storing data in 1D array would help me to save a lot too, but obviously I don't want to copy your idea. I'll see what I can do later. Thanks! Jun 28, 2016 at 17:41

## Python 2, 158 bytes

Try it online. Simple recursive solution

a,X,Y=input()
M=len(a)
N=len(a[0])
def R(x,y):
if~0<x<M and~0<y<N and a[x][y]:a[x][y]=0;R(x-1,y);R(x+1,y);R(x,y-1);R(x,y+1)
R(X,Y)
print'\n'.join(map(str,a))


0-indexed in row-column order

1 - empty space, 0 - filled space

Takes input as array of arrays of 1 and 0, and two numbers

# Perl 5, 129 + 1 (-a) = 130 bytes

sub f{my($r,$c)=@_;$a[$r][$c]eq$"&&($a[$r][$c]=X)&&map{f($r+$_,$c);f($r,$c+$_)}-1,1}@a=map[/./g],<>;f$F[0]+1,$F[1]+1;say@$_ for@a


Try it online!

How?

sub f{   # recursive subroutine
my($r,$c)=@_; # taking row and column as inputs
$a[$r][$c]eq$"&&  # using Boolean short circuit as an 'if' statement to
# check if the current position in the global array is blank
($a[$r][$c]=X)&& # then setting it to 'X' map{f($r+$_,$c);f($r,$c+$_)}-1,1 # and checking the four surrounding spaces } # -a command line option implicitly splits the first line into the @F array @a=map[/./g],<>; # put the input in a 2-D array f$F[0]+1,$F[1]+1; # start the fill at the given position, correcting for # Perl's 0 based arrays say@$_ for@a        # output the resulting pattern


# 05AB1E, 53 bytes

[©g_#®ć©d®IgIнg‚‹«PisD®нèD®θèi2®θǝ®нǝs1ÝÂ‚D(«ε®+}ìë\s


Input-coordinate as a wrapped pair of integers $$\[[x,y]]\$$, and input-grid as a matrix of 1s and 0s for empty spaces and borders respectively. Flood-fills with 2s.

Try it online or verify all test cases. (The ]J» in the footer of the single TIO is used to pretty-print the output-matrix. Feel free to remove it to see the actual output.)

Explanation:

Despite being a codegolf language, 05AB1E's matrix builtins aren't too useful here. And 05AB1E's modular indexing is only a disadvantage for a challenge like this, where you want to stay within the dimension of the grid.

[                  # Start an infinite loop:
©                 #  Store the list of coordinates in variable ® (without
#  popping)
#  (which is the first implicit input in the first iteration)
g_               #  If it's empty:
#              #   Stop the infinite loop
©ć               #  Extract head of ®; pop and remainder-list and first
#  coordinate separated to the stack
©              #  Store this coordinate as new variable ® (without popping)
d             #  Check [x>=0,y>=0]
Ig          #  Push the amount of rows of the input-matrix
Iнg       #  Push the amount of columns of the input-matrix
‚      #  Pair them together
®      ‹     #  Check [x<rowCount,y<columnCount]
«    #  Merge the two lists together
Pi  #  Pop, and if all were truthy (so [x,y] is within bounds):
s                 #   Swap so the matrix is at the top
D                #   Duplicate this matrix
®нè             #   Pop and get the x'th (of coordinate ®) row of the matrix
D            #   Duplicate this row
®θè         #   Pop and get the y'th (of coordinate ®) cell of this row
i        #   If this value is 1:
2®θǝ    #    Insert a 2 at this y'th cell of the row
®нǝ #    Insert this modified x'th row into the matrix
s                 #    Swap so the list of coordinates is at the top again
1Ý               #    Push [0,1]
Â‚             #    Bifurcate (Duplicate & Reverse copy) and pair:
#    [[0,1],[1,0]]
D(«          #    Duplicate, negate, merge: [[0,1],[1,0],[0,-1],[-1,0]]
ε®+}      #    Add coordinate ® to each pair:
#    [[x,y+1],[x+1,y],[x,y-1],[x-1,y]]
ì     #    Prepend-merge it at the front of the coordinates-list
ë        #   Else: the value was 0 or 2 instead:
\       #    Discard the duplicated row
s      #    And swap so the coordinates list is at the top again
]                  # Close the open if-statements and infinite loop
\                 # Discard the empty coordinates list
# (after which the matrix is output implicitly as result)


# Java, 112 bytes

int f(int[][]m,int x,int y){try{if(m[x][y]==0)f(m,x+f(m,x,y+f(m,x-f(m,x,y+--m[x][y]),y)),y);}finally{return 1;}}


Input as a matrix of 0s and 1s for empty spaces and borders respectively. Modifies the input-matrix directly, and flood-fills with -1s.

Uses the same flood-fill recursive method I've used in this answer, this answer, and this answer of mine.

Try it online.

Explanation:

// Recursive method with integer matrix & x,y parameters and integer return-type
int f(int[][]m,int x,int y){
try{if(m[x][y]==0)   //  If the current cell-value is 0:
--m[x][y]  //   Decrement the current cell-value to -1
f(m,x,y+...)//   Recursive call west
f(m,x-...,y) //   Recursive call north
f(m,x,y+...)  //   Recursive call east
f(m,x+...,y);  //   Recursive call south
}finally{            //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
//  (shorter than manual if-checks)
return 1;}  //  Always result in 1, so we use it to our advantage to
//  save bytes here by nesting, instead of having four
//  loose calls to each direction)