4. Labyrinth, Backtracking+Ausgabe

Labyrinth, Backtracking+Ausgabe

  • B

    Hi.
    Ich habe ein Programm geschrieben, welches bei einem Labyrinth den Weg finden und dann ausgeben soll. Das Programm findet zwar alle Wege und bestätigt dies durch die Ausgabe von "Ziel!", aber bei der Ausgabe des Weges tut sich nichts.
    Ich habe beim hier vorliegenden Code alle Ansätze den Weg auszugeben entfernt, weil es sehr verworren war und zu nichts wirklich brauchbaren geführt hat.
    Über Lösungsansätze würde ich mich sehr freuen.
    Lg

    #include <stdio.h>

int find(char feld[4][4],unsigned int ,unsigned int);

int main(void)
{
	int i,j;
	unsigned int x=0,y=0;
	char feld[4][4];

        /*Labyrinth wird definiert(A=Anfang, E=Ende)*/

	feld[0][0]=feld[0][3]=feld[1][0]=feld[2][0]=feld[3][1]=feld[3][0]='*';
	feld[1][3]=feld[2][3]=feld[3][3]='*';
	feld[1][1]=feld[1][2]=feld[2][2]=feld[0][2]=feld[2][1]=' ';
	feld[0][1]='A';feld[3][2]='E';

        /*Labyrinth wird ausgegeben*/

	for(i=0; i<4;i++)
	{
		for(j=0;j<4;j++)
		{printf("%c ", feld[i][j]);
		}
	printf("\n");
	}

        /*Startfeld wird gesucht*/

	for(i=0; i<4;i++)
	{
		for(j=0;j<4;j++)
		{ if(feld[i][j]=='A') 
			{x=i; y=j;}
		}
	}

	printf("Startfeld: (%d %d)\n", x,y);

	find(feld,x,y);

return 0;
}

int find(char feld[4][4],unsigned int x,unsigned int y)
{

	if(feld[x][y]=='*')	{return 0;}
	if (feld[x][y]=='E') {printf("Ziel!\n");return 0;}
	if (feld[x][y]=='.') {return 0;}
	if ((feld[x][y]==' ') || (feld[x][y]=='A'))  
		{	 
			feld[x][y]='.';

			if (find(feld,x+1,y)) {return 1; }
			else if (find(feld,x-1,y)) {return 1; }
			else if (find(feld,x,y+1)) {return 1;}
			else if (find(feld,x,y-1)) {return 1;}
			else  {feld[x][y]=' '; return 0;}
		}

	else {return 0;}

}
    0
  • N

    Wahrscheinlich solltest du in Zeile 59 1 zurückgeben.

    0
  • B

    Wenn man in Zeile 59 eine 1 zurückgeben lässt, bricht er nach dem ersten weg ab. Das soll ja nicht so sein.
    Die Frage ist eher, wie man hier eine vernünftige Ausgabe des Weges erreicht.

    0
  • N

    Achso.

    Du müsstest wohl in jedem Punkt des Feldes speichern, aus welcher Richtung bzw. woher du in jedem Schritt gekommen bist. Wenn du dann das Ziel erreichst, kannst du damit den Weg rekonstruieren.

    Abgesehen davon würde ich es nicht rekursiv machen, weil dann bei größeren Feldern schnell der Stack überlaufen kann.

    0
  • B

    Kannst du mal genau sagen, wie du es machen würdest, oder wie ich was wo einbauen muss, damit es fkt.!?!

    0
  • N

    Na wenn du es sowieso rekursiv machst, kannst du die Information, wo du herkommst, auch einfach als lokale Variable speichern. Also

    struct path {
    int x, y;
    struct path *prev;
};

int find(char feld[4][4],unsigned int x,unsigned int y, struct path *prev)
{
    struct path p = {x, y, prev};

    /* ... */
    if (feld[x][y]=='E') {
        printf("Ziel! ");
        for (struct path *pp = &p; pp; pp = pp->prev)
            printf("(%d,%d)", pp->x, pp->y);
        printf("\n");
        return 0;
    }
    /* ... */
            if (find(feld,x+1,y, &p)) {return 1; }
            else if (find(feld,x-1,y, &p)) {return 1; }
            else if (find(feld,x,y+1, &p)) {return 1;}
            else if (find(feld,x,y-1, &p)) {return 1;}
    /* ... */
}

    Vom main aus rufst du es dann mit NULL auf.

    Allerdings wird der Weg damit in umgekehrter Reihenfolge ausgegeben.

    0
Anmelden zum Antworten