Cod sursa(job #1204834)

Utilizator hrazvanHarsan Razvan hrazvan Data 4 iulie 2014 10:45:49
Problema Matrix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#define MAXN 1000
#define MAXM 1000
#define ALF 26
int frecv[ALF], vir[ALF];
char om[MAXN][MAXN];
short linii[MAXN][MAXN][ALF];

void frecventa(int n, int m){
  int i, j, k;
  for(j = 0; j < n; j++){
    for(i = 0; i < n; i++){
      if(i < m) linii[0][j][om[i][j] - 'a']++;
      else{
        for(k = 0; k < ALF; k++){
          linii[i - m + 1][j][k] = linii[i - m][j][k];
        }
        linii[i - m + 1][j][om[i][j] - 'a']++;
        linii[i - m + 1][j][om[i - m][j] - 'a']--;
      }
    }
  }
  return ;
}

void adunlinie(int *v1, short *v2, int prod){
  int i;
  for(i = 0; i < ALF; i++){
    v1[i] += v2[i] * prod;
  }
  return ;
}

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){
    adunlinie(frecv, linii[i - m + 1][j - m + 1], -1);
    adunlinie(frecv, linii[i - m + 1][j + 1], 1);
    rez += caut(i, j + 1, n, m);
    adunlinie(frecv, linii[i - m + 1][j - m + 1], 1);
    adunlinie(frecv, linii[i - m + 1][j + 1], -1);
  }
  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);
    }
    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);
  frecventa(n, m);
  for(j = 0; j < m; j++){
    adunlinie(frecv, linii[0][j], 1);
  }
  int rez = caut(m - 1, m - 1, n, m);
  FILE *out = fopen("matrix.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}