Cod sursa(job #3167408)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 10 noiembrie 2023 18:25:10
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
#define DIM 1001
#define y1 iurewhfiu

using namespace std;

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

int a[DIM][DIM], dp[DIM][DIM], valid[DIM][DIM];

int f[DIM];

char c;

int i, j, n, m, k, answer;

int check(int x1, int y1, int x2, int y2){

    return (dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x2][y2]);

}

int main(){

    fin >> n >> m;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){

            fin >> c;

            a[i][j] = c - 'a' + 1;

            if(i + m - 1 <= n && j + m - 1 <= n)

                valid[i][j] = 1;

        }

    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++){

            fin >> c;

            f[c - 'a' + 1]++;

        }

    for(k=1;k<=26;k++){

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                dp[i][j] = 0;

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                dp[i][j] += (a[i][j] == k) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(check(i, j, i + m - 1, j + m - 1) != f[k])
                    valid[i][j] = 0;

    }

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            answer += valid[i][j];

    fout << answer;

    return 0;
}