Menghitung Permata

Latar Belakang

Kotak perhiasan saya baru saja jatuh! Ada terlalu banyak permata dengan bentuk berbeda di tanah. Dan tugas Anda adalah menghitung jumlah jenis permata tertentu.

I / O

• Kode Anda harus mengambil dua input Sdan G, yang bisa berupa string dengan baris baru, array garis, array karakter dua dimensi, file teks atau dalam format apa pun yang wajar (jika demikian, sebutkan dengan jelas).
• Dua string ini hanya akan berisi !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~(dari 0x21ke 0x7Edalam tabel ASCII), spasi dan baris baru (bentuk biner tergantung pada platform Anda).
• Di setiap string, garis memiliki panjang yang sama.
• Sadalah permata yang ingin kita hitung. Ada dua keadaan.
  1. Terlampir dan tidak mengandung area terlampir yang bersarang. (dalam contoh 1/2)
  2. Tidak mengandung area tertutup. (misalnya 3/4)
• Ruang di sekitarnya tidak dianggap sebagai bagian dari permata.
• G adalah bentuk permata di tanah.
• Dapat diterima bahwa kode Anda memerlukan input tambahan untuk menentukan dimensi SdanG
• Dapat diterima bahwa kode Anda mengambil nilai ASCII sebagai input, bukan karakter itu sendiri. Tetapi Anda tidak harus mengganti karakter dengan bilangan bulat yang lebih sederhana (0,1,2,3). Program Anda harus dapat memproses karakter, atau nilai ASCII.

Contoh 1 (Karakter sebagai input)

Masukan S:

+-+  
| +-+
| | |
| | |
| +-+
+-+  

Masukan G:

    +-+       +-+
    | +-+   +-+ |
    | | |   | | |
    | | |   | | |
    | +-+   +-+ |
    +-+       +-+
         +-+     
+---+    | +-+   
|   |    | | |   
|   |    | | |   
|   |    | +-++  
|   |    +-+| +-+
+---+       | | |
            | | |
  +-+       | +-+
  | +-+     +-+  
  | |-|          
  | |-|          
  | +-+          
  +-+            

Ouptut:

2

Contoh 2 (nilai ASCII sebagai input)

Masukan S:

32 32 32 32 32 32 32 32
32 32 32 32 99 32 99 32
32 32 32 99 32 99 32 99
32 32 32 99 32 32 32 99
32 32 32 99 32 32 32 99
32 32 32 99 32 32 32 99
32 32 32 32 99 32 99 32
32 32 32 32 32 99 32 32
32 32 32 32 32 32 32 32

Masukan G:

32 99 32 99 32 99 32 99 32 32 99 32
99 32 99 32 99 32 99 32 99 99 32 99
99 32 32 32 99 32 32 32 99 32 32 99
99 99 32 32 99 32 32 32 99 32 32 99
99 32 32 32 99 32 32 32 99 32 32 99
32 99 32 99 32 99 32 99 99 32 99 32
32 32 99 32 32 32 99 32 32 99 32 32

Keluaran:

1

Divisualisasikan S(32 diganti dengan -):

-- -- -- -- -- -- -- --
-- -- -- -- 99 -- 99 --
-- -- -- 99 -- 99 -- 99
-- -- -- 99 -- -- -- 99
-- -- -- 99 -- -- -- 99
-- -- -- 99 -- -- -- 99
-- -- -- -- 99 -- 99 --
-- -- -- -- -- 99 -- --
-- -- -- -- -- -- -- --

Divisualisasikan G:

-- 99 -- 99 -- 99 -- 99 -- -- 99 --
99 -- 99 -- 99 -- 99 -- 99 99 -- 99
99 -- -- -- 99 -- -- -- 99 -- -- 99
99 99 -- -- 99 -- -- -- 99 -- -- 99
99 -- -- -- 99 -- -- -- 99 -- -- 99
-- 99 -- 99 -- 99 -- 99 99 -- 99 --
-- -- 99 -- -- -- 99 -- -- 99 -- --

Contoh 3 (Tidak terlampir)

Terima kasih kepada @ Draco18s

Memasukkan S

AB

Memasukkan G

AAB BA CAB

Keluaran

2

Contoh 4 (Tidak termasuk 2D)

Memasukkan S

ABCD
  GE
   F

Memasukkan G

ABCD 
BGGED
CDEFE
    F

Keluaran

1

Catatan

• Hanya dua permata dari satu bentuk yang dianggap sama.
• Bentuk yang sama dalam arah yang berbeda tidak dianggap sama.
• Namun, seperti dijelaskan dalam contoh I / O, tumpang tindih dimungkinkan. Dalam keadaan seperti itu, hanya yang lengkap yang dihitung.
• +, -dan |dalam contoh tidak memiliki arti khusus. Mereka tidak menunjukkan sudut atau tepi bentuk.
• Anda mungkin menganggap input selalu valid.
• Anda dapat mengasumsikan dua permata target tidak pernah berbagi tepi yang sama persis.
• Celah standar dilarang.
• Ini adalah kode-golf, jadi kode terpendek menang!

C (gcc) , 303305 326 byte

Semua optimisasi perlu dimatikan dan hanya bekerja pada GCC 32-bit.

#define r(z,k)for(z=0;z<k;z++)
#define c s[i][j]
x,y,o,p,t,i,j;char**s;h(i,j){!((i<0)+(j<0)+i/x+j/y+c-32)?h(i+1,j),h(i-1,j),h(i,j+1),h(i,j-1),c=0:0;}f(w,e,u,v,a,g)char**a,**g;x=w,y=e,s=a;r(o,x)h(o,0),h(o,y-1);r(p,y)h(0,p),h(x-1,p);w=0;r(o,u-x+1)r(p,v-y+1){t=1;r(i,x)r(j,y)t*=!(c*(c-g[i+o][j+p]));w+=t;}}

Kode ini menggunakan timbunan banjir untuk menggantikan ruang di sekitarnya dengan \0dan mencari kecocokan sambil mengabaikan \0.

ungolfed dan macro dihitung (beberapa huruf berbeda dari versi golf, tetapi logika tetap sama):

int x, y, o, p, c, d, t;
char **s, **g;
h(int i, int j) {                             // Floodfill function
    if(i<0 || j<0) return;                    // Boundary detection
    if(i>=x || j>=y) return;
    if(s[i][j] != ' ') return;                // Character detection

    s[i][j] = 0;                              // Replace it with \0
    h(i+1, j);
    h(i-1, j)
    h(i  , j+1);
    h(i  , j-1);
}
f(
    int w,    //1st dimension of S
    int e,    //2nd dimension of S
    int u,    //1st dimension of G
    int v     //2nd dimension of G
    char** i, //Input S
    char** j, //Input G
    );
{
    x=w,y=e,s=i,g=j;
    for(o=0; o<x; o++)                        // Replace all surrounding spaces using floodfill
    {
        h(o, 0);                               
        h(o, y-1);
    }
    for(p=0; p<y; p++)
    {
        h(0,   p);
        h(x-1, p);
    }
    w = 0;
    for(o=0; o<=u-x; o++)                     // Main O(w*e*u*v) matching process
        for(p=0; p<=v-y; p++) {
            t=1;
            for(c=0; c<x; c++)
                for(d=0; d<y; d++)
                if(s[c][d]*(s[c][d]-g[c+o][d+p]))
                    t=0;
            w+=t;
        }
}