Cod sursa(job #126179)

Utilizator marinMari n marin Data 21 ianuarie 2008 17:05:40
Problema Piese Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#define DIM 501

struct punct{
  int lin,col;
};


int n,m,p,u,h,w,x,lSus,lJos,cStg,cDrp,t,i,j;

punct c[2][DIM*DIM];
int a[DIM+1][DIM+1];

int p2(int n){
  int rez = 1;
  while (rez<<1 <= n)
    rez<<=1;
  return rez;
}


void main(){
  FILE *f = fopen("piese.in","r");
  fscanf(f,"%d %d",&n,&m);
  fclose(f);

  p=1;u=1;
  c[1][p].lin=1;c[1][p].col=1;
  c[2][p].lin=n;c[2][p].col=m;
  while (p<=u) {
    h = p2(c[2][p].lin-c[1][p].lin+1);
    w = p2(c[2][p].col-c[1][p].col+1);
    if (h<w) x = h;
       else x = w;
    if (x>0) {
      t++;
      for (i=c[1][p].lin;i<c[1][p].lin+x;i++)
	for (j=c[1][p].col;j<c[1][p].col+x;j++)
	  a[i][j]=t;
      lSus=c[1][p].lin;lJos=c[1][p].lin+x-1;
      cStg=c[1][p].col+x;cDrp=c[2][p].col;
      if((lJos-lSus>=0)&&(cDrp-cStg>=0)){
	u++;
	c[1][u].lin=lSus;c[1][u].col=cStg;
	c[2][u].lin=lJos;c[2][u].col=cDrp;
      }
      lSus=c[1][p].lin+x;lJos=c[2][p].lin;
      cStg=c[1][p].col;cDrp=c[1][p].col+x-1;
      if((lJos-lSus>=0)&&(cDrp-cStg>=0)){
	u++;
	c[1][u].lin=lSus;c[1][u].col=cStg;
	c[2][u].lin=lJos;c[2][u].col=cDrp;
      }
      lSus=c[1][p].lin+x;lJos=c[2][p].lin;
      cStg=c[1][p].col+x;cDrp=c[2][p].col;
      if((lJos-lSus>=0)&&(cDrp-cStg>=0)){
	u++;
	c[1][u].lin=lSus;c[1][u].col=cStg;
	c[2][u].lin=lJos;c[2][u].col=cDrp;
      }
    }

    p++;
  }
  printf("%d\n",t);
  for (i=1;i<=n;i++) {
    for (j=1;j<=m;j++)
      printf("%d ",a[i][j]);
    printf("\n");
  }

}