Cod sursa(job #1903122)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 4 martie 2017 23:39:34
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <cstring>
#include <string>

using namespace std;

const int NMAX = 1000 + 5;
int freq[NMAX][NMAX][13];

string mat[NMAX];
int freqP[26];

bool ok[NMAX][NMAX];

int main()
{
    ifstream cin("matrix.in");
    ofstream cout("matrix.out");

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++ i) {
        cin >> mat[i];
        mat[i] = " " + mat[i];
        for (int j = 1; j <= N; ++ j)
            ok[i][j] = true;
    }

    string pattern;
    for (int i = 1; i <= M; ++ i) {
        cin >> pattern;
        for (auto it: pattern)
            ++ freqP[it - 'a'];
    }

    int ans = 0;
    for (int addent = 0; addent < 14; addent += 13) {
        for (int i = 1; i <= N; ++ i) {
            for (int j = 1; j <= N; ++ j) {
                for (int k = 0; k < 13; ++ k)
                    freq[i][j][k] = freq[i - 1][j][k] - freq[i - 1][j - 1][k] + freq[i][j - 1][k];

                if (addent == 0) {
                    if (mat[i][j] - 'a' < 13)
                        ++ freq[i][j][mat[i][j] - 'a'];
                }
                else {
                    if (mat[i][j] - 'a' >= 13)
                        ++ freq[i][j][mat[i][j] - 'a' - 13];
                }
            }
        }

        for (int i = 1; i + M - 1 <= N; ++ i)
            for (int j = 1; j + M - 1 <= N; ++ j) {
                for (int k = 0; k < 13 && ok[i][j]; ++ k) {
                    int aux = freq[i + M - 1][j + M - 1][k] + freq[i - 1][j - 1][k] -
                              freq[i + M - 1][j - 1][k]     - freq[i - 1][j + M - 1][k];
                    if (aux != freqP[k + addent])
                        ok[i][j] = false;
                }

                if (addent)
                    ans += ok[i][j];
            }

        if (!addent)
            memset(freq, 0, sizeof freq);
    }

    cout << ans << '\n';
    return 0;
}