Pagini recente » Cod sursa (job #2607112) | Borderou de evaluare (job #1551157) | Cod sursa (job #2232659) | Cod sursa (job #3277521) | Cod sursa (job #761055)
Cod sursa(job #761055)
#include<stdio.h>
#include<string.h>
#define NMAX 506
#define MMAX 102
int M1[ NMAX ][ NMAX ], M2[ MMAX ][ MMAX ], A[ NMAX ][ NMAX ], B[ MMAX ][ MMAX ], C[ NMAX ][ NMAX ], L[ MMAX ][ MMAX ], n, m, nr;
void read()
{
int i, j;
FILE *f = fopen("tetris2.in", "r");
fscanf(f, "%d", &n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
fscanf(f, "%d", &M1[i][j]), A[i][j-1] = M1[i][j-1] - M1[i][j];
fscanf(f, "%d", &m);
for(i = 1; i <= m; i++)
for(j = 1; j <= m; j++)
fscanf(f, "%d", &M2[i][j]), B[i][j-1] = M2[i][j] - M2[i][j-1];
fclose(f);
if(m == 1)
nr = n * n;
}
void Prefix(int l)
{
int k, i;
L[l][1] = 0;
for(i = 2; i < m; i++)
{
k = L[l][i-1];
while(k && B[l][k+1] != B[l][i])
k = L[l][k];
if(B[l][k+1] == B[l][i])
k++;
L[l][i] = k;
}
}
void KMP(int l1, int l2)
{
int i, k = 0;
for(i = 1; i <= n; i++)
{
while(k > 0 && B[l2][k+1] != A[l1][i])
k = L[l2][k];
if(B[l2][k+1] == A[l1][i])
k++;
if(k == m - 1)
{
C[l1][i - m + 1] = 1;
k = L[l2][k];
}
}
}
void solve()
{
int i, q, l, c, s;
for(i = 1; i <= m; i++)
Prefix(i);
for(i = 1; i <= n - m + 1; i++)
{
memset(C, 0, sizeof(C));
for(q = 1; q <= m; q++)
KMP(i + q - 1, q);
for(c = 1; c <= n - m + 1; c++)
{
if(C[i][c])
{
s = 1, l = i + 1;
while(C[l][c])
s++, l++;
if(s == m)
nr++;
}
}
}
}
void write()
{
FILE *g = fopen("tetris2.out", "w");
fprintf(g, "%d\n", nr);
fclose(g);
}
int main()
{
read();
if(!nr)
solve();
write();
return 0;
}