4044 - camere

Cerința

Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

Date de intrare

Prima linie din input conține numerele N și M. Pe următoarele N linii se vor găsi câte M caractere din mulțime {'A', 'N', 'C'}, reprezentând elementele matricii.

Date de ieșire

Se va afișa un singur număr, reprezentând valoarea cerută.

Restricții și precizări

1 ≤ N, M ≤ 300

Exemplu

Intrare

3 4
ACNN
NCCA
AACN

Ieșire

Explicație

Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.

Rezolvare

<syntaxhighlight lang="python"> from typing import List

def validate_input(N: int, M: int, matrix: List[List[str]]) -> bool:

   # Verifică dacă N și M sunt în intervalul specificat
   if not (1 <= N <= 300) or not (1 <= M <= 300):
       return False
   # Verifică dacă matricea conține doar caracterele {'A', 'N', 'C'}
   for i in range(N):
       for j in range(M):
           if matrix[i][j] not in {'A', 'N', 'C'}:
               return False
   return True

def count_submatrices(N: int, M: int, matrix: List[List[str]]) -> int:

   count = 0
   # Iterează prin toate submatricile posibile ale matricei
   for i in range(N):
       for j in range(M):
           for k in range(i, N):
               for l in range(j, M):
                   # Calculează numărul de alune și nuci în submatrice
                   num_almonds = sum(matrix[p][q] == 'A' for p in range(i, k+1) for q in range(j, l+1))
                   num_walnuts = sum(matrix[p][q] == 'N' for p in range(i, k+1) for q in range(j, l+1))
                   # Verifică dacă numărul de alune este egal cu numărul de nuci
                   if num_almonds == num_walnuts:
                       count += 1
   return count

def main() -> None:

   # Citirea datelor de intrare
   N, M = map(int, input().split())
   matrix = [list(input().strip()) for _ in range(N)]

   # Validarea datelor de intrare
   if not validate_input(N, M, matrix):
       print("Date de intrare invalide")
       return

   # Rezolvarea problemei și afișarea rezultatului
   result = count_submatrices(N, M, matrix)
   print(result)

if __name__ == '__main__':

   main()

</syntaxhighlight>