Fişierul intrare/ieşire: | convex.in, convex.out | Sursă | Cerc informatică Vianu |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 4096 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Convex (clasa a 8-a)
Să considerăm o matrice m x n. Iniţial toate pătrăţelele matricei sînt colorate în alb. Homer a colorat o parte din pătrăţele (cel puţin una) în negru. Denumim o matrice colorată convexă dacă putem să mergem de la orice căsuţă neagră la orice altă căsuţă neagră traversînd numai căsuţe negre adiacente şi schimbînd direcţia cel mult o dată. În figura de mai jos matricea din stînga este convexă, în timp ce cea din dreapta nu este convexă, pentru că există două căsuţe pentru care trebuie să schimbăm direcţia mai mult de o dată în calea de la una la cealaltă.
Cerinţă
Vi se dă o matrice pictată. Spuneţi-i lui Homer dacă este convexă sau nu.
Date de intrare
Fişierul de intrare convex.in conţine pe prima linie doi întregi, m şi n, dimensiunile matricei. Fiecare din următoarele m linii conţine n caractere 'A' sau 'N'. Caracterul 'A' reprezintă o căsuţă albă, iar 'N' una neagră.
Date de ieşire
Fişierul de ieşire convex.out conţine pe singura lui linie numărul 1 dacă matricea este convexă, sau 0 în caz contrar.
Restricţii
- 1 ≤ m, n ≤ 700
- există cel puţin o căsuţă pictată
- pentru 40% din teste 1 ≤ m, n ≤ 50
- pentru 80% din teste 1 ≤ m, n ≤ 150
Exemple
convex.in | convex.out |
---|---|
3 4 AANA NAAA AAAN | 0 |
3 1 N N A | 1 |