Cod sursa(job #2363164)

Utilizator anamariatoaderAna Toader anamariatoader Data 3 martie 2019 13:01:23
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <cstring>

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

short int n,m,i,j,k,v[1001][1001];
int s[1001][1001];
int fr[27],nr;
char c;
bool sol[1001][1001];

int main(){
    fin>>m>>n;
    for(i=1;i<=m;i++)
      for(j=1;j<=m;j++){
          fin>>c;
          v[i][j]=c-'a'+1;
      }
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++){
          fin>>c;
          fr[c-'a'+1]++;
      }
    for(i=n;i<=m;i++)
        for(j=n;j<=m;j++)
            sol[i][j]=1;
    for(k=1;k<=26;k++)
       if(fr[k]!=0){
          for(i=1;i<=m;i++)
            for(j=1;j<=m;j++)
                if(v[i][j]==k)
                  s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1;
                else
                   s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
          for(i=n;i<=m;i++)
            for(j=n;j<=m;j++){
                if(s[i][j]-s[i-n][j]-s[i][j-n]+s[i-n][j-n]!=fr[k])
                    sol[i][j]=0;
              }
       }
    for(i=n;i<=m;i++)
        for(j=n;j<=m;j++)
            nr+=sol[i][j];
    fout<<nr;
    return 0;
}