Directions were taken in the array as forward, backward, or downward.
Forward: when the n index is incremented;
Backward: when the n index is decremented;
Down: When the m index is incremented.
0 1 2 3 4 5 n
0 - - - - * -
1 - - - - * -
2 - - - * * -
3 - - - * - -
4 - - - * * -
5 - - - - * -
m
As a convention let's assume that the problem is translated into a m n array and that the open nodes have 1 value and the nodes closed has 0 value, thus:
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
Considering that the path to be searched starts by descending through the matrix, we first look for an open node in the vector m = 0, finding the position m = 0 and n = 4
0 1 2 3 4 5 n
0 0 0 0 0 1 0
m
Java code snippet:
//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 starts, since you want to descend the array in search of the path with open nodes.
In this section of Java code we have the method that explores the neighborhood of a certain position of the array, note that it receives 5 arguments:
matrix: the matrix;
m: position m where the node is open;
n: position n where the node is open;
mm: position m of the previous open node;
nn: position n of the previous open node.
mm and nn are required 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 you have:
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 array 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};
You have:
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 array no error is displayed, but in this case some adaptation in the code and you can use it without problems.
See the example working on ideone .
