Cod sursa(job #631422)

Utilizator sebii_cSebastian Claici sebii_c Data 7 noiembrie 2011 23:21:52
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
using namespace std;

#define NMAX 1024

char map[NMAX][NMAX], c;
int fw[NMAX][NMAX], bc[NMAX][NMAX], v[26];

int main()
{
    ifstream fin("matrix.in");
    ofstream fout("matrix.out");
    int n, m, i, j, k;
    char c;
    fin >> n >> m;
    printf("%d %d\n", n, m);
    for (i=1; i<=n; ++i) {
	for (j=1; j<=n; ++j) {
	    fin >> map[i][j];
	    map[i][j] -= 'a';
	}
    }
    
    for (i=1; i<=m; ++i) {
	for (j=1; j<=m; ++j) {
	    fin >> c;
	    ++v[c-'a'];
	}
    }
    
    for (k=0; k<26; ++k) {
	for (i=1; i<=n; ++i)
	    for (j=1; j<=n; ++j)
		fw[i][j] = fw[i-1][j] + fw[i][j-1] - fw[i-1][j-1] + (map[i][j] == k); 
	for (i=m; i<=n; ++i)
	    for (j=m; j<=n; ++j) {
		int val = fw[i][j] - fw[i-m][j] - fw[i][j-m] + fw[i-m][j-m];
		if (val != v[k])
		    bc[i][j] = 1;
	    }
    }

    int count=0;
    for (i=m; i<=n; ++i)
	for (j=m; j<=n; ++j)
	    count += (bc[i][j] == 1);
    fout << (n-m+1)*(n-m+1)-count;
    return 0;
}