Fişierul intrare/ieşire:	convex.in, convex.out	Sursă	Cerc informatică Vianu
Autor	Cristian Francu	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	0.15 sec	Limită de memorie	4096 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

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