Pagini recente » Cod sursa (job #661107) | Borderou de evaluare (job #123276) | Cod sursa (job #3201662) | Cod sursa (job #492054)
Cod sursa(job #492054)
#include<cstdio>
const int NMAX=1<<10;
int m1[NMAX][NMAX];
int f2[27];
int f1[27];
int M,N;
int sumc[NMAX][NMAX][26];
void fisiere()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
}
void citeste()
{
fisiere();
int i,j;
char s[NMAX];
scanf("%d%d",&M,&N);
for (i=1;i<=M;++i)
{
gets(s);
for (j=0;j<M;++j)
m1[i][j+1]=s[j]-'a';
}
for (i=1;i<=N;++i)
{
gets(s);
for (j=0;j<N;++j)
++f2[s[j]-'a'];
}
}
void cop(int a,int b)
{
int k;
for (k=0;k<26;++k)
sumc[a][b][k]=sumc[a][b-1][k];
}
void sumpart()
{
int j,i;
for (j=1;j<=M;++j)
sumc[1][j][m1[1][j]]++;
for (i=2;i<=M;++i)
for (j=1;j<=M;++j)
{
cop(i,j);
sumc[i][j][m1[i][j]]++;
}
}
bool egalitate()
{
int i;
for (i=0;i<26;++i)
if (f1[i]!=f2[i])
return false;
return true;
}
void actualizare(int c1,int c2,int i2)
{
int k;
for (k=0;k<26;++k)
f1[k]+=sumc[i2][c2][k]-sumc[i2][c1][k];
}
void actualizare2(int i1,int i2)
{
int j,k;
for (j=1;j<=N;++j)
for (k=0;k<26;++k)
f1[k]-=sumc[i1][j][k]-sumc[i1-1][j][k]+sumc[i2][j][k]-sumc[i2-1][j][k];
}
void afiseaza(int numar)
{
printf("%d",numar);
}
void rezolva()
{
int numar, c1,c2, i1,i2, i,j;
numar=0;
for (i=1;i<=N;++i)
for (j=1;j<=N;++j)
f1[m1[i][j]]++;
i1=1;
i2=N;
do
{
c1=1;
c2=N;
do
{
if (egalitate()==true) ++numar;
++c2;
actualizare(c1,c2,i2);
++c1;
}while(c2<=M);
++i2;
actualizare2(i1,i2);
++i1;
}while(i2<=M);
afiseaza(numar);
}
int main()
{
citeste();
sumpart();
rezolva();
return 0;
}