Foram adotadas direções na matriz como para frente, para traz ou para baixo.
Para frente: quando o índice n é incrementado;
Para traz: quando o índice n é decrementado;
Para baixo: quando o índice m é incrementado.
0 1 2 3 4 5 n
0 - - - - * -
1 - - - - * -
2 - - - * * -
3 - - - * - -
4 - - - * * -
5 - - - - * -
m
Como convenção vamos adotar que o problema é traduzido em uma matriz m X n e que os nós abertos tem valor 1 e os nós fechados tem valor 0, ficando assim:
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
Levando em consideração que o caminho a ser procurado se inicia descendo pela matriz, primeiro busca-se um nó aberto no vetor m = 0, sendo encontrada a posição m = 0 e n = 4
0 1 2 3 4 5 n
0 0 0 0 0 1 0
m
Trecho de código Java:
//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
}
}
A partir de então entra em ação a busca recursiva, já que se deseja descer a matriz em busca do caminho com nós abertos.
Nesse trecho de código Java temos o método que explora a vizinhança de uma determinada posição da matriz, note que ele recebe 5 argumentos:
matrix: a matriz;
m: posição m onde se encontra o nó aberto;
n: posição n onde se encontra o nó aberto;
mm: posição m do nó aberto anterior;
nn: posição n do nó aberto anterior.
mm e nn são necessários para controlar quem já foi visitado, evitando assim uma recursão infinita.
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
}
Como resultado tem-se:
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
Utilizando a matriz com a configuração abaixo:
_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};
Tem-se:
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
Por fim, caso não exista caminho possível até o fim da matriz nenhum erro é apresentado, mas nesse caso alguma adaptação no código e será possível utilizá-lo sem problemas.
Veja o exemplo funcionando no ideone.
Depois de muitas tentativas não estou a conseguir chegar lá
. Poderia nos mostrar algumas das suas tentativas e o q te impossibilitou de chegar la?