Cod sursa(job #1097105)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 2 februarie 2014 23:28:18
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

char C[1005][1005];

int dp[1005][1005],ap[30];

int 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];
            final[i][j]=1;
         }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
          {
              char x;
              f>>x;
              ap[x-'a']++;
          }

    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];

                if(i-m>=0 && j-m>=0 && ap[k]==( dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]))
                        final[i][j]*=1;
                    else
                        final[i][j]=0;
            }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            total+=final[i][j];
    g<<total;

    return 0;

}