Cod sursa(job #3167090)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 9 noiembrie 2023 22:54:58
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 1001
#define alfac 130
bool ok[NMAX][NMAX];
int dp[NMAX][NMAX];
char a[NMAX][NMAX];
int vf[alfac];
int main(void){
    ofstream cout("matrix.out");
    ifstream cin("matrix.in");
    int n, m;
    cin >> n>> m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++)cin >> a[i][j];
    }
    for(int i = 1;i<=m;i++)
        for(int j = 1;j<=m;j++){
             char x;
             cin >> x;
             vf[x]++;
        }
    for(int i = m;i<=n;i++){
        for(int j = m;j<=n;j++)ok[i][j] = 1; /// presupunem ca este o potrivire
     }
    for(int Alfa = 'a'; Alfa <= 'z'; Alfa++){
        for(int i= 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = (a[i][j] == Alfa) + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }
        for(int i = m;i<=n;i++){
            for(int j = m;j<=n;j++){
                if (dp[i][j] - dp[i-m][j] - dp[i][j-m] + dp[i-m][j-m] != vf[Alfa])
                    ok[i][j] = 0; /// nu este o potrivire asa ca am presupunerea noastra este gresita si o anulam
            }
        }
    }
    int ans = 0;
    /// solutia este de fapt cate presupuneri corecte ne au ramas
    for(int i =m;i<=n;i++)
        for(int j = m;j<=n;j++)
            ans += ok[i][j];
    cout << ans << '\n';
}