Cod sursa(job #2013166)

Utilizator mihai.alphamihai craciun mihai.alpha Data 20 august 2017 17:54:23
Problema Matrix Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <string.h>

#define MAX_N 1000
#define alfa 1000

int N, M;
FILE *fin, *fout;

int ap[alfa + 1];
char a[MAX_N + 1][MAX_N + 1];
bool pot[MAX_N + 1][MAX_N + 1];
int current[MAX_N + 1][MAX_N + 1];

int main() {
	fin = fopen("matrix.in", "r");
	fout = fopen("matrix.out", "w");
	fscanf(fin, "%d%d", &N, &M);
	fgetc(fin);
	char c;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			a[i][j] = fgetc(fin);
		}
		fgetc(fin);
	}
	int sum = 0;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= M; j++) {
			c = fgetc(fin);
			ap[c - 'a']++;
		}
		fgetc(fin);
	}
	for (int lit = 0; lit < alfa; lit++) {
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++) {
				int ok = 0;
				if (a[i][j] - 'a' == lit) {
					ok = 1;
				}
				current[i][j] = current[i - 1][j] + current[i][j - 1] - current[i - 1][j - 1] + ok;
			}
		for(int i = N - M + 1;i <= N;i++)
			for (int j = N - M + 1; j <= N; j++) {
				int sum = current[i][j] - current[i - M][j] - current[i][j - M] + current[i - M][j - M];
				if (sum != ap[lit])
					pot[i][j] = 1;
			}
	}
	int ans = 0;
	for (int i = N - M + 1; i <= N; i++)
		for (int j = N - M + 1; j <= N; j++)
			ans += 1 - pot[i][j];
	fprintf(fout, "%d", ans);
	fclose(fin);
	fclose(fout);
	return 0;
}