Pagini recente » Cod sursa (job #647311) | Cod sursa (job #2934877) | Cod sursa (job #24551) | Cod sursa (job #203190) | Cod sursa (job #893273)
Cod sursa(job #893273)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("matrix.in");
ofstream out ("matrix.out");
#define m 1025
#define max_alf 27
int M, N, dp[m][m], freq[max_alf], ok[m][m], Sol;
char map[m][m];
int main()
{
int i, j, lit;
char ch;
in >> M >> N;
// citim harta
for (i = 1; i <= M; i++)
{
for (j = 1; j <= M; j++)
{
in >> map[i][j];
}
}
// citim virusul
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
in >> ch;
freq[ch - 'a' + 1] ++;
}
}
// posibile pozitii de final ale matricei virusului
for (i = N; i <= M; i++)
{
for (j = N; j <= M; j++)
{
ok[i][j] = 1;
}
}
// vedem care dintre aceste pozitii nu e corecta/buna
for (lit = 1; lit <= 26; lit++)
{
memset (dp, 0, sizeof(dp));
for (i = 1; i <= M; i++)
{
for (j = 1; j <= M; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (map[i][j] - 'a' + 1 == lit);
}
}
for (i = N; i <= M; i++)
{
for (j = N; j <= M; j++)
{
if ( (dp[i][j] - dp[i - N][j] - dp[i][j - N] + dp[i - N][j - N]) != freq[lit]) ok[i][j] = 0;
}
}
}
// numaram cate dintre aceste pozitii au mai ramas corecte
for (i = N; i <= M; i++)
{
for (j = N; j <= M; j++)
{
if (ok[i][j]) ++Sol;
}
}
out << Sol;
return 0;
}