Cod sursa(job #1038065)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 20 noiembrie 2013 23:01:02
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <cstring>

#define maxn 1001

using namespace std;

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

char a[maxn][maxn],b[maxn][maxn];
int dp[maxn][maxn];
bool ok[maxn][maxn];

int q[260],total,n,m;

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)
        fin>>b[i][j],q[b[i][j]]++;

    memset (ok,1,sizeof(ok));

    for (int k='a'; k<='z'; ++k)
    {
        memset (dp,0,sizeof(dp));

        for (int i=1; i<=n; ++i)
            for (int 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]==k) ++dp[i][j];

            if (i>=m && j>=m)
                if (dp[i][j]-dp[i][j-m]-dp[i-m][j]+dp[i-m][j-m]!=q[k]) ok[i][j] = 0;
        }
    }

    for (int i=m; i<=n; ++i)
        for (int j=m; j<=n; ++j)
    {
        if (ok[i][j]) ++total;
    }

    fout<<total;
}