Cod sursa(job #809119)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 7 noiembrie 2012 21:47:53
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
using namespace std;

char C[1005][1005];
int dp[1005][1005][26],ap[30];

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

    return 0;


}