Labyrinth

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Labyrinth

    Hi

    ich brauche mal eure Hilfe so richitg funktioniert mein Backtracking Algorithmus nicht. Was is falsch ?


    Quellcode

    1. class Labyrinth{
    3. final static int[] STEPX = { 0, 1, 0,-1 };
    4. final static int[] STEPY = { -1, 0, 1, 0 };
    5. static int schritt;
    6. final static int OBEN = 0, RECHTS = 1, UNTEN = 2, LINKS = 3;
    7. static int aktX;
    8. static int aktY;
    10. static char[][] labyrinth = {
    11. {' ','x','x','x','x'},
    12. {' ',' ',' ','x','x'},
    13. {'x','x',' ',' ',' '},
    14. {'x',' ',' ','x',' '},
    15. {'x','x','x','x',' '}};
    17. static boolean findeWeg(char[][] lab, int i, int j){
    19. int n = lab.length;
    20. schritt = -1;
    22. while (schritt != LINKS) {
    23. schritt ++;
    24. int neuX = i + STEPX[schritt];
    25. int neuY = j + STEPY[schritt];
    27. boolean ok = true;
    29. if (neuX < 0 || neuX >= n) ok = false;
    30. if (neuY < 0 || neuY >= n) ok = false;
    31. if (ok && lab[neuX][neuY] !=' ') ok = false;
    33. if(ok){
    34. lab[neuX][neuY] = '.';
    36. if (findeWeg(lab, neuX, neuY)) {
    37. return true;
    38. } else {
    39. return false;
    40. }
    41. }
    42. }//while
    43. lab[i][j]= ' ';
    44. return false;
    47. }//findeWeg
    48. public static void zeige(char[][]a){
    50. for (int i = 0; i < a.length; i++) {
    51. for (int j = 0; j < a.length; j++) {
    52. System.out.print(a[i][j]+ " ");
    53. }
    54. System.out.println();
    56. }
    57. }
    59. public static void main (String[] args){
    60. zeige(labyrinth);
    61. boolean b = findeWeg(labyrinth, 0, 0);
    62. if (b) System.out.println("Weg gefunden");
    63. else System.out.println("Keinen Weg gefunden");
    64. zeige(labyrinth);
    65. }
    66. }// Klassenende
    Alles anzeigen

  • so ich habe den ausgang rechts unten gesetzt als zwischenlösung nur die schritte
    zurück klappen nicht :(

    Quellcode

    1. class Labyrinth{
    3. final static int[] STEPX = { 0, 1, 0,-1 };
    4. final static int[] STEPY = { -1, 0, 1, 0 };
    5. static int schritt;
    6. final static int OBEN = 0, RECHTS = 1, UNTEN = 2, LINKS = 3;
    7. static int aktX;
    8. static int aktY;
    10. static char[][] labyrinth = {
    11. {' ','x','x','x','x'},
    12. {' ',' ',' ','x','x'},
    13. {'x','x',' ',' ',' '},
    14. {'x',' ',' ','x',' '},
    15. {'x','x','x','x',' '}};
    17. static boolean findeWeg(char[][] lab, int i, int j){
    19. int n = lab.length;
    20. schritt = -1;
    21. zeige(lab);
    22. System.out.println("----");
    23. while (schritt != LINKS) {
    24. schritt ++;
    25. int neuX = i + STEPX[schritt];
    26. int neuY = j + STEPY[schritt];
    28. boolean ok = true;
    30. if (neuX < 0 || neuX >= n) ok = false;
    31. if (neuY < 0 || neuY >= n) ok = false;
    32. if (ok && lab[neuX][neuY] !=' ') ok = false;
    34. if(ok){
    35. lab[neuX][neuY] = '.';
    37. if (!ausgangGefunden(neuX, neuY)) {
    38. // rekursiver Aufruf von FindeLoesung
    39. if (findeWeg(lab, neuX, neuY)) {
    40. // Lösung gefunden
    41. return true;
    42. } else {
    43. lab[neuX][neuY] = ' ';
    44. }
    45. } else return true;
    46. }
    47. }//while
    48. return false;
    49. }
    52. private static boolean ausgangGefunden(int neuX, int neuY) {
    54. if(neuX==4 && neuY==4){
    55. return true;
    56. }
    57. return false;
    58. }
    61. public static void zeige(char[][]a){
    63. for (int i = 0; i < a.length; i++) {
    64. for (int j = 0; j < a.length; j++) {
    65. System.out.print(a[i][j]+ " ");
    66. }
    67. System.out.println();
    69. }
    70. }
    72. public static void main (String[] args){
    73. zeige(labyrinth);
    74. boolean b = findeWeg(labyrinth, 0, 0);
    75. if (b) System.out.println("Weg gefunden");
    76. else System.out.println("Keinen Weg gefunden");
    77. zeige(labyrinth);
    78. }
    79. }// Klassenende
    Alles anzeigen

  • Hehe wenn ich dir jetzt sage woran es liegt, schlägst du wahrscheinlich die Hände überm Kopf zusammen. Also soweit stimmt alle.
    Fangen wir aber erst mal bei was anderem an.
    Ich nörgele so gerne an anderer Leuten Code rum.
    Du solltest umbedingt aufhören, alles als static zu deklarieren und richtige Klassen schreiben. Soll heißen: ne eigene Klasse Labyrinth, mit verschiedenen Methoden und eine Klasse "Client" die das ganze ausführt.
    Solltest dir erst gar nicht angewöhnen alles als static zu deklarieren und direkt aufzurufen !!!!

    So nun zu deinen "Kleinigkeit"
    Wenn du ein "int" vor "schritt = -1" schreibst funktioniert es ;)

    Quellcode

    1. static boolean findeWeg(char[][] lab, int i, int j){
    2. int n = lab.length;
    3. int schritt = -1;
    4. ...


    Du verwendest nur EINE Variable, anstatt für jeden rekursiven Aufruf eine eigene.

    mfg
    Ubuntu Edgy * Kernel 2.6.17 * Gnome 2.16 * Beryl
    2 x Athlon MP 1900 * MSI K7D Master-L * 1024 MB ECC DDR333
    Hercules 9800XT 256 MB Ram * 1x 250 GB IDE
    Wasserkühlung