Insule și Oceane - Task 3

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

Garda de mediu a stabilit faptul că celulele de apă între care te poți deplasa între ele în două moduri diferite au niște proprietăți speciale, care îi pot ajuta la descifrarea misterului!

Problema

Vi se dau două celule de apă. Voi trebuie să determinați dacă este posibil să ne deplasăm în două moduri diferite între cele două celule.

O deplasare între două celule reprezintă o succesiune de celule în așa fel încât oricare două celule consecutive au cel puțin o latură sau un colț comun. Într-o deplasare nu putem trece de mai multe ori prin aceeași celulă. Două deplasări între două celule se consideră diferite dacă intersecția mulțimii celulelor (cu excepția primei și ultimei celule) ale ambelor deplasări au intersecția vidă.

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 $4$ numere, $a, b, c$ și $d$, care reprezintă celulele pentru care dorim să aflăm dacă există sau nu două deplasări între celulele $(a, b)$ și $(c, d)$.

Date de ieșire

Dacă există două deplasări distincte între celulele $(a,b)$ și $(c,d)$ 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 apă.
• Liniile și coloanele sunt indexate de la $1$.
• O deplasare nu este valabilă dacă iese din matrice.
• 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 1 1 1 0 1
0 1 0 1 1 1 1
0 0 0 1 0 1 1
0 1 1 1 1 1 0
0 0 0 0 0 0 0
1 1 1 1 0 1 1
0 0 0 0 0 0 0
3 1 1 2

output

DA

input

7 7
1 0 1 1 1 0 1
0 1 0 1 1 1 1
0 0 0 1 0 1 1
0 1 1 1 1 1 0
0 0 0 0 0 0 0
1 1 1 1 0 1 1
0 0 0 0 0 0 0
3 1 4 7

output

NU

Explicație

Între celulele $(3, 1)$ și $(1, 2)$ se pot realiza două drumuri distincte (drumul portocaliu și drumul galben).

Între celulele $(3, 1)$ și $(4, 7)$ nu se pot realiza două drumuri distincte.

Mult succes!