Cod sursa(job #602213)

Utilizator mihai995mihai995 mihai995 Data 9 iulie 2011 19:46:38
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
using namespace std;

const int N=1001;
int a[N][N],v[27],aux[27],n,m;
bool okay[N][N];
char s[N][N];

ifstream in("matrix.in");
ofstream out("matrix.out");

inline int sum(int x,int y,int z,int t)
{
	return a[z][t]-a[x][t]-a[z][y]+a[x][y];
}

int main()
{
	int i,j,nr=0;
	in>>n>>m>>ws;
	for (i=1;i<=n;i++)
	{
		in.getline(s[i]+1,n+1);
		for (j=1;j<=n;j++)
			okay[i][j]=true;
	}
	for (i=1;i<=n;i++)
	{
		in.getline(s[0]+1,n+1);
		for (j=1;s[0][j];j++)
			v[s[0][j]-'a']++;
	}
	for (char c='a';c<='z';c++)
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				a[i][j]=(s[i][j]==c)+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		for (i=1;i<=n-m+1;i++)
			for (j=1;j<=n-m+1;j++)
				okay[i][j]&=(sum(i-1,j-1,i+m-1,j+m-1)==v[c-'a']);
	}
	for (i=1;i<=n-m+1;i++)
		for (j=1;j<=n-m+1;j++)
			nr+=okay[i][j];
	out<<nr<<"\n";
	return 0;
}