Cod sursa(job #809135)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 7 noiembrie 2012 22:02:20
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char C[1005][1005];
int dp[1005][1005],ap[30];
bool final[1005][1005];

int main()
{
    int n,m,total=0;
    ifstream f("matrix.in");
    ofstream g("matrix.out");
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f>>C[i][j];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
          {
              char x;
              f>>x;
              ap[x-'a']++;
          }
    memset(final,1,sizeof(final));

    for(int k=0;k<26;k++)
    {
        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(k==(C[i][j]-'a'))
                    dp[i][j]++;
                bool se_poate=true;
                if(i-m>=0 && j-m>=0)
                 {
                    if(ap[k]!=( dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]))
                    {
                        se_poate=false;
                        break;
                    }
                 }
                else
                    se_poate=false;
                final[i][j]&=se_poate;
            }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            total+=final[i][j];
    g<<total;

    return 0;


}