Cod sursa(job #1463535)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 21 iulie 2015 10:19:20
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <cstring>

#define NMAX 1001

using namespace std;

char huMap[NMAX][NMAX];
char vir[NMAX];

int freq[30];

bool good[NMAX][NMAX];
int dp[NMAX][NMAX];

int main()
{
    int n, m;
    int i, j;
    ifstream f("matrix.in");
    f >> m >> n;
    for(i = 1; i <= m; i++)
        f >> huMap[i] + 1;
    for(i = 1; i <= n; i++)
    {
        f >> vir;
        for(j = 0; vir[j] != '\0'; j++)
            freq[vir[j] - 'a']++;
    }
    f.close();
    for(i = n; i <= m; i++)
        for(j = n; j <= m; j++)
            good[i][j] = true;
    for(int letter = 0; letter < 27; letter++)
    {
        for(i = 1; i <= m; i++)
            for(j = 1; j <= m; j++)
            {
                if(huMap[i][j] - 'a' == letter)
                    dp[i][j] = 1;
                else
                    dp[i][j] = 0;
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        for(i = n; i <= m; i++)
            for(j = n; j <= m; j++)
            {
                if(!good[i][j] || freq[letter] != (dp[i][j] - dp[i - n][j] - dp[i][j - n] + dp[i - n][j - n]))
                    good[i][j] = false;
            }
    }
    int sol = 0;
    for(i = n; i <= m; i++)
        for(j = n; j <= m; j++)
            if(good[i][j])
                sol++;
    ofstream g("matrix.out");
    g << sol << '\n';
    return 0;
}