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

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.

Notă: Toate restricțiile impuse la taskul precedent se aplică și aici.

Detectivii care cercetează corporația Chert And au tras concluzia că o anumită insulă le poate oferi informații suplimentare pentru dezlușirea dezastrului!

Problema

Vă este dată o celulă de uscat care aparține de o insulă. Deoarece voi credeți că și în apă se pot găsi indicii, veți dori să determinați dretpunghiul de arie minimă ce include complet insula de care aparține celula. Un dreptunghi include complet o insulă dacă toate celulele care aparțin de insula respectivă se află în interiorul dreptunghiului (nu și pe conturul acestuia).

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, separate prin câte un spațiu, 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 două numere, $a$ și $b$, care reprezintă celula pentru care dorim să găsim dreptunghiul care înconjoară complet insula de care aparține celula.

Date de ieșire

Se vor afișa două puncte: colțul stânga-sus al dreptunghiului și colțul dreapta-jos al dreptunghiului. Coordonatele vor fi separate prin câte un spațiu.

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 = 5$
• $N = M = 250$
• Valorile din matrice sunt fie $0$, fie $1$.
• Se garantează că celula $(a, b)$ este celulă de uscat.
• Liniile și coloanele sunt indexate de la $1$.
• Celulele de pe conturul matricei (nu cel al insulei) vor fi toate cu valori de $0$.
• 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 exemplu se va analiza strict un test mai mic, care nu va fi utilizat pentru evaluare.

Exemplu

0.txt

7 7
0 0 0 0 0 0 0
0 1 1 1 0 0 0
0 0 1 1 1 0 0
0 1 1 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0
4 2

output

1 1 7 7

Explicație

Se poate observa că insula noastră poate să fie inclus complet în dreptunghiul care are colțurile $(1, 1)$ și $(7, 7)$. Un dreptunghi de arie mai mică decât cel dat în exemplu este imposibil de găsit.

Mult succes!