| Fişierul intrare/ieşire: | cycle.in, cycle.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Boaca Cosmin •darkseeker | |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cycle
Aceasta problema este usoara.
Pentru că se plictisea în casă Tezeu s-a hotărât să se plimbe puţin prin labirint să vađă ce mai face minotaurul. Labirintul este reprezentat ca o matrice bidimensională cu 0 şi 1. Celulele cu valoare 1 reprezintă camere libere iar cele cu valoare 0 reprezintă camere ocupate, în care nici Tezeu nici minotaurul nu pot ajunge.
Tezeu intră în labirint prin colţul stânga sus al acestuia celula (0, 0). El ştie că poate învinge minotaurul într-o luptă doar dacă acesta nu îl ia prin surprindere, şi de aceea Tezeu ar vrea să stie daca există un drum din celula (0, 0) care se termină tot în celula (0, 0), nu trece de 2 ori prin aceeaşi cameră, şi trece prin minim 3 camere distincte, el folosind acest drum pentru a fugi din labirint în cazul în care minotaurul va apărea subit în spatele lui.
Date de intrare
Fisierul de intrare cycle.in va conţine pe prima un număr T reprezentând numărul de teste din fişier.
Fiecare test are forma:
Pe prima linie numerele M şi N reprezentând numărul de linii, respectiv coloane al matricii. Pe următoarele M linii vor fi câte N numere din mulţimea {0, 1} cu semnificaţia de mai sus.
Date de ieşire
Fişierul de ieşire cycle.out va conţine T linii cu 0 sau 1, 1 însemnând că există un drum cu proprietatea din enunţ şi 0 că nu există.
Restricţii
* Celula din care se pleaca poate fi si 0!!!!!
* 2 ≤ N, M ≤ 200
* Drumul poate trece doar prin camere libere
* T ≤ 10
Exemplu
| cycle.in | cycle.out |
|---|---|
| 1 4 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 | 1 |
Explicaţie
Tezeu poate pleca din celula (0, 0) pe marginea labirintului şi se poate întoarce înapoi în celula (0, 0) fără a trece de 2 ori prin nicio cameră.
