Isi banjir kisi 2D

9

Deskripsi tantangan

Mari kita sebut array dua dimensi, persegi panjang (artinya setiap subarray memiliki panjang yang sama), sebuah kisi . Setiap unit kisi adalah ruang kosong atau perbatasan . Dalam kotak karakter, ruang kosong diwakili oleh spasi tunggal; karakter lain diperlakukan sebagai perbatasan. Kisi sampel ( +'s, |' dan -'ditambahkan agar mudah dibaca - mereka bukan bagian dari kisi ):

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

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

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

Diberi kisi 2D dan sepasang koordinat, isi area tertutup di sekitar titik yang diwakili oleh koordinat.

Input / output sampel

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

Catatan

  • Grid kosong dianggap tertutup, yaitu batas secara implisit terletak di sepanjang tepi grid juga (lihat contoh 1. dan 5.),

  • Sudut area tertutup tidak harus berbentuk L. Oleh karena itu dua area berikut ini setara:

####         ##
#  #        #  #
#  #   ==   #  #
#  #        #  #
####         ##
  • Jika unit di bawah koordinat kebetulan merupakan perbatasan Anda dapat membiarkan grid tidak berubah (seperti pada contoh 4.) atau memperlakukannya sebagai ruang kosong,

  • Anda dapat memilih karakter apa pun untuk pengisi / ruang kosong selama Anda memasukkan informasi ini dalam kiriman,

  • Jika menggunakan jenis selain yang charsesuai dengan tujuan Anda dengan lebih baik, Anda dapat menggunakan ints( 0untuk ruang kosong, 1untuk perbatasan) atau booleans( truedan falsemasing - masing) atau jenis lainnya - pastikan untuk memasukkan informasi ini dalam kiriman Anda,

  • Koordinat yang digunakan dalam contoh di atas adalah (row, column)koordinat berindeks 0 , karena lebih nyaman untuk array dua dimensi. Jika Anda ingin menggunakan (column, row)sistem (kartesius) dan / atau koordinat non-0-diindeks, tentukan dalam kiriman Anda.

  • Jika Anda tidak tahu harus mulai dari mana, lihat artikel Wikipedia tentang banjir

  • Ingat bahwa ini adalah tantangan , jadi buat kode Anda sesingkat mungkin!

shooqie
sumber
Terkait: 1 , 2 , 3 , 4 , mungkin lebih.
Peter Taylor
Mungkin layak memiliki test case dengan unit perbatasan tunggal di posisi koordinat, untuk menunjukkan bahwa ada dua output yang valid: Entah grid semua terisi atau grid tidak berubah. (Jika saya telah memahami nada ke-3 Anda dengan benar.)
trichoplax
Lihat mantan 4) pembaruan
shooqie
1
Saya tidak mengerti bagaimana Anda mendapatkan contoh alternatif Anda 4. Itu tampaknya menghancurkan sel-sel perbatasan selain dari input persegi yang ditentukan.
Joffan

Jawaban:

4

MATLAB, 30 7 byte

Karena kita dapat menggunakan input logis alih-alih string, kita dapat menggunakan fungsi bare, seperti:

@imfill

Ini adalah fungsi anonim. Untuk penggunaannya, kita harus mengasumsikan nama, mis f=@imfill. Kemudian kita bisa mengevaluasinya sebagai f(input,point), di mana inputada matriks logis, misalnya [0,0;0,1], dan pointmerupakan vektor 2d dengan koordinat berbasis 1, misalnya [1,2].

Versi lama mengerjakan string:

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

Fungsi anonim ini menerima input serta vektor dengan koordinat (indeks berbasis 1). Fungsi imfilltidak persis apa yang kita butuhkan, tetapi hanya beroperasi pada gambar biner. Itulah sebabnya kami mengonversi matriks input ke array logis (di mana #batas-batasnya, dan (spasi) kosong), melakukan pengisian dan kemudian dikonversi kembali. (lagi #diisi, ruang tidak diisi).

Terima kasih @LuisMendo untuk - 1 byte.

cacat
sumber
Untuk versi string, Anda dapat menggantinya ~=32dengan>32
Luis Mendo
3

C, 162 byte

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

Mengambil input dari argumen ( ./floodfill X Y grid). Kisi harus berisi \natau di \r\nantara setiap baris, baris baru final adalah opsional. Cara paling sederhana yang saya temukan untuk memanggil dari shell:

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

Output ke stdout, gunakan !untuk karakter isian. Jika posisi awal bertepatan dengan a #, tidak membuat perubahan.

Kerusakan:

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

Perhatikan bahwa ini bergantung pada modifikasi string argumen input, yang dilarang, jadi ini mungkin tidak berfungsi pada semua platform (deklarasi implisit juga menjadikan ini non-standar).

Dave
sumber
Anda dapat menyimpan 4 byte dengan mengubah int w, l;hanya w, l;- gcc default untuk intmengetik
Jacajack
@Jacajack poin bagus! Terima kasih
Dave
1

C - 263 247 240 238 byte

Ini adalah versi ketiga kedua pertama , saya percaya kode dapat menyusut juga.

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

Dan versi yang dapat dibaca:

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

}

Kompilasi dan jalankan:
gcc -o flood floodgolf.c && cat 1.txt | ./flood

Sumber:

Catatan: Saya sedang mengerjakan intnilai. Setiap (32) diperlakukan sebagai ruang kosong. Nilai lain dianggap sebagai batas. Koordinat dalam format(row, column)

Jacajack
sumber
1
Jangan lupa Anda dapat menyimpan titik koma dengan meletakkan pernyataan di dalam for(di scanfsini), dan menggunakan parameter utama pertama sebagai deklarasi int murah akan bekerja di sebagian besar kompiler. Anda juga mungkin bisa menghemat sedikit dengan meratakan susunan Anda (pasti akan membantu lingkaran cetak)
Dave
@Dave Benar. Saya telah belajar sedikit sejak saya menulis kode ini. Saya pikir menyimpan data dalam array 1D akan membantu saya untuk menyimpan banyak juga, tapi jelas saya tidak ingin menyalin ide Anda. Saya akan melihat apa yang bisa saya lakukan nanti. Terima kasih!
Jacajack
0

Python 2, 158 byte

Cobalah online . Solusi rekursif sederhana

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-diindeks dalam urutan kolom-baris

1 - ruang kosong, ruang 0-diisi

Mengambil input sebagai array array 1 dan 0, dan dua angka

Possum Mati
sumber
0

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

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

Cobalah online!

Bagaimana?

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
sumber