Θέλω συμβουλή σε αλγόριθμο σε JAVA

[SteamPunk9000]

Θέλω να βρω την βέλτιστη διαδρομή από το [0][0] στο [ν-1][ν-1] σε έναν boolean πίνακα με false τιμή στα εμπόδια. Θέλω να το υλοποιήσω με ουρά(FIFO) και έχω φτιάξει μέχρι στιγμής το εξής:

 

  import java.util.*;

/**

 * Κλάση για τον υπολογισμό της 

 * βέλτιστης διαδρομής σε μία μάζα

 * Δέχεται έναν boolean [n][n] maza με true στις 

 * επιτρεπτές θέσεις και false στα εμπόδια και int n

 * το μέγεθος του πίνακα.

 * 

 */

public class cheese {

    public static int min_steps(boolean [][] maza, int n) {    

        int [][] oura = new int [n^2][3];

        int f = 0;

        int r = 0;

        oura[f][0] = 0;// grammes tou pinaka

        oura[f][1] = 0;// steiles tou pinaka

        oura[f][2] = 0;// to kostos +1 gia kathe vima

        r = (r+1)%(n^2);

        int i = 0;

        int steps;// krataei to teliko kostos  

        int temp;

        do

        {

            /**

             * Metakinisi pros ta deksia ston pinaka

             */

            if(maza[oura[0]+1][oura[1]])

            {

              oura[r][0] = oura[0]+1;

              oura[r][1] = oura[1];

              oura[r][2] = oura[2]+1;

              r = (r+1)%(n^2);

            }

            /**

             * Metakinisi pros ta katw ston pinaka

             */

            if(maza[oura[0]][oura[1]+1])

            {

                oura[r][0] = oura[0];

                oura[r][1] = oura[1]+1;

                oura[r][2] = oura[2]+1;

                r = (r+1)%(n^2);

            }

            /**

             * Metakinisi pros ta

             */

            if(i>0)

            {

             /**

             * Metakinisi pros ta panw ston pinaka

             */

              if(oura[0]>0 && maza[oura[0]-1][oura[1]])

              {

                oura[r][0] = oura[0]-1;

                oura[r][1] = oura[1];

                oura[r][2] = oura[2]+1;

                r = (r+1)%(n^2);

              }

              /**

               * Metakinisi pros ta aristera ston pinaka

               */

              if(oura[1]>0 && maza[oura[0]][oura[1]-1])

              {  

                oura[r][0] = oura[0];

                oura[r][1] = oura[1]-1;

                oura[r][2] = oura[2]+1;

                r = (r+1)%(n^2);

              }

            }

  

            steps = oura[2];

            temp = oura[0];

            /** 

             * Διαγραφή του πρώτου στοιχείου

             */

            oura[f][0] = -1;

            oura[f][1] = -1;

            oura[f][2] = -1;

            f = (f+1)%(n^2);

            i++;

        }

        while(f!=r);

        if (temp<n-1)

            return 0;

        else

        {

             return steps;

            }

   }

}

 

Μου βγάζει java.lang.ArrayIndexOutOfBoundsException

 

 Οποιαδήποτε βοήθεια θα είναι χρήσιμη!

Ευχαριστώ εκ των προτέρων!

[NickSym]

Πες μας και που στο βγάζει ρε μαν !

[defacer]

Δε μπαίνω στον κόπο να προσπαθήσω να βγάλω άκρη ώς έχουν τα πράγματα γιατί ο κώδικας είναι αρκετά δυσκολοδιάβαστος. Μερικά τυχαία σχόλια:

 

1. Το ^ δεν κάνει αυτό που νομίζεις οτι κάνει, οπότε δεν πρόκειται να σου δουλέψει έτσι κι αλλιώς. Για την ακρίβεια το ^ μέσα στο new του πίνακα είναι τουλάχιστον μέρος του προβλήματος που έχεις.

 

2. Υπάρχουν σημεία όπου κάνεις calculated array accesses π.χ. maza[oura[0]+1] χωρίς να μπεις στον κόπο να ελέγξεις αν το oura[0]+1 είναι μέσα στο length του πίνακα. Γιατί;

[nilosgr]

Το n^2 δεν υψωνει σε δυναμη, δοκιμασε n*n

[kaliakman]

Ερώτηση: Σίγουρα είναι μάζα και όχι maze (= λαβύρινθος; ) ;

Επίσης τι αλγόριθμο προσπάθεις να χρησιμοποιήσεις;

 

Υ.Γ. Γιατί δεν χρησιμοποιείς την Queue της Java;

 

https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

[SteamPunk9000]

Το σφάλμα μου το έβγαζε στο   if( maza[oura[0]+1][oura[1]]) είναι το πρώτο if μέσα στην do-while, αλλά το ξεπέρασα αλλάζοντας το n^2 με n*n στη δήλωση του πίνακα.

 

Επίσης τσεκάρω αν το oura[0]+1 είναι εντός του πίνακα ως εξής 

if (oura[0] < n && maza[[0]+1][oura[1]]) και στα υπόλοιπα if αντίστοιχα.

Φυσικά ακόμα μου βγάζει μόνο 0 ως λύση συνέχεια, αλλά που θα πάει θα το βρω.

 

Η μάζα είναι όντως ένας λαβύρινθος και είχα σκεφτεί να το υλοποιήσω με LinkedList αλλά επειδή θέλω να κρατάω ένα triplet με τις συντεταγμένες του λαβυρίνθου(πίνακα maza) και το κόστος βήματος δηλ. (γραμμή, στήλη,κόστος) και δεν ξέρω πως μπορώ αλλιώς να προχωράω μέσα στον λαβύρινθο. Είχα σκεφτεί το εξής loop 

 

 LinkedList List = new LinkedList();

int k = 0;

 for(int i=0;i<n;i++){

          for(int j=0;j<=i;j++){

            System.out.print(maza[ i-j ][ j ]); // Έλεγχος των στοιχείων που εξετάζω κάθε φορά 

            if (maza[ i-j ][ j ]){

                List.addLast(k);

          }

        System.out.println("  ");

       k++;

}

 

αλλά μπορώ να φτάσω έτσι μέχρι την διαγώνιο, στα μέσα του πίνακα και μου μένει ο άλλος μισός πίνακας. Επίσης επειδή ασχολούμαι για διδακτικούς λόγους σκέφτηκα η υλοποίηση με πίνακα ίσως είναι για μένα καλύτερη.

[SteamPunk9000]

Μετά από κάποιες διορθώσεις ο αλγόριθμός μου φαίνεται να δουλεύει, εκτός από το εξής: όταν φτάνει στο [n-1][n-1] σημείο πάει και εισάγει στην ουρά τα προηγούμενα σημεία από τα οποία έχει ήδη περάσει. Μπορεί κάποιος να μου δώσει καμιά ιδέα πως θα διαχειριστώ αυτά τα πισωγυρίσματα;

Σημείωση: η υλοποίηση της ουράς είναι με πίνακα όπως το ξεκίνησα.  

 

Επίσης σε ένα site βρήκα αυτήν την υλοποίηση του προβλήματος:

public void visit(String []map , Point start){

   int []x = {0,0,1,-1};//This represent 4 directions right, left, down , up
   int []y = {1,-1,0,0};
   LinkedList<Point> q = new LinkedList(); 
   q.add(start);
   int n = map.length;
   int m = map[0].length();
   int[][]dist = new int[n][m];
   for(int []a : dist){
       Arrays.fill(a,-1);
   }
   dist[start.x][start.y] = 0;
   while(!q.isEmpty()){
       Point p = q.removeFirst();
       for(int i = 0; i < 4; i++){
            int a = p.x + x[i];
            int b = p.y + y[i];
            if(a >= 0 && b >= 0 && a < n && b < m && dist[a][b] == -1 && map[a].charAt(b) != '*' ){
                  dist[a][b] = 1 + dist[p.x][p.y];
                  q.add(new Point(a,b));
             }
        }
     }
}

 

Και θα ήθελα αν είναι δυνατόν να μου εξηγήσει κάποιος τι ρόλο παίζει η 

  for(int []a : dist){

       Arrays.fill(a,-1);
   }

Επεξ/σία 23 Ιανουαρίου 2017 από SteamPunk9000

[tsofras]

 

Και θα ήθελα αν είναι δυνατόν να μου εξηγήσει κάποιος τι ρόλο παίζει η 

  for(int []a : dist){

       Arrays.fill(a,-1);

   }

 

Εσύ δεν το έγραψες ?

[Aztec]

 

Και θα ήθελα αν είναι δυνατόν να μου εξηγήσει κάποιος τι ρόλο παίζει η 

  for(int []a : dist){

       Arrays.fill(a,-1);

   }

 

για να καταλάβεις κάποιες φορές τι κάνει ενα κομμάτι κώδικα φτιάχνεις ενα προγραμματάκι που τσεκάρει μόνο αυτό.

Ας πουμε πες οτι εγω δεν ήξερα η δεν ήμουν σίγουρος τι κάνει . Θα έφτιαχνα ενα προγραμματάκι όπως το ακόλουθο

 

 int[][] dist = new int[2][2];
 System.out.println("Before");

 for (int k = 0; k < 2; k++) {
    for (int m = 0; m < 2; m++) {
         System.out.println(dist[k][m]);
    }
 }

  for (int[] a : dist) {
      Arrays.fill(a, -1);
  }
 System.out.println("After");
 for (int k = 0; k < 2; k++) {
       for (int m = 0; m < 2; m++) {
           System.out.println(dist[k][m]);
       }
  }

το οποίο δίνει result

 

Before

0

0

0

0

After

-1

-1

-1

-1

 

 

και άρα συμπεραίνεις οτι κατι initlization τα στοιχεια στο multidimensional array dist  σε -1