Cod sursa(job #3166773)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 9 noiembrie 2023 16:24:08
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#define letters 26
#define DIM 1001

using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

int n, m;
int virus[letters];
int current[letters];
bool checked[DIM + 1][DIM + 1];
char matrice[DIM][DIM];
int sol;
char s;

bool equal(int a[], int b[], int length) {
    for (int i = 0; i < length; i++) {
        if (a[i] != b[i])
            return false;
    }
    return true;
}

int solve(int i, int j, int size, int current[]) {
    checked[i][j] = true;
    int prev = 0;
    int currentAux[letters];
    if (j + 1 <= n && !checked[i][j + 1]) {
        for (int letter = 0; letter < letters; letter++) {
            currentAux[letter] = current[letter];
        }
        for (int line = i - size + 1; line <= i; line++) {
            currentAux[matrice[line][j - size + 1] - 'a']--;
            currentAux[matrice[line][j + 1] - 'a']++;
        }
        prev += solve(i, j + 1, size, currentAux);
    }
    if (i + 1 <= n && !checked[i + 1][j]) {
        for (int letter = 0; letter < letters; letter++) {
            currentAux[letter] = current[letter];
        }
        for (int collumn = j - size + 1; collumn <= j; collumn++) {
            currentAux[matrice[i - size + 1][collumn] - 'a']--;
            currentAux[matrice[i + 1][collumn] - 'a']++;
        }
        prev += solve(i + 1, j, size, currentAux);
    }
    return prev + equal(virus, current, letters);
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fin >> matrice[i][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            fin >> s;
            virus[s - 'a']++;
            current[matrice[i][j] - 'a']++;
        }
    }
    fout << solve(m, m, m, current);
}