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.
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?– Math
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.
– Luiz Vieira
Another question: will your configuration always be so "simple"? I mean, if there is a possible path, it will always be unique?
– Luiz Vieira