1

Estou a ter alguma dificuldade em resolver um problema de recursividade, que abaixo explico.

Dada uma matriz de n linhas e colunas, verificar se existe permeabilidade, ou seja, tendo a seguinte matriz(sendo que '*' - representa nó aberto e '-' - representa nó fechado):

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

Verificar se existe um caminho de nós abertos desde a linha 0 até à linha 5. Neste caso, o problema reduz-se a saber se existe um nó aberto na última linha que possa ser ligado a um nó aberto na primeira linha através de nós abertos vizinhos (o de cima, o de baixo, o da direita e o da esquerda).

Depois de muitas tentativas não estou a conseguir chegar lá, especialmente porque tem de se usar recursividade.

3
  • 4
    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?
    – Math
    Commented 11/03/2014 às 16:09
  • A sua dúvida é sobre como funciona a recursividade ou sobre o algoritmo mesmo? Como @Math já mencionou, se você já tentou algum algoritmo, talvez seja interessante colocar ao menos a sua tentativa mais promissora na questão. Commented 12/03/2014 às 10:43
  • Outra pergunta: a sua configuração vai ser sempre assim "simples"? Digo, se existir um caminho possível, ele será sempre único? Commented 12/03/2014 às 10:47

1 Resposta 1

1

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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .