Java permeability

Asked

Viewed 216 times

1

I’m having some difficulty solving a recursive problem, which I explain below.

Given an array of n rows and columns, check for permeability, i.e., having the following matrix (where '*' - represents open node and '-' - represents closed node):

  0 1 2 3 4 5
0 - - - - * -
1 - - - - * -
2 - - - * * -
3 - - - * - -
4 - - - * * -
5 - - - - * -

Check if there is an open node path from line 0 to line 5. In this case, the problem is reduced to whether there is an open node on the last line that can be connected to an open node on the first line through neighboring open nodes (the top, the bottom, the right and the left).

After many attempts I’m not getting there, especially because recursiveness has to be used.

  • 4

    Depois de muitas tentativas não estou a conseguir chegar lá. Could you show us some of your attempts and what prevented you from getting there?

  • Is your question about how recursion works or about the same algorithm? As @Math has already mentioned, if you’ve tried some algorithm, it might be interesting to put at least your most promising attempt into the question.

  • Another question: will your configuration always be so "simple"? I mean, if there is a possible path, it will always be unique?

1 answer

1


Directions were adopted in the matrix as forward, back or down.

Forward: when the index n is incremented;

Back: when the index n is decremented;

Down: when the index m is incremented.

  0 1 2 3 4 5 n
0 - - - - * -
1 - - - - * -
2 - - - * * -
3 - - - * - -
4 - - - * * -
5 - - - - * -
m

As a convention we will adopt that the problem is translated into a matrix m X n and that open nodes have value 1 and the closed nodes have value 0, being like this:

  0 1 2 3 4 5 n
0 0 0 0 0 1 0
1 0 0 0 0 1 0
2 0 0 0 1 1 0
3 0 0 0 1 0 0
4 0 0 0 1 1 0
5 0 0 0 0 1 0
m

Taking into account that the path to be searched starts down the matrix, first we search for an open node in the vector m = 0, being found the position m = 0 and n = 4

  0 1 2 3 4 5 n
0 0 0 0 0 1 0
m

Chunk of Java code:

//matriz
int[][] _matrix = new int[6][6];
_matrix[0] = new int[]{0,0,0,0,1,0};
_matrix[1] = new int[]{0,0,0,0,1,0};
_matrix[2] = new int[]{0,0,0,1,1,0};
_matrix[3] = new int[]{0,0,0,1,0,0};
_matrix[4] = new int[]{0,0,0,1,1,0};
_matrix[5] = new int[]{0,0,0,0,1,0};

//procurando a primeira posição aberta
int _m = 0;
for(int _n = 0; _n < _matrix[_m].length; _n++){
    int _value = _matrix[_m][_n];
    if(_value == 1){
        System.out.println("start m = " + _m + " n = " + _n);

        /* chamada ao método recursivo, passando os índices m e n do nó aberto
         * passando também valores negativos nos argumentos mm e nn, 
         * indicando que ainda não há nó anteriormente visitado
         */
        neighbour(_matrix, _m, _n, -1, -1);

        break;//não buscar outra posição aberta
    }
}

From then on, the recursive search comes into action, since you want to descend the matrix in search of the path with open nodes.

In this snippet of Java code we have the method that explores the neighborhood of a given matrix position, note that it takes 5 arguments:

Matrix: the matrix;

m: position m where the open node is;

n: position n where the open node is located;

mm: position m of the previous open node;

nn: position n of the previous open node.

mm and nn are needed to control who has already been visited, thus avoiding an infinite recursion.

public static void neighbour(int[][] matrix, int m, int n, int mm, int nn){

    int _n = n - 1;
    if(_n >= 0 && _n != nn){//para não estourar o índice e não seja um nó já visitado
        if(1== matrix[m][_n]){
            //para traz
            System.out.println("      m = " + m + " n = " + _n);
            neighbour(matrix, m, _n, -1, n);
        }
    }

    int _m = m + 1;
    if(_m < matrix.length && _m != mm){//para não estourar o índice e não seja um nó já visitado
        if(1== matrix[_m][n]){
            //para baixo
            System.out.println("      m = " + _m + " n = " + n);
            neighbour(matrix, _m, n, m, -1);
        }
    }

    _n = n + 1;
    if(_n < matrix[m].length && _n != nn){//para não estourar o índice e não seja um nó já visitado
        if(1== matrix[m][_n]){
            //para frente
            System.out.println("      m = " + m + " n = " + _n);
             neighbour(matrix, m, _n, -1, n);
        }
    }

    //não explora para cima, pois queremos "descer" na matriz
}

As a result:

start m = 0 n = 4
      m = 1 n = 4
      m = 2 n = 4
      m = 2 n = 3
      m = 3 n = 3
      m = 4 n = 3
      m = 4 n = 4
      m = 5 n = 4

Using the matrix with the configuration below:

_matrix[0] = new int[]{1,0,0,0,0,0};
_matrix[1] = new int[]{1,1,1,1,0,0};
_matrix[2] = new int[]{0,0,0,1,0,0};
_matrix[3] = new int[]{0,0,0,1,0,0};
_matrix[4] = new int[]{0,0,0,1,1,0};
_matrix[5] = new int[]{0,0,0,0,1,0};

One has:

start m = 0 n = 0
      m = 1 n = 0
      m = 1 n = 1
      m = 1 n = 2
      m = 1 n = 3
      m = 2 n = 3
      m = 3 n = 3
      m = 4 n = 3
      m = 4 n = 4
      m = 5 n = 4

Finally, if there is no possible path to the end of the matrix no error is presented, but in this case some adaptation in the code and it will be possible to use it without problems.

See the example working on ideone.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.