Cod sursa(job #3282105)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 4 martie 2025 15:28:30
Problema Matrix Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;
const int nmax = 1e4;
char mat[nmax + 1][nmax + 1];
int k, vc[26];
void upd(int poz, int val)
{
    vc[poz] += val;
    if(vc[poz] == 0)
        k--;
    if(vc[poz] == val)
        k++;
}
int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    int n, m, i, j, sol = 0;
    char ch;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            cin >> mat[i][j];
    for(i = 1; i <= m; i++)
        for(j = 1; j <= m; j++)
        {
            cin >> ch;
            upd(ch - 'a', 1);
            upd(mat[i][j] - 'a', -1);
        }
    int l = m, c = m;
    while(l <= n)
    {
        if(k == 0)
            sol++;
        if(c == m)
        {
            while(c < n)
            {
                for(i = l; i >= l - m + 1; i--)
                {
                    upd(mat[i][c + 1] - 'a', -1);
                    upd(mat[i][c - m + 1] - 'a', 1);
                }
                if(k == 0)
                    sol++;
                c++;
            }
            if(l <= n)
            {
                for(j = n; j >= n - m + 1; j--)
                {
                    upd(mat[l + 1][j] - 'a', -1);
                    upd(mat[l - m + 1][j] - 'a', 1);
                }
            }
            l++;
        }
        else
        {
            while(c > m)
            {
                for(i = l; i >= l - m + 1; i--)
                {
                    upd(mat[i][c] - 'a', 1);
                    upd(mat[i][c - m] - 'a', -1);
                }
                if(k == 0)
                    sol++;
                c--;
            }
            if(l <= n)
            {
                for(j = 1; j <= m; j++)
                {
                    upd(mat[l + 1][j] - 'a', -1);
                    upd(mat[l - m + 1][j] - 'a', 1);
                }
            }
            l++;
        }
    }
    cout << sol;
    return 0;
}