Cod sursa(job #64693)

Utilizator raula_sanChis Raoul raula_san Data 4 iunie 2007 22:10:01
Problema Matrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <cstring>

#define Max 1001
#define Alpha 27

char A[Max][Max], B[Max][Max];

int N, M, SC;
int C[Alpha], S[Max][Max];

long long Sol;

void Read();
void Solve();
void Write();

int Ok(int, int);

int main()
{
    Read();
    Solve();
    Write();
    
    return 0;
}

void Read()
{
     FILE *f = fopen("matrix.in", "rt");
     int i, j, k;
     
	 for(fscanf(f, "%d %d\n", &N, &M), i=0; i<N; ++i)
     {
                   fgets(A[i], Max, f);
				   k = strlen(A[i]) - 1;

				   for(j=0; j<k; ++j)
				   {
							if(!i && !j) S[i][j] = (int) A[i][j] - 'a' + 1;

							else if(!i) S[i][j] = S[i][j-1] + (int) A[i][j] - 'a' + 1;
							else if(!j) S[i][j] = S[i-1][j] + (int) A[i][j] - 'a' + 1;

							else
								S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + (int) A[i][j] - 'a' + 1;
				   }
	 }

	 for(i=0; i<M; ++i)
	 {
			  fgets(B[i], Max, f);
			  k = strlen(B[i]) - 1;

			  for(j=0; j<k; ++j)
					   ++ C[(int) B[i][j] - 'a' + 1];
	 }

	 fclose(f);
}

void Solve()
{
	 int i, j, s;

	 for(i=1; i<Alpha; ++i) SC += C[i] * i;

	 for(i=M-1; i<N; ++i)
				for(j=M-1; j<N; ++j)
				{
						   if(i == M-1 && j == M-1) s = S[i][j];

						   else if(i == M-1) s = S[i][j] - S[i][j-M];
						   else if(j == M-1) s = S[i][j] - S[i-M][j];

						   else
							   s = S[i][j] - S[i-M][j] - S[i][j-M] + S[i-M][j-M];

						   if(s == SC && Ok(i-M+1, j-M+1)) ++ Sol;
				}
}

void Write()
{
	FILE *g = fopen("matrix.out", "wt");

	fprintf(g, "%lld", Sol);

	fclose(g);
}

int Ok(int i, int j)
{
	int r, c;

	int Count[Alpha] = { 0 };

	for(r=i; r<=i+M-1; ++r)
			 for(c=j; c<=j+M-1; ++c)
             {
					  ++ Count[(int) A[r][c] - 'a' + 1];

                      if(Count[(int) A[r][c] - 'a' + 1] > C[(int) A[r][c] - 'a' + 1])
                                     return 0;
             }

    for(i=1; i<Alpha; ++i)
             if(Count[i] != C[i])
                         return 0;
                         
    return 1;
}