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 efectuează verificarea, care va afișa un mesaj corespunzător în funcție de input-ul dat și cerințele de validitate ale problemei. Dacă testele de validitate sunt efectuate cu succes, pe un rând nou 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

Date de intrare valide

18

Explicație exemplu

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

if __name__ == '__main__':

   # 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
   else:
       print("Date de intrare valide")
   # Rezolvarea problemei și afișarea rezultatului
   result = count_submatrices(N, M, matrix)
   print(result)

</syntaxhighlight>

Explicație cod

Programul are trei funcții principale:

1. `validate_input`: verifică dacă datele de intrare sunt valide. Verifică dacă N și M se încadrează în intervalul specificat și dacă matricea conține doar caracterele {'A', 'N', 'C'}.

2. `count_submatrices`: calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N'. Iterează prin toate submatricile posibile ale matricei și verifică condiția.

3. `main`: citește datele de intrare, validează datele, rezolvă problema și afișează rezultatul.

Programul citește N și M de la intrarea standard, apoi citește matricea de dimensiune N x M. Apoi, datele de intrare sunt validate folosind funcția `validate_input`. Dacă datele de intrare sunt valide, programul calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N', folosind funcția `count_submatrices`. Rezultatul este afișat la ieșirea standard.