Impaturirea Hartii

[•cr1st18]

Cine a mai rezolvat problema aceasta cu impaturirea hartii .....se poate rezolva cu divide et impera ....este din cartea programarea in limbajul c++ pentru liceu-tehnici si metode de programare de emanuela cherchez si serban marinel........o harta strategica este reprezentata ca o matrice cu n linii si m coloane ,fiecare componenta avand cota terenului respectiv.Determinati o modalitate de a impaturi harta astfel incat zona deasupra sa aiba arie maxima si aceasi cota,plierea hartii se face doar orizontal si vertical si numai in parti egale(daca dimensiunea este impara nu se face plierea).Pe ecran sa se afiseze aria maxima cu cota si codificarea plierilor(aici am avut probleme) dupa urmatoarea conventie: mai intai se precizeaza directia (O-orizontal,V-verical,apoi pozitia de la care se face plierea iar apoi modul plierii(L-partea stanga deasupra,R-partea dreapta deasupra,U-partea de sus deasupra,D-partea de jos deasupra ) 2 plieri consecutive fiind separate prin " " ...........deci daca careva are timp.....sau daca a rezolvat-o sa-mi dea niste indicii sau nu stiu ........la codarea plierilor nu prea stiu cum sa fac:P

[•alexandru92]

ai scris codul pana la "codificare pilierilor" ?

[•cr1st18]

Cod:

int arie,amax=-MAXINT,cota,harta[50][50],n,m;

char a[50][50];

int verif(int xs,int ys,int xd,int yd){

int c,i,j;

c=harta[ys][xs];

for(i=ys;i<=yd;i++)
for(j=xs;j<=xd;j++)
if(harta[i][j]!=c)
return 0;


return 1;}


void pliaza(int xs,int ys,int xd,int yd){

char aux[50],u[50],d[50],r[50],l[50];

if(verif(xs,ys,xd,yd)==1){
arie=(xd-xs+1)*(yd-ys+1);
if(arie>amax){
amax=arie;cota=harta[xs][ys];}}

else

{	if((yd-ys+1)%2==0){

   int yu=(yd+ys)/2+1;
   int yde=(yd+ys)/2;


	pliaza(xs,yu,xd,yd);

     itoa(yu,u,10);
     itoa(yde,d,10);
     strcpy(aux,"O"); strcat(aux,u); strcat(aux,"U"); strcat(aux," ");
     strcat(aux,a[cota]); strcpy(a[cota],aux);

	pliaza(xs,ys,xd,yde);
}

	if((xd-xs+1)%2==0){

   int xr=(xd+xs)/2;
   int xl=(xd+xs)/2+1;


	pliaza(xs,ys,xr,yd);

      itoa(xr,r,10);
      itoa(xl,l,10);

	pliaza(xl,ys,xd,yd);

}}}



void main(){
clrscr();
int i=1,j=1;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>harta[i][j];

pliaza(1,1,m,n);
if(amax==-MAXINT)
cout<<"ghinion";
else
{cout<<"aria max="<<amax<<endl;
cout<<"cu cota="<<cota;}