Java permeability

Question

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.

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.