Cod sursa(job #1598980)

Utilizator LucianTLucian Trepteanu LucianT Data 13 februarie 2016 14:58:28
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define maxN 1004
using namespace std;
int n, m, i, j, sol;
char a[maxN][maxN], x, c;
bool ok[maxN][maxN];
int dp[maxN][maxN];
int fr[130];
int main()
{
    ifstream f("matrix.in");
    ofstream g("matrix.out");
    f >> n >> m;
    for(i = 1; i <= n; i++)
        f>>(a[i]+1);
    for(i = 1; i <= m; i++)
        for(j = 1; j <= m; j++)
        f>>x, fr[x]++;
    for(c = 'a'; c <= 'z'; c++)
    {
        for(i = 1; i <= n; i++)
            for(j = 1;j <= n; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            if(a[i][j] == c) dp[i][j]++;
        }
        for(i = m; i <= m; i++)
            for(j = m; j <= m; j++)
            if(dp[i][j] - dp[i-m][j] - dp[i][j-m] + dp[i-m][j-m] != fr[c])
            ok[i][j] = true;
    }
    for(i = m; i <= n; i++)
        for(j = m; j <= n; j++)
        if(!ok[i][j]) sol++;
    g << sol;
    return 0;
}