Cod sursa(job #1204417)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 iulie 2014 21:23:33
Problema Matrix Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define MAXN 1000
#define MAXM 1000
#define ALF 26
int frecv[ALF], vir[ALF];
char om[MAXN][MAXN];

char equal(int *v1, int *v2){
  int i;
  char ad = 1;
  for(i = 0; i < ALF; i++){
    if(v1[i] != v2[i])  ad = 0;
  }
  return ad;
}

int caut(int i, int j, int n, int m){
  int rez = equal(frecv, vir), k;
  if(j + 1 < n){
    for(k = i - m + 1; k <= i; k++){
      frecv[om[k][j - m + 1] - 'a']--;
      frecv[om[k][j + 1] - 'a']++;
    }
    rez += caut(i, j + 1, n, m);
    for(k = i - m + 1; k <= i; k++){
      frecv[om[k][j - m + 1] - 'a']++;
      frecv[om[k][j + 1] - 'a']--;
    }
  }
  if(j - m + 1 == 0 && i + 1 < n){
    for(k = j - m + 1; k <= j; k++){
      frecv[om[i - m + 1][k] - 'a']--;
      frecv[om[i + 1][k] - 'a']++;
    }
    rez += caut(i + 1, j, n, m);
  }
  return rez;
}

int main(){
  FILE *in = fopen("matrix.in", "r");
  int n, m;
  fscanf(in, "%d%d ", &n, &m);
  int i, j;
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      om[i][j] = fgetc(in);
      if(i < m && j < m)  frecv[om[i][j] - 'a']++;
    }
    fgetc(in);
  }
  char ch;
  for(i = 0; i < m; i++){
    for(j = 0; j < m; j++){
      ch = fgetc(in);
      vir[ch - 'a']++;
    }
    fgetc(in);
  }
  fclose(in);
  int rez = caut(m - 1, m - 1, n, m);
  FILE *out = fopen("matrix.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}