Cod sursa(job #422018)

Utilizator andreirulzzzUPB-Hulea-Ionescu-Roman andreirulzzz Data 22 martie 2010 00:48:20
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <cstring>
#define FOR(i,a,b) for(i=a;i<=b;i++)
using namespace std;

char a[1001][1001],b[1001][1001];
short k=0,nr,ok,i1,j1,i2,j2,car[256],aux[256],m,n,i,j;

int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d%d",&m,&n);
	FOR(i,1,m) scanf("%s",&a[i]);
	FOR(i,1,n) scanf("%s",&b[i]);
	FOR(i,1,n) FOR(j,0,n-1) ++car[int(b[i][j])];
	FOR(i,1,n) FOR(j,0,n-1) ++aux[int(a[i][j])];
	i1=j1=1,i2=j2=n;
	while (1){
		ok=1;
		FOR(i,97,122) if (car[i]!=aux[i]){ok=0;break;}
		if (ok) ++nr;
		if (k==0) ++j1,++j2;
		if (k==1) --j1,--j2;
		if (j2>m||!j1){
			++i1,++i2;
			if (i2>m) break;
			if (k){ 
				k=0;
				++j1,++j2;
				FOR(i,j1-1,j2-1)
					--aux[int(a[i1-1][i])],++aux[int(a[i2][i])];
				continue;
			}
			else {
				k=1;
				--j1,--j2;
				FOR(i,j1-1,j2-1)
					--aux[int(a[i1-1][i])],++aux[int(a[i2][i])];
				continue;
			}
		}
		if (!k)
			FOR(i,i1,i2)
				--aux[int(a[i][j1-2])],++aux[int(a[i][j2-1])];
		else
			FOR(i,i1,i2)
				++aux[int(a[i][j1-1])],--aux[int(a[i][j2])];
	}
	printf("%d\n",nr);
	return 0;
}