Cod sursa(job #1772942)

Utilizator GinguIonutGinguIonut GinguIonut Data 7 octombrie 2016 11:55:51
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <string.h>

#define nMax 1001
#define chMax 26

using namespace std;

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

int n, m;
int dp[nMax][nMax], viz[chMax];
char mat[nMax][nMax], line[nMax];
bool Sol[nMax][nMax];

void read()
{
    fin>>n>>m;
    fin.get();

    for(int i=1; i<=n; i++)
        fin>>mat[i]+1;

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

void solve()
{
    for(int i=m; i<=n; i++)
        for(int j=m; j<=n; j++)
            Sol[i][j]=1;

    for(int let=0; let<=25; let++)
    {
        if(viz[let])
        {
            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(mat[i][j]-'a'==let)
                        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]!=viz[let])
                            Sol[i][j]=0;
                }
            }
        }
    }

}

void write()
{
    int nrSol=0;
    for(int i=m; i<=n; i++)
        for(int j=m; j<=n; j++)
            nrSol+=Sol[i][j];

    fout<<nrSol;
}

int main()
{
    read();
    solve();
    write();
}