Cod sursa(job #683252)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 20 februarie 2012 12:43:36
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
 
using namespace std;
 
char x;
int v[26],c[26], a[1024][1024],m,n,sum=0;
 
int verif()
{
    for(int i=1;i<=26;i++)
        if(c[i]!=v[i]) return 0;
    return 1;
}
void citire()
{
    ifstream fin("matrix.in");
    fin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            fin >>x;
            a[i][j]=x-'a'+1;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            fin>>x;
            ++v[x-'a'+1];
        }
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ++c[a[i][j]];*/
    /*if(verif())
		sum++;*/
}
void inlocuire(int x,int y,int k)
{
    for(int i=x;i<=n+x-1;i++)
        c[a[i][y]]+=k;
    for(int i=x;i<=n+x-1;i++)
        c[a[i][y+n]]-=k;
}
void det()
{
    for(int i=1;i<=m-n+1;i+=2)
    {
		for(int i2=i;i2<=n;i2++)
			for(int j2=1;j2<=n;j2++)
				++c[a[i2][j2]];
		if(verif()) sum++;
        for(int j=1;j<=m-n;j++)
        {
            inlocuire(i,j,-1);
            if(verif()) sum++;
        }
		for(int i2=m;i2>=m-n+1;i2--)
			c[a[i][i2]]--;
		for(int i2=m;i2>=m-n+1;i2--)
			c[a[i+n][i2]]++;
        //for(int i2=1;i2<=26;i2++)
        //    c[i2]=0;
        /*for(int i2=i+1;i2<=n+i;i2++)
            for(int j2=1;j2<=n;j2++)
                ++c[a[i2][j2]];*/
        if(verif()) sum++;
		for(int j=m-n;j>=1;j--)
        {
            inlocuire(i+1,j,1);
            if(verif()) sum++;
        }
    }
}
int main()
{
    citire();
    det();
    ofstream fout("matrix.out");
    fout<<sum;
    return 0;
}