Fişierul intrare/ieşire:convex.in, convex.outSursăCerc informatică Vianu
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.15 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inconvex.out
3 4
AANA
NAAA
AAAN
0
3 1
N
N
A
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici