Cod sursa(job #2030269)

Utilizator cella.florescuCella Florescu cella.florescu Data 1 octombrie 2017 13:20:59
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3;

char mat[MAXN + 1][MAXN + 1], ok[MAXN + 1][MAXN + 1];
int sp[MAXN + 1][MAXN + 1], freq[200];

int main()
{
    int n, m;
    ifstream fin("matrix.in");
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        fin >> mat[i][j];
    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= m; ++j) {
        char ch;
        fin >> ch;
        ++freq[ch];
      }
    fin.close();
    memset(ok, 1, sizeof ok);
    for (char ch = 'a'; ch <= 'z'; ++ch) {
      memset(sp, 0, sizeof sp);
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
          sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + (mat[i][j] == ch);
          if (i >= m && j >= m && (sp[i][j] - sp[i - m][j] - sp[i][j - m] + sp[i - m][j - m]) != freq[ch])
            ok[i][j] = 0;
        }
    }
    int ans = 0;
    for (int i = m; i <= n; ++i)
      for (int j = m; j <= n; ++j)
        ans += ok[i][j];
    ofstream fout("matrix.out");
    fout << ans;
    fout.close();
    return 0;
}