Cod sursa(job #2030651)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 1 octombrie 2017 22:12:25
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>

const int MAXN = 1e3;
const int MAXALF = 26;

char a[MAXN + 1][MAXN + 1];
bool check[MAXN + 1][MAXN + 1];
int s[MAXN + 1][MAXN + 1], fr[MAXALF + 1];

int main() {
  int n, m, ans;
  char c;
  FILE *f = fopen("matrix.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%s", a[i] + 1);
  }
  fscanf(f, "%c", &c);
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j) {
      fscanf(f, "%c", &c);
      ++fr[c - 'a' + 1];
    }
    fscanf(f, "%c", &c);
  }
  fclose(f);
  for (int i = m; i <= n; ++i) {
    for (int j = m; j <= n; ++j) {
      check[i][j] = 1;
    }
  }
  for (int i = 1; i <= MAXALF; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        s[j][k] = s[j - 1][k] + s[j][k - 1] - s[j - 1][k - 1] + (a[j][k] + 1 == i + 'a');
      }
    }
    for (int j = m; j <= n; ++j) {
      for (int k = m; k <= n; ++k) {
        if ((s[j][k] - s[j - m][k] - s[j][k - m] + s[j - m][k - m]) != fr[i]) {
          check[j][k] = 0;
        }
      }
    }
  }
  ans = 0;
  for (int i = m; i <= n; ++i) {
    for (int j = m; j <= n; ++j) {
      ans += check[i][j];
    }
  }
  f = fopen("matrix.out", "w");
  fprintf(f, "%d\n", ans);
  fclose(f);    
  return 0;
}