Cod sursa(job #2243784)

Utilizator osiaccrCristian Osiac osiaccr Data 21 septembrie 2018 13:23:12
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#define DEF 1010

using namespace std;

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

int V[26], S[DEF][DEF], n, m, sol;

char A[DEF][DEF];

bool OK[DEF][DEF][26];

void inline add (int A[], int x) {
    A[x] += 1;
}

void add (int A[], int B[]) {
    for (int i = 0; i < 26; ++ i) {
        A[i] += B[i];
    }
}

void substract (int A[], int B[]) {
    for (int i = 0; i < 26; ++ i) {
        A[i] -= B[i];
    }
}

bool cmp (int A[], int B[]) {
    for (int i = 0; i < 26; ++ i) {
        if (A[i] != B[i])
            return false;
    }
    return true;
}

int main () {

    fin >> n >> m;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            fin >> A[i][j];
        }
    }

    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            char c;
            fin >> c;
            ++ V[c - 'a'];
        }
    }

    for (int c = 0; c < 26; ++ c) {

        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (A[i][j] - 'a' == c);
            }
        }

        for (int i = m; i <= n; ++ i) {
            for (int j = m; j <= n; ++ j) {
                int temp = S[i][j] - S[i - m][j] - S[i][j - m] + S[i - m][j - m];
                if (temp == V[c]) {
                    OK[i][j][c] = true;
                }
            }
        }

    }

    for (int i = m; i <= n; ++ i) {
        for (int j = m; j <= n; ++ j) {
            bool temp = true;
            for (int k = 0; k < 26; ++ k) {
                if (!OK[i][j][k]) {
                    temp = false;
                    break;
                }
            }
            sol += temp;
        }
    }

    fout << sol;

}