9
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Related: 1, 2, 3, 4, possibly more. \$\endgroup\$ – Peter Taylor Jun 25 '16 at 21:49
  • \$\begingroup\$ 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.) \$\endgroup\$ – trichoplax Jun 25 '16 at 22:39
  • \$\begingroup\$ See ex. 4) update \$\endgroup\$ – shooqie Jun 25 '16 at 23:04
  • 1
    \$\begingroup\$ I don't get how you get your alternative example 4. That appears to be destroying border cells other than the specified input square. \$\endgroup\$ – Joffan Jun 26 '16 at 0:39
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For the string version, you can replace ~=32 by >32 \$\endgroup\$ – Luis Mendo Jun 26 '16 at 14:19
3
\$\begingroup\$

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).

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

C - 263 247 240 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]);}

And readable version:

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

/*
    a, b - flood fill start coordinates
    v, w - recursive function start coordinates
    x, y - iterators
    c - character read
    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( )
{
    //Read coordinates
    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)

\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Dave Jun 28 '16 at 17:38
  • \$\begingroup\$ @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! \$\endgroup\$ – Jacajack Jun 28 '16 at 17:41
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.