15
\$\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\$
4
  • \$\begingroup\$ Related: 1, 2, 3, 4, possibly more. \$\endgroup\$ Jun 25, 2016 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, 2016 at 22:39
  • \$\begingroup\$ See ex. 4) update \$\endgroup\$
    – shooqie
    Jun 25, 2016 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, 2016 at 0:39

7 Answers 7

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\$
1
  • \$\begingroup\$ For the string version, you can replace ~=32 by >32 \$\endgroup\$
    – Luis Mendo
    Jun 26, 2016 at 14:19
4
\$\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\$
2
  • \$\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, 2016 at 19:12
  • \$\begingroup\$ @Jacajack good point! Thanks \$\endgroup\$
    – Dave
    Jun 28, 2016 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\$
2
  • 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, 2016 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, 2016 at 17:41
1
\$\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\$
1
\$\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\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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