Cod sursa(job #2162487)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 12 martie 2018 11:28:50
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define N 1002
using namespace std;
ifstream in("matrix.in");
ofstream out("matrix.out");
string s[N];
int arr[200];
int dp[N][N];
bool b[N][N];
int main()
{
    int n,m,i,j,nr=0;
    char c;
    in>>n>>m;
    for(i=1;i<=n;i++)
        in>>s[i],s[i]=' '+s[i];
    for(i=0;i<m*m;i++)
    {
        in>>c;
        arr[c]++;
    }
    for(c='a';c<='z';c++)
        if(arr[c])
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                {
                    dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
                    if(s[i][j]==c)
                        dp[i][j]++;
                }
            for(i=m;i<=n;i++)
                for(j=m;j<=n;j++)
                    if(dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]!=arr[c])
                        b[i][j]=1;
        }
    for(i=m;i<=n;i++)
        for(j=m;j<=n;j++)
            if(b[i][j]==0)
                nr++;
    out<<nr;
    return 0;
}