Rellenar una cuadrícula 2D

9

Descripción del desafío

Llamemos a una matriz rectangular de dos dimensiones (lo que significa que cada subcadena tiene la misma longitud), una cuadrícula . Cada unidad de una cuadrícula es un espacio vacío o un borde . En una cuadrícula de caracteres, el espacio vacío está representado por un solo espacio en blanco; cualquier otro personaje se trata como un borde. Cuadrículas de muestra ( +'s, |' sy -'s añadidas para facilitar la lectura; no son parte de la cuadrícula ):

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

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

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

Dada una cuadrícula 2D y un par de coordenadas, rellena el área cerrada que rodea el punto representado por las coordenadas.

Muestra de entradas / salidas

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|
|                |      |                |
|                |      |                |
+----------------+      +----------------+

Notas

  • Una cuadrícula vacía se considera cerrada, es decir, los bordes también están implícitamente ubicados a lo largo de los bordes de la cuadrícula (ver ejemplos 1. y 5.),

  • Una esquina de un área cerrada no necesita tener forma de L. Por lo tanto, las dos áreas siguientes son equivalentes:

####         ##
#  #        #  #
#  #   ==   #  #
#  #        #  #
####         ##
  • Si una unidad debajo de las coordenadas resulta ser un borde, puede dejar la cuadrícula sin cambios (como en el ejemplo 4) o tratarla como un espacio vacío,

  • Puede elegir cualquier carácter para relleno / espacio vacío siempre que incluya esta información en el envío,

  • Si usa un tipo diferente a charsus propósitos, puede usarlo ints( 0para el espacio vacío, 1para el borde) o booleans( truey falserespectivamente) o cualquier otro tipo, solo asegúrese de incluir esta información en su envío,

  • Las coordenadas utilizadas en los ejemplos anteriores son (row, column)coordenadas indexadas en 0 , ya que es más conveniente para una matriz bidimensional. Si desea utilizar (column, row)el sistema (cartesiano) y / o coordenadas sin índice 0, especifíquelo en su envío.

  • Si no sabe por dónde empezar, consulte el artículo de Wikipedia sobre inundación

  • Recuerde que este es un desafío de , ¡así que haga su código lo más corto posible!

shooqie
fuente
Relacionado: 1 , 2 , 3 , 4 , posiblemente más.
Peter Taylor
Podría valer la pena tener un caso de prueba con una sola unidad de borde en la posición de las coordenadas, para mostrar que hay dos salidas válidas: o bien la cuadrícula está llena o la cuadrícula no ha cambiado. (Si he entendido correctamente su tercera nota.)
trichoplax
Ver ej. 4) actualización
shooqie
1
No entiendo cómo obtienes tu ejemplo alternativo 4. Parece estar destruyendo celdas de borde que no sean el cuadrado de entrada especificado.
Joffan

Respuestas:

4

MATLAB, 30 7 bytes

Como podemos usar entradas lógicas en lugar de cadenas, podemos usar la función simple, como es:

@imfill

Esta es una función anónima. Para el uso, tenemos que asumir un nombre, por ejemplo f=@imfill. Entonces podemos evaluarlo como f(input,point), donde inputes una matriz lógica, por ejemplo [0,0;0,1], y pointes un vector 2d con coordenadas basadas en 1, por ejemplo [1,2].

Versión antigua trabajando en cadenas:

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

Esta función anónima acepta la entrada, así como un vector con las coordenadas (índice basado en 1). La función imfillhace exactamente lo que necesitamos, pero opera solo en imágenes binarias. Es por eso que convertimos la matriz de entrada en una matriz lógica (donde #están los límites, y (los espacios) son el vacío), realiza el relleno y luego se convierte de nuevo. (De nuevo #se llena, el espacio no se llena).

Gracias @LuisMendo por - 1 byte.

falla
fuente
Para la versión de cadena, puede reemplazar ~=32por>32
Luis Mendo
3

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);}

Toma datos de argumentos ( ./floodfill X Y grid). La cuadrícula debe contener \no \r\nentre cada línea, la nueva línea final es opcional. La forma más simple que he encontrado para invocar desde shell:

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

Salidas a stdout, utilizando !para el carácter de relleno. Si la posición de inicio coincide con a #, no hace ningún cambio.

Descompostura:

                                    // 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

Tenga en cuenta que esto se basa en modificar la cadena de argumento de entrada, que está prohibida, por lo que esto puede no funcionar en todas las plataformas (las declaraciones implícitas también hacen que esto no sea estándar).

Dave
fuente
Puede guardar 4 bytes cambiando int w, l;a simplemente w, l;- gcc lo predetermina a intescribir
Jacajack
@Jacajack buen punto! Gracias
Dave
1

C - 263 247 240 238 bytes

Esta es la primera segunda tercera versión, creo que el código también se puede reducir.

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]);}

Y versión legible:

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] );     

}

Compilar y ejecutar:
gcc -o flood floodgolf.c && cat 1.txt | ./flood

Recursos:

Nota: estoy trabajando en intvalores. Cada (32) se trata como un espacio vacío. Cualquier otro valor se trata como borde. Las coordenadas están en formato.(row, column)

Jacajack
fuente
1
No olvide que puede guardar puntos y comas colocando declaraciones dentro del for( scanfaquí), y usar el primer parámetro de main como una declaración int barata funcionará en la mayoría de los compiladores. También es posible que pueda ahorrar un poco al aplanar su matriz (ciertamente debería ayudar al ciclo de impresión)
Dave
@Dave Eso es correcto. He aprendido un poco desde que escribí este código. Creo que almacenar datos en una matriz 1D también me ayudaría a ahorrar mucho, pero obviamente no quiero copiar su idea. Veré qué puedo hacer más tarde. ¡Gracias!
Jacajack
0

Python 2, 158 bytes

Pruébalo en línea . Solución recursiva simple

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 indexado en orden fila-columna

1 - espacio vacío, 0 - espacio lleno

Toma la entrada como una matriz de matrices de 1 y 0, y dos números

Zarigüeya muerta
fuente
0

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

Pruébalo en línea!

¿Cómo?

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
Xcali
fuente