Cod sursa(job #893273)

Utilizator informatician28Andrei Dinu informatician28 Data 26 februarie 2013 14:31:45
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <cstring>

using namespace std;

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

#define m 1025
#define max_alf 27

int M, N, dp[m][m], freq[max_alf], ok[m][m], Sol;
char map[m][m];

int main()
{
    int i, j, lit;
    char ch;
    in >> M >> N;
    // citim harta
    for (i = 1; i <= M; i++)
    {
        for (j = 1; j <= M; j++)
        {
            in >> map[i][j];
        }
    }
    // citim virusul
    for (i = 1; i <= N; i++)
    {
        for (j = 1; j <= N; j++)
        {
            in >> ch;
            freq[ch - 'a' + 1] ++;
        }
    }
    // posibile pozitii de final ale matricei virusului
    for (i = N; i <= M; i++)
    {
        for (j = N; j <= M; j++)
        {
            ok[i][j] = 1;
        }
    }
    // vedem care dintre aceste pozitii nu e corecta/buna
    for (lit = 1; lit <= 26; lit++)
    {
        memset (dp, 0, sizeof(dp));
        for (i = 1; i <= M; i++)
        {
            for (j = 1; j <= M; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (map[i][j] - 'a' + 1 == lit);
            }
        }
        for (i = N; i <= M; i++)
        {
            for (j = N; j <= M; j++)
            {
                if ( (dp[i][j]  - dp[i - N][j] - dp[i][j - N] + dp[i - N][j - N]) != freq[lit]) ok[i][j] = 0;
            }
        }
    }
    // numaram cate dintre aceste pozitii au mai ramas corecte
    for (i = N; i <= M; i++)
    {
        for (j = N; j <= M; j++)
        {
            if (ok[i][j]) ++Sol;
        }
    }
    out << Sol;
    return 0;
}