Cod sursa(job #1315250)

Utilizator hrazvanHarsan Razvan hrazvan Data 12 ianuarie 2015 17:39:18
Problema BMatrix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <stdio.h>
#define MAXN 200
char ma1[MAXN][MAXN], ma2[MAXN][MAXN];
int sums[MAXN][MAXN], sumj[MAXN][MAXN], ds[MAXN], dj[MAXN];

void refl(char ma[MAXN][MAXN], int n, int m){
  int i, j, aux;
  for(i = 0; i < (n >> 1); i++){
    for(j = 0; j < m; j++){
      aux = ma[i][j];
      ma[i][j] = ma[n - i - 1][j];
      ma[n - i - 1][j] = aux;
    }
  }
}

void parc(int st, int dr, int pas, int *v, int *rez){
  int i, stiv[MAXN], cp = 0;
  for(i = st; i != dr + pas; i += pas){
    while(cp > 0 && v[stiv[cp - 1]] > v[i]){
      rez[stiv[cp - 1]] = i;
      cp--;
    }
    stiv[cp] = i;
    cp++;
  }
  while(cp > 0){
    rez[stiv[cp - 1]] = dr + pas;
    cp--;
  }
}

int sky(int *v, int n){
  int st[MAXN], dr[MAXN], i, max = 0;
  parc(0, n - 1, 1, v, dr);
  parc(n - 1, 0, -1, v, st);
  for(i = 0; i < n; i++){
    if(v[i] * (dr[i] - st[i] - 1) > max)
      max = v[i] * (dr[i] - st[i] - 1);
  }
  return max;
}

void calc(int sum[MAXN][MAXN], int *d, char ma[MAXN][MAXN], int n, int m){
  int i, j;
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      if(ma[i][j] == 0){
        if(i == 0)
          sum[i][j] = 1;
        else
          sum[i][j] = sum[i - 1][j] + 1;
      }
      else
        sum[i][j] = 0;
    }
  }
  int max;
  for(i = 0; i < n; i++){
    d[i] = 0;
    if(i != 0)
      d[i] = d[i - 1];
    max = sky(sum[i], m);
    if(d[i] < max)
      d[i] = max;
  }
}

int rezolv(char ma[MAXN][MAXN], int n, int m){
  calc(sums, ds, ma, n, m);
  refl(ma, n, m);
  calc(sumj, dj, ma, n, m);
  refl(ma, n, m);
  int i, max = 0, aux;
  for(i = 0; i < (n >> 1); i++){
    aux = dj[n - i - 1];
    dj[n - i - 1] = dj[i];
    dj[i] = aux;
  }
  for(i = 0; i < n - 1; i++){
    if(ds[i] + dj[i + 1] > max)
      max = ds[i] + dj[i + 1];
  }
  return max;
}

int main(){
  FILE *in = fopen("bmatrix.in", "r");
  int n, m, i, j;
  fscanf(in, "%d%d ", &n, &m);
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      ma1[i][j] = fgetc(in) - '0';
      ma2[j][n - i - 1] = ma1[i][j];
    }
    fgetc(in);
  }
  fclose(in);
  int max, m1, m2;
  m1 = rezolv(ma1, n, m);
  m2 = rezolv(ma2, m, n);
  if(m1 < m2)
    max = m2;
  else
    max = m1;
  FILE *out = fopen("bmatrix.out", "w");
  fprintf(out, "%d", max);
  fclose(out);
  return 0;
}