Cod sursa(job #2354981)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 25 februarie 2019 18:50:04
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <bitset>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int d[1002][1002];
bitset <1002> ok[1002];
int fr[200],n,m,i,j;
bool num(int x1,int y1,int x2,int y2,char car){
int sum=0;
sum+=d[x2][y2];
sum-=d[x1-1][y2];
sum-=d[x2][y1-1];
sum+=d[x1-1][y1-1];
if(sum==fr[car])
    return 1;
return 0;
}
char a[1002][1002],b[1002][1002];
int main(){
fin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fin>>a[i][j];
for(i=1;i<=m;i++)
for(j=1;j<=m;j++){
fin>>b[i][j];
fr[b[i][j]]++;
}
for(i=m;i<=n;i++)
for(j=m;j<=n;j++)
ok[i][j]=1;

for(char lit='a';lit<='z';lit++){
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
    d[i][j]=(a[i][j]==lit)+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
    if(i<m||j<m)
        continue;
    if( num(i-m+1,j-m+1,i,j,lit)==0 )
        ok[i][j]=0;
    }
}
int sol=0;
for(i=m;i<=n;i++)
    for(j=m;j<=n;j++)
    sol+=ok[i][j];

fout<<sol;
}