Problem beim Labyrinthlöser
-
Guten Tag
Wir sollen gerade in der Schule einen Labyrinthlöser programmieren. Soweit habe ich den fertig, nur, funktioniert das Backtracking nicht einwandfrei, d.h. er löscht wenn er einen falschen Weg findet das Wegsymbol '@' nicht immer. (nach vielem rumprobieren viel mir auf, dass er nicht um die Ecke löscht)
Kann mir eventuell jemand da helfen? Wäre nettCode der Rekursion:
Zur Erklärung: Die Ausgänge werden vorher mit A/65 markiert, somit überprüft er zunächst ob ein Ausgang in Reichweite ist.int Rekursion ( int i, int j){ if ((Feld[i][j+1] == 65) || (Feld[i][j-1] == 65) || (Feld [i+1][j] == 65) || (Feld[i-1][j] == 65)){ printf("\n"); Ausgabe(); } if (Feld[i-1][j] == 32){ Feld[i-1][j] = '@'; Rekursion(i-1,j); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i-1][j] = 32; Feld[i][j] = 32; } } // else { if (Feld[i+1][j] == 32){ Feld[i+1][j] = '@'; Rekursion(i+1,j); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i+1][j] = 32; Feld[i][j] = 32; } } // else { if (Feld[i][j-1] == 32){ Feld[i][j-1] = '@'; Rekursion(i,j-1); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i][j-1] = 32; Feld[i][j] = 32; } } // else { if (Feld[i][j+1] == 32){ Feld[i][j+1] = '@'; Rekursion(i,j+1); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i][j+1] = 32; Feld[i][j] = 32; } } return 0; }Ganzer Code:
#include <stdio.h> #include <stdlib.h> int Feld[45][60]; int xmax=0; int ymax=0; int counter=0; int Einlesen(); int Ausgabe(); int Exit(); int Start(); int Rekursion(int i, int j); int Einlesen(){ FILE *F; int x, y, z; counter = 0; x = 0; y = 0; F = fopen ("eingabe.txt", "r"); while(z != -1){ z = fgetc(F); if (z != -1){ Feld[x][y] = z; if(/*(z != -1)&&*/(z != 10)) counter++; x++; if (z == 10){ xmax = x-2; x = 0; y++; } // if (z == 10) } //if } // while // ymax = y-1; ymax = y; return 0; } //main int Ausgabe(){ int i, x, y; x=0; y=0; for (i=0; i<counter; i++){ printf("%c", Feld[x][y]); x++; if (Feld[x][y]== 10){ printf ("\n"); x=0; y++; } } return 0; } int Exit(){ int x, y; for(y=0; y<=ymax; y++){ if (Feld[xmax][y] == 32) Feld[xmax][y] = 65; } for(x=0; x<=xmax; x++){ if (Feld[x][ymax] == 32) Feld[x][ymax] = 65; } for(y=0; y<=ymax; y++){ if (Feld[0][y] == 32) Feld[0][y] = 65; } for(x=0; x<=xmax; x++){ if (Feld[x][0] == 32) Feld[x][0] = 65; } } int Start(){ int i=0,j=0; while (Feld[i][j] != 69){ if (i == ymax){ j++; i=0;} else i++; } // printf("Startfeld: %d, %d \n", i,j); if (i == 0){ Feld[++i][j] = '@'; Rekursion(i,j); } if (i == ymax){ Feld[--i][j] = '@'; Rekursion(i,j); } if (j == 0){ Feld[i][++j] = '@'; Rekursion(i,j); } if (j == xmax){ Feld[i][--j] = '@'; Rekursion(i,j); } return 0; } int Rekursion ( int i, int j){ if ((Feld[i][j+1] == 65) || (Feld[i][j-1] == 65) || (Feld [i+1][j] == 65) || (Feld[i-1][j] == 65)){ printf("\n"); Ausgabe(); } if (Feld[i-1][j] == 32){ Feld[i-1][j] = '@'; Rekursion(i-1,j); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i-1][j] = 32; Feld[i][j] = 32; } } // else { if (Feld[i+1][j] == 32){ Feld[i+1][j] = '@'; Rekursion(i+1,j); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i+1][j] = 32; Feld[i][j] = 32; } } // else { if (Feld[i][j-1] == 32){ Feld[i][j-1] = '@'; Rekursion(i,j-1); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i][j-1] = 32; Feld[i][j] = 32; } } // else { if (Feld[i][j+1] == 32){ Feld[i][j+1] = '@'; Rekursion(i,j+1); if ((Feld[i][j+1] != 32) && (Feld[i][j-1] != 32) && (Feld [i+1][j] != 32) && (Feld[i-1][j] != 32)){ Feld[i][j+1] = 32; Feld[i][j] = 32; } } return 0; } int main(){ Einlesen(); Exit(); Start(); // Ausgabe(); printf ("\n\n %d, %d", xmax, ymax); return 0; }
-
Hi,
offtopic: ich hab vorhin fuer einen genau das gleiche Programm geschrieben. In welcher Schule seit ihr? Weil auf die frage obs fuer die Schule waere hat er gemeitn nein
-
fürn technisches Gymnasium, aber das is wirklich off topic ^^
Wäre nett wenn jemand oder vllt. du uns helfen könntest, wir wollen ja nich, dass jemand das für uns schreibt. Wir hängen nur an dieser einen Stelle...
Alles andere is kein Problem (Einlesen, Ausgeben etc.)
-
ok hier mal das was ich im FindWay geschrieben hab:
void FindWay(int Col, int Row) { Mark( Col, Row, WALKED_CHAR); if( IsEdge( Col, Row) ) { g_Ways++; g_End = clock(); ShowMaze(); printf("took %d milli seconds to find the way\n\n", g_End - g_Start); g_Start = clock(); } else { if( g_Maze[Row-1][Col] == FREE_CHAR) FindWay(Col, Row-1); if( g_Maze[Row][Col-1] == FREE_CHAR) FindWay(Col-1, Row); if( g_Maze[Row+1][Col] == FREE_CHAR) FindWay(Col, Row+1); if( g_Maze[Row][Col+1] == FREE_CHAR) FindWay(Col+1, Row); } Mark( Col, Row, FREE_CHAR); }berueht auf folgenden Artikel: Backtracking
-
Ich hab deinen Algorithmus mal in mein Labyrinth eingebaut
Problem ist jetzt aber, er findet nur 5 von möglichen 6 WegenDein Algorithmus umgemodelt (variblen etc. angepasst)
int Rekursion ( int i, int j){ Feld[i][j] = '@'; if ((Feld[i][j+1] == 65) || (Feld[i][j-1] == 65) || (Feld [i+1][j] == 65) || (Feld[i-1][j] == 65)){ printf("\n"); Ausgabe(); } else { if (Feld[i-1][j] == 32){ Rekursion(i-1,j); } // else { // else { if (Feld[i][j-1] == 32){ Rekursion(i,j-1); } // else { if (Feld[i][j+1] == 32){ Rekursion(i,j+1); } if (Feld[i+1][j] == 32){ Rekursion(i+1,j); } } Feld[i][j] = 32; return 0; }joa er findet nun leider eben nicht alle. Weißt du worans liegen könnte.
Er übergeht einen Ausgang nämlich komplett ^^
-
Meinst du vielleicht das hier:
------------ test header text ------------ Found entry at: 1 / 1 Found 3 exits .................... E@@ . . ... ..@. . . . ... ..... .@@. . . . .. . .@.. ....... . . . .@.. . . . .@............ ..... .@@ . ... . . ..@. ... ... ... . . .@@. ... . .@............. .... .@@@@@ . . . . ...@. . . ...... . . .@@@. . . ...@. ....... ...... took 0 milli seconds to find the way .................... E@@ . . ... ..@. . . . ... ..... .@@. . . . .. . .@.. ....... . . . .@.. . . . .@............ ..... .@@ . ... . . ..@. ... ... ... . . .@@. ... . .@............. .... .@@@@@ . . . . ...@. . . ...... . . . @. . . ... .@....... ...... took 0 milli seconds to find the way .................... E@@@@ . .@@@@@ ... .. .@. . .@...@..... . .@. .@@@.@ .. . . ..@.......@.@ . . . ..@@@@@@@@@.@. . . ............@..... . . ...@@@. . .. . ... ... ...@. . . . ... @@ . . .............@.... . . .@@@@@ . . ... . . .@...... . . . . .@@@ . ... . .......@...... took 0 milli seconds to find the way .................... E@@@@ . .@@@@@ ... .. .@. . .@...@..... . .@. .@@@.@ .. . . ..@.......@.@ . . . ..@@@@@@@@@.@. . . ............@..... . . ...@@@. . .. . ... ... ...@. . . . ... @@ . . .............@.... . . . @@@@. . ... . . . ......@. . . . . @@@@@@. ... . .......@...... took 0 milli seconds to find the way .................... E@@@@ . .@@@@@ ... .. .@. . .@...@..... . .@. .@@@.@@.. . . ..@.......@.@@ . . . ..@@@@@@@@@.@. . . ............@..... . . ...@@@. . .. . ... ... ...@. . . . ... @@ . . .............@.... . . .@@@@@ . . ... . . .@...... . . . . .@@@ . ... . .......@...... took 0 milli seconds to find the way .................... E@@@@ . .@@@@@ ... .. .@. . .@...@..... . .@. .@@@.@@.. . . ..@.......@.@@ . . . ..@@@@@@@@@.@. . . ............@..... . . ...@@@. . .. . ... ... ...@. . . . ... @@ . . .............@.... . . . @@@@. . ... . . . ......@. . . . . @@@@@@. ... . .......@...... took 0 milli seconds to find the way found 6 ways for the maze
muss ehrlich sagen hab keine lust mich in dein Programm einzuarbeiten. Sorry bleibt dir wohl nix andres uebrig als zu debuggen.
Gruss
€ beim zweiten hab ich 7837 moegliche Wege