Cod sursa(job #3167936)
Utilizator | Gabriel Stefan Tita gabriel.9619 | Data | 11 noiembrie 2023 12:06:36 |
---|---|---|---|
Problema | Matrix | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.43 kb |
#include <fstream>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
char a[1005][1005];
int dp[1005][1005], ok[1005][1005], f[150];
int main()
{
char c;
int n, m, i, j;
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>>c;
f[c]++;
}
}
for(i=m;i<=n;i++)
{
for(j=m;j<=n;j++)
{
ok[i][j]=1;
}
}
for(c='a';c<='z';c++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]==c)
{
dp[i][j]=1+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
}
else
{
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
}
}
}
for(i=m;i<=n;i++)
{
for(j=m;j<=n;j++)
{
if(dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]!=f[c])
{
ok[i][j]=0;
}
}
}
}
int sol=0;
for(i=m;i<=n;i++)
{
for(j=m;j<=n;j++)
{
if(ok[i][j]==1)
{
sol++;
}
}
}
fout<<sol;
}