Ein Feld mit Ecksteinen pflastern - Divide&Conquer

[Cherrycoke]

Hallo Community,

ich komme mit meinen Aufgaben einfach nicht weiter. An folgender Aufgabe sitze ich schon seit heute morgen:

Gegeben ist ein quadrtisches Feld der Seitenlänge 2^k. Auf diesem Feld wird nun an beliebiger Stelle ein Stein platziert. Nun soll das Feld mit Ecksteinen der Größe drei gefüllt werden.

Beispiel für k = 2 und Startstein auf 1, 1:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

2 2 0 0
2 1 0 0
0 0 0 0
0 0 0 0

2 2 0 0
2 1 3 0
0 3 3 0
0 0 0 0

2 2 4 4
2 1 3 4
0 3 3 0
0 0 0 0

usw.

Bisher habe ich folgenden kleinen Algorithmus:

//Startstück suchen:
Wenn Teilstück Startstück enthält:
  Solange Feldgröße > 2x2
	pflastern(Quadrant1);
	pflastern(Quadrant2);
	pflastern(Quadrant3);
	pflastern(Quadrant4);
Quadrant mit dem Startstück fertig pflastern;
Einen Eckstein in die Mitte setzen, der jeweils einen Stein in jedem der uebrigen Quadranten hat;

Mein Programm sieht bisher so aus:

#include <stdio.h>
#include <stdlib.h>

int globalcount;

void feld_ausgeben(int **feld, int n)
{
  int i, j;
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      printf(" %3d ",feld[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}


/* Funktion zur rekursiven Pflasterung des Feldes:                             
 x y gibt die Lage des einzelnen Steines im aktuell betrachteten Teilfeld an, 
das durch mini, maxi, minj und maxj begrenzt wird. Die Pflasterung soll ueberpruefen
in welchem Quadranten sich der einzelne Stein befinden, dann in diesem Quadranten 
die Pflasterung fortsetzen, einen Eckstein in die Mitte setzen, der jeweils einen Stein 
in jedem der uebrigen Quadranten hat und dann mit diesem neuen Einzelstein die Pflasterung
in den anderen Quadranten fortsetzen. Verwenden Sie die lokale Kopie der globalen Variable 
actglobalcount, um die Ecksteine im Feld zu markieren */

void pflastern(int mini, int maxi, int minj, int maxj, int **feld, int x, int y)
{
  int actglobalcount = globalcount;
	int n = maxi+1;
	int h = 0;
	int i,j;

  globalcount++;

  /* Fortsetzen der Pflasterung */
  /* Noch zu implementieren! */


	/* Wenn sich das Startstück in diesem Teilstück befindet setze h == 1 */
	for( i = mini; i <= maxi; i++ ){
		for( j = minj; j <= maxj; j++){
			if( feld[i][j] == 1){
				h = 1;
			}
			else{

			}
		}
	}

	if( h == 1 ){
		if( n > 2){
			pflastern(0,(n/2)-1, 0,(n/2)-1,feld,x,y);
			pflastern(0,(n/2)-1, (n/2),n-1,feld,x,y);
			pflastern(n/2,n-1, 0,(n/2)-1,feld,x,y);
			pflastern(n/2,n-1, (n/2),n-1,feld,x,y);
		}
		else{
		/* Startquadranten belegen */
			for( i = mini; i <= maxi; i++){
				for( j = minj; j <= maxj; j++){
					if( feld[i][j] == 0){
						feld[i][j] = 2;
					}
				}
			}
		}
	}

}

int main(int argc, char *argv[])
{
  int **feld;
  int i, n;
  int x, y;

  globalcount++;

  printf("Bitte geben Sie n ein: ");
  scanf("%d",&n);

  feld = (int**) calloc(n,sizeof(int*));
  for(i=0;i<n;i++){
    feld[i] = (int*) calloc(n,sizeof(int));
  }

  printf("Bitte geben Sie die Koordinaten des Startsteins an: ");
  scanf("%d %d", &x, &y);
  
  feld[x][y] = globalcount;
  globalcount++;
  
  pflastern(0,n-1,0,n-1,feld,x,y);

  feld_ausgeben(feld,n);

  free(feld);

  return 0;
}

Ich tüftel nun schon den ganzen Tag, wie ich den neuen Eckstein richtig setzen kann, um mit der Pflasterung fortzusetzen.

Hat da jemand eine Idee oder einen kleinen Tipp? Wäre wirklich super!

 

[Vereth]

Wenn pflastern einen 2*2-Quadranten zu füllen hat, dann belegst du die restlichen freien Felder mit dem übergebenen Wert und kehrst zurück.
Wenn du einen größeren Quadranten zu bearbeiten hast, dann musst du als erstes den Teil-Quadranten rekursiv pflastern, in dem ein Stein ist; anschließend ist dieser Quadrant vollständig gefüllt. Anschließend platzierst du den neuen Eckstein so in der Mitte, dass den nunmehr gepflasterten Quadranten umschließt. Für die drei verbleibenden Quadranten rufst du dann wieder die die pflastern-Funktion mit den jeweiligen Parametern auf.
Das schon belegte Feld eines Quadranten ist immer in einer der äußeren 4 Ecken; nur beim Startstein gilt das nicht, aber dessen Position ist ja bekannt.

 

[Cherrycoke]

Wenn pflastern einen 2*2-Quadranten zu füllen hat, dann belegst du die restlichen freien Felder mit dem übergebenen Wert und kehrst zurück.
Wenn du einen größeren Quadranten zu bearbeiten hast, dann musst du als erstes den Teil-Quadranten rekursiv pflastern, in dem ein Stein ist; anschließend ist dieser Quadrant vollständig gefüllt. Anschließend platzierst du den neuen Eckstein so in der Mitte, dass den nunmehr gepflasterten Quadranten umschließt. Für die drei verbleibenden Quadranten rufst du dann wieder die die pflastern-Funktion mit den jeweiligen Parametern auf.
Das schon belegte Feld eines Quadranten ist immer in einer der äußeren 4 Ecken; nur beim Startstein gilt das nicht, aber dessen Position ist ja bekannt.

Auf dm Blatt kann ich diesen Algorithmus für mich problemlos durchführen. Allerdings habe ich eher ein Problem ihn zu implemntieren. Ich scheitere an der Stelle, an der ein neuer Eckstein gesetzt werden soll. Wie setze ich Einen gültigen Eckstein, der in den drei anderen Quadranten liegt?

 

[Vereth]

Anschließend platzierst du den neuen Eckstein so in der Mitte, dass den nunmehr gepflasterten Quadranten umschließt.

int x0 = mini + (maxi-mini)/2;
int y0 = minj + (maxj-minj)/2;
int gc = actglobalcount++;
if ( feld[x0+0][y0+0] == 0 )  
{ feld[x0+0][y0+0] = gc; pflastern(mini,x0+0,minj,y0+0,feld,x0+0,y0+0); }
if ( feld[x0+0][y0+1] == 0 ) 
{ feld[x0+0][y0+1] = gc; pflastern(mini,x0+0,y0+1,maxj,feld,x0+0,y0+1); }
if ( feld[x0+1][y0+0] == 0 ) 
{ feld[x0+1][y0+0] = gc; pflastern(x0+1,maxi,minj,y0+0,feld,x0+1,y0+0); }
if ( feld[x0+1][y0+1] == 0 ) 
{ feld[x0+1][y0+1] = gc; pflastern(x0+1,maxi,y0+1,maxj,feld,x0+1,y0+1); }

 

[Cherrycoke]

So sieht mein Programm zur Zeit aus:

void pflastern(int mini, int maxi, int minj, int maxj, int **feld, int x, int y)
{
  int actglobalcount = globalcount;
  int n = maxi+1;
  int i, j;
  int quadrant = 1;
  int q1mini, q1maxi, q1minj, q1maxj;
  int q2mini, q2maxi, q2minj, q2maxj;
  int weiter = 0;


  globalcount++;

  /* Fortsetzen der Pflasterung */


  /* Es handelt sich um ein 2x2 Feld */
  if( n == 2 ){
	 
	  /* Vervollständigt das Feld */
	  for( i = 0; i < n; i++){
		  for( j = 0; j < n; j++){
			  if( feld[i][j] == 0){
				  feld[i][j] = 2;
			  }
		  }
	  }

	  return;

  }
  /* Es handelt sich um ein Feld größer als 2x2 */
  else{
	  /* Teile Feld in 4 Quadranten */
	  /* Wiederhole solange, bis Feld Größe 2x2 */
	  while( n != 2 ){

		  if( weiter == 0){
			  weiter = 0;
			  quadrant = 1;

			  /* Quadrant 1 */
			  q1mini = mini;
			  q1maxi = (n/2);
			  q1minj = minj;
			  q1maxj = (n/2);

			  for( i = q1mini; i < q1maxi; i++ ){
				  for( j = q1minj; j < q1maxj; j++){
					  if( feld[i][j] == 1 ){
						mini = q1mini;
						maxi = q1maxi;
						minj = q1minj;
						maxj = q1maxj;
						n = q1maxi;
						weiter = weiter + feld[i][j];
					  }
				  }
			  }
		  }

		  if( weiter == 0){
			printf("Checkpoint");
			  quadrant = 2;
			  /* Quadrant 2 */
			  q2mini = mini;
			  q2maxi = (maxi/2)-1;
			  q2minj = maxj/2;
			  q2maxj = maxj-1;

			  for( i = q2mini; i < q2maxi; i++ ){
				  for( j = q2minj; j < q2maxj; j++){
					  if( feld[i][j] == 1 ){
						mini = q2mini;
						maxi = q2maxi;
						minj = q2minj;
						maxj = q2maxj;
						n = q2maxi;
						weiter = weiter + feld[i][j];
					  }
				  }
			  }


		  }

	  }
	  
	  /* Pflasterung vervollständigen !testweise nur mit 3 füllen*/
	  for( i = mini; i < maxi; i++){
		  for( j = minj; j < maxj; j++){
			  if( feld[i][j] == 0 || feld[i][j] == 1 ){
				  feld[i][j] = 3;
			  }
		  }
	  }

	  /* Neuen Startstein legen !unfertig */
	  switch(quadrant){
		case 1:
			feld[maxi][maxi] = 1;
			feld[maxi][maxi-1] = 1;
			feld[maxi-1][maxi] = 1;
	  }

	  pflastern(0,n-1,0,n-1,feld,x,y);

  }
}

Es funktioniert schon einmal, wenn der Startstein ganz rechts oben liegt, da im Moment auch nur der erste Quadrant überprüft wird. Im nächsten Schritt wollte ich den zweiten Quadranten überprüfen lassen. Allerdings bekomme ich es nicht hin, dass der zweite Quadrant richtig überprüft wird. Mit dm obigen Quellcode müsste doch bereits zum Beispiel für die Koordinate (0, 2) auf einm 4x4 Feld ein Ergebnis liefern.
Allerdings gerät er in eine Endlosschleife (Zeile 63), und ich komme einfach nicht drauf warum.

Kann mir jemand weiterhelfen?

 

[Vereth]

Das sukzessive Aufteilen in immer kleinere Quadranten geschieht per Rekursion, du brauchst also keine umständliche Schleifenkonstruktion.

/* Hilfsvariablen setzen */
int x0 = mini + (maxi-mini)/2;
int y0 = minj + (maxj-minj)/2;
/* Quadrant mit Vorgabestein ermitteln und pflastern */
if ( x <= x0 && y <= y0 ) { pflastern(mini,x0+0,minj,y0+0,feld,x,y); }
if ( x <= x0 && y >  y0 ) { pflastern(mini,x0+0,y0+1,maxj,feld,x,y); }
if ( x >  x0 && y <= y0 ) { pflastern(x0+1,maxi,minj,y0+0,feld,x,y); }
if ( x >  x0 && y >  y0 ) { pflastern(x0+1,maxi,y0+1,maxj,feld,x,y); }
/* Eckstein setzen und restliche Quadranten pflastern */
int gc = actglobalcount++;
if ( feld[x0+0][y0+0] == 0 )  
{ feld[x0+0][y0+0] = gc; pflastern(mini,x0+0,minj,y0+0,feld,x0+0,y0+0); }
if ( feld[x0+0][y0+1] == 0 )
{ feld[x0+0][y0+1] = gc; pflastern(mini,x0+0,y0+1,maxj,feld,x0+0,y0+1); }
if ( feld[x0+1][y0+0] == 0 )
{ feld[x0+1][y0+0] = gc; pflastern(x0+1,maxi,minj,y0+0,feld,x0+1,y0+0); }
if ( feld[x0+1][y0+1] == 0 )
{ feld[x0+1][y0+1] = gc; pflastern(x0+1,maxi,y0+1,maxj,feld,x0+1,y0+1); }