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

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile 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