Green Byte Hackathon 2024 | Insule și Oceane - Task 1

ATENȚIE: Aceasta problemă valorează $100$ de puncte. La "submissions" scorul maxim este rescalat la $100$ de puncte, dar adevaratul scor va fi vizibil pe leaderboard.

Corporația Chert And derulează niște activități suspicioase pe niște insule din Oceanul Pacific. De la experimente care nu știm în ce măsura afectează mediul până la tranzacții bancare ilegitime. Demascați această activitate rezolvând următorul task, iar megacorporația va fi obligată să mai dezvăluie din datele de la ferma din România.

Problema

Arhipelagul nostru va putea fi reprezentat ca o matrice de dimensiune $N \times M$, unde celulele de $1 \times 1$ din matrice pot avea două valori:

• $0$ - o celulă de apă
• $1$ - o celulă de pământ

Spunem că două celule sunt considerate vecine daca au cel puțin o latură în comun. Mai multe celule de pământ vecine alcătuiesc o insulă.

Pentru a obține câteva indicii despre activitățile ilegale ale corporației Chert And, voi trebuie să răspundeți la mai multe intrebări: Sunt celulele $(a, b)$ și $(c, d)$ în aceeași insulă?

Output only

Această problemă este de tip output only. Voi (participanții) va trebui să vă rulați local $Q$ teste (care se pot descărca aici sau în dreapta paginii sub „Atașamente”), apoi veți transmite comisiei prin intermediul platformei răspunsurile.

Date de intrare

Pe prima linie dintr-un test se vor afla două numere $N$ și $M$, care reprezintă lungimea, respectiv lățimea matricei.

Pe următoarele $N$ rânduri se vor afla câte $M$ valori, care reprezintă codificarea arhipelagului. O celulă cu valoarea $0$ reprezintă o celulă de apă, iar o celulă cu valoarea $1$ reprezintă o celulă de uscat.

Pe linia $N + 2$ din input se vor afla $4$ numere, $a, b, c$ și $d$, care reprezintă celulele $(a, b)$ și $(c, d)$ despre care vrem să știm dacă sunt sau nu în aceeași insulă.

Date de ieșire

Dacă celulele $(a, b)$ și $(c, d)$ se află în aceeași celulă, veți transmite DA, altfel veți transmite NU.

Răspunsurile la cele $Q$ teste le puteți transmite fie printr-un fișier, fie le încărcați mai jos în zona de atașare al codului. Răspunsurile de la fiecare test se vor afla pe câte un rând separat, pe al $i$-lea rând din output aflându-se răspunsul la a $i$-a întrebare.

Restricții și precizări

• $Q = 10$
• $N = M = 250$
• Valorile din matrice sunt fie $0$, fie $1$.
• Se garantează că celulele $(a, b)$ și $(c, d)$ sunt celule de uscat.
• Liniile și coloanele sunt indexate de la $1$.
• Pentru rezolvarea corectă a taskului veți primi un batch de coordonate pentru META-TASK.
• Linkul de la batch se va găsi în verdictul testului de evaluare.

Notă: Pentru simplitate, în exemple se vor analiza strict două teste mai mici, care nu vor fi utilizate pentru evaluare.

Exemple

0.txt

7 7
1 0 0 0 0 1 0
0 0 0 0 1 1 0
1 1 1 1 1 0 0
0 0 0 1 0 0 0
1 0 0 0 0 0 0
1 1 0 0 1 1 1
1 0 0 0 1 0 0
3 1 2 6

output

DA

input

7 7
1 0 0 0 0 1 0
0 0 0 0 1 1 0
1 1 1 1 1 0 0
0 0 0 1 0 0 0
1 0 0 0 0 0 0
1 1 0 0 1 1 1
1 0 0 0 1 0 0
3 3 7 5

output

NU

Explicație

Se poate observa din desen că celulele $(3, 1)$ (cerculeț roșu) și $(2, 6)$ (cerculeț verde) se află în aceeași insulă. În schimb, celulele $(3, 3)$ (cerculeț albastru) și $(7, 5)$ (cerculeț negru) se află în insule diferite.

Mult succes!