[Resolvido]Dúvida em um método de Recursão

Bom dia || boa tarde || boa noite, eu sou um novato em programação e tenho uma dúvida referente a um método recursivo para contar caracteres em uma matriz, sendo que ela possui caracteres misturados. Porém eu estou tendo problemas com os meus pontos de parada, acho eu…

     private int ContaChar(int line, int column, String direction) {
               return ContaCharR(line, column, 1, direction);
     }
 
     private int ContaCharR(int line, int column, int units, String direction) {

         // valida se a posição já foi revelada, se foi revelada deve continuar
        // procurando.

         // Esse ponto de parada, já dá um erro pelo debugger, 
         //mas como deveria ser a condição para ele só desconsiderar 
        //essa posição e seguir em frente?

           if (isPosicaoRevelada(line, column)) {
               return ContaChar(line, column, direction);
           } 
                               
           // Se ainda não havia sido revelada, é revelada.

            matrizBoolean[line][column] = true;

          // Vê se o caractere é igual ao passado por parâmetro
         // direction significa para onde a recursão está indo.

         if (isCaractereIgual(line, column, direction)) {
                    			
             // Se é o mesmo caractere vai começar a procurar vizinho idênticos.
                    			
             // (I) linha atual -1, coluna atual

             if (line- 1 >= 0 && line- 1 < matriz.length) {
                if (column>= 0 && column< matriz[line- 1].length) {
                    return ContaCharR(line- 1, column, units + 1, "Cima");
                }
             }

            // (II) linha atual + 1, coluna atual;

            if (line+ 1 >= 0 && line+ 1 < matriz.length) {
               if (column>= 0 && column< matriz[line+ 1].length) {
                   return ContaCharR(line+ 1, column, units + 1, "Baixo");
               }
            }

            // (III) linha atual, coluna atual – 1;

           if (line>= 0 && line< matriz.length) {
              if (column- 1 >= 0 && column- 1 < matriz[line].length) {
                  return ContaCharR(line, column- 1, units + 1, "Esquerda");
              }
           } 

          // (IV) linha atual, coluna atual + 1.

          if (line>= 0 && line< matriz.length) {
             if (column+ 1 >= 0 && column+ 1 < matriz[line].length) {
                 return ContaCharR(line, column+ 1, units+ 1, "Direita");
             }
          }

        } 

        return units;

     }

Será que poderiam me dar uma ajuda?
Agradeço desde já!

Eu faria um pouco diferente.

Se a lenha ou a coluna estiver fora dos limites, retorna zero, isso alivia o código pois não há mais necessidade de se preocupar com as posições.

private int ContaCharR(int row, int col, char value) {
    if (row < 0 || row >= matriz.length || col < 0 || col >= matriz[row].length) return 0;

Não entendi muito bem essa parte, vc quer contar caracteres iguais? Se for, então se a posição foi revelada ou o caractere for diferente do que está sendo buscado, retorna 0

       if (isPosicaoRevelada(line, column) || !isCaractereIgual(row, col, value)) {
            return 0; // achaTodosCaracteres(line, column, direction);
       } else {
            matrizBoolean[line][column] = true;
       }

agora vem a parte recursiva:

return 1 + ContaCharR(row + 1, col) + ContaCharR(row, col + 1) + ContaCharR(row - 1, col) + ContaCharR(row, col - 1);

e o ContaChar

 private int ContaChar(int row, int col) {
           return ContaCharR(row, col, matriz[row][col]);
 }

Vou tentar fazer as modificações que tu me aconselhaste e rodar o debugger novamente.
Obrigado por enquanto :+1:

Um do meus pontos de parada desse método é enquanto houver vizinhos com o mesmo char, ele vai procurar esses vizinhos, e quando não achar, cria o objeto com as unidades encontradas do método e pula para outro char fazendo o mesmo esquema.
Porém no meu método de comparação ele está tentando acessar uma row que tem o mesmo length da matriz, ou seja, arrayIndexOutOfBounds e acredito que também esteja acontecendo esse erro com a col. Já debuggei e modifiquei as minhas condições inúmeras vezes, porém ele continua tentando comparar com uma row ou col inexistente.

public boolean findNeighbor(int row, int col, String direction) {
		boolean result = true;

		if (row + 1 > matrix.length || row - 1 < 0 || col + 1 > matrix[row].length || col - 1 < 0) {
			result = false;
		} else {
			if (row == 0 && col == 0) {
				result = true;
			} else if (direction == "Up") {
				if (matrix[row][col] != matriz[row - 1][col])
					result = false;
			} else if (direction == "Down") {
				if (matrix[row][col] != matrix[row + 1][col])
					result = false;
			} else if (direction == "Left") {
				if (matrix[row][col] != matrix[row][col - 1])
					result = false;
			} else if (direction == "Right") {
				if (matrix[row][col] != matrix[row][col + 1])
					result = false;
			}
		}

		return result;

	} 

Eu utilizei a String direction, para dizer qual o sentido que a recursão está tomando, para ser possível fazer a comparação correta nesse método. Porém debuggando ele chega na row == 14 e tenta comparar com a row + 1 == 15, o que não deveria ocorrer por causa do meu if, que olha se a row + 1 ou a col + 1 forem maior que o length.

Depois dessa comparação, se for false retorna 0 e se for true ele faz a recursão que procura os outros vizinhos.

Será que estou me passando na condição?

Obrigado!

eu verifiquei esse método e não achei erro, posta o método que chama ele para podermos analisar se não é ali que pode está o erro.

if (row + 1 > matrix.length || row - 1 < 0 || col + 1 > matrix[row].length || col - 1 < 0) {

da para mudar para:

if (row + 1 > matrix.length || row == 0 || col + 1 > matrix[row].length || col == 0) {

Agora achei algo que pode ser que está o erro, você diz abaixo no seu if que pode ser 0, mas acima você não permite, assim nunca cai no if, pois 0-1 daria -1 o que entra no primeiro if que retorna false;

pode trocar por

if (row + 1 > matrix.length || row < 0 || col + 1 > matrix[row].length || col < 0) {

1 curtida

Acho que onde está

row + 1 > matrix.length

seria:

row + 1 >= matrix.length

pois se length for 15 e row for 14, então fica 15 >= 15 e portanto não tem vizinho, o mesmo para o col

col + 1 > matrix[row].length

para

col + 1 >= matrix[row].length
1 curtida

O método que chama o findNeighbor é o seguinte:

private int ContaChar(int row, int col, String direction) {
		return ContaCharR(row, col, direction);
	}

	private int ContaCharR(int row, int col, String direction) {

		// valida se a posição já foi revelada, se foi revelada deve continuar
		// procurando.

		if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[row].length) {
			return 0;
		}

		if (isPosicaoJaRevelada(row, col)) {
			return 0;
		} else {
			matrixBoolean[row][col] = true;
		}

		if (!findNeighbor(row, col, direction)) {
			return 0;
		} else {

			return 1 + ContaCharR(row + 1, col, "Down")
					+ ContaCharR(row , col + 1, "Right")
					+ ContaCharR(row - 1, col, "Up")
					+ ContaCharR(row , col - 1, "Left");
		}

E o método que eu tenho problema é o findNeighbor que é o seguinte no qual fiz as alterações que me propuseram:

public boolean findNeighbor (int row, int col, String direction) {
		boolean result= true;

		if (row+ 1 > matrix.length || row== 0 || col+ 1 > matrix[row].length || col== 0) {
			result= false;
		} else if (row+ 1 > matrix.length || row< 0 || col+ 1 > matrix[row].length || col< 0) {
			result= true;
		} else if (direction== "Up") {
			if (matrix[row][col] != matrix[row- 1][col])
				result= false;
		} else if (direction== "Down") {
			if (matrix[row][col] != matrix[row+ 1][col])
				result= false;
		} else if (direction== "Left") {
			if (matrix[row][col] != matrix[row][col- 1])
				result= false;
		} else if (direction== "Right") {
			if (matrix[row][col] != matrix[row][col+ 1])
				result= false;
		}

		return result;

	}

Testei pelo debbuger, e logo na primeira verificação ele entra em false, e fica lá até dar StackOverflowError, segue a primeira verificação que causa isso:

if (row+ 1 > matrix.length || row== 0 || col+ 1 > matrix[row].length || col== 0) {'
result = false;

Será que o fato de eu ter alterado o row == 0, faz ele ficar em false logo de cara?

Obrigado!

alterando para row== 0 ou deixando row-1<0 ele vai entrar no false, pois 0-1<0 também entra, só mostrei que um era igual o outro, no caso para garantir que apenas não seja valor negativo tem que trocar para row<0 e col<0,ai ele entra no true.

não vai dar certo pois você está retornando verdadeiro o que no de cima é false, então ele não entra nesse método, você pode retirar esse else if por completo, pois se não cair em nenhum if ou else if ele já retorna true;

acho que seu erro está aqui.
if (!findNeighbor(row, col, direction)) {
return 0;
} else {

		return 1 + ContaCharR(row + 1, col, "Down")
				+ ContaCharR(row , col + 1, "Right")
				+ ContaCharR(row - 1, col, "Up")
				+ ContaCharR(row , col - 1, "Left");
	}

PS: não consegui fazer citação, por isso foi no braço mesmo.

você está verificando somente uma direção que é a passada no inicio, de depois no else você chama as 4 direções, você teria que verificar 1 a 1 exemplo:
if (findNeighbor(row, col, "Up)) {
return 1 + ContaCharR(row - 1, col, “Up”);
}
else{ return 0;}

if (findNeighbor(row, col, “Down”)) {
return 1 + ContaCharR(row - 1, col, “Down”);
}
else{ return 0;}

e assim por diante.

Se eu tiver entendido correto o que seu enunciado pede é para contar quantos caracteres terão em uma matriz: exemplo matriz[0][0]=“casa”, matriz[0][1]=“escola”, matriz[1][0]=“pa”,matriz[1][1]=“cama”, o resultado final seria 16; Sendo assim aconselho a fazer mais ou menos assim:

private int ContaCharR(int line, int column,String[][] vetor){
if(line==vetor.lenght&&column==vetor[line].lenght){ return 0;}
else if(cloumn==vetor[line].lenght){
return vetor[line][colum].size() + ContaCharR(line+1,0,vetor);}
else{ return vetor[line][colum].size() + ContaCharR(line,column+1,vetor);}
}

para chamar a primeira vez ficaria
ContaCharR(0,0,vetor);

1 curtida

Lembrando que sempre que você começa não vai ter vizinho nem a esquerda nem em cima, ai não continuaria a execução do seu programa da forma que está, caso tenha que verificar é os vizinho mesmo você vai ter que verificar 1 a 1 para saber quais vizinhos ele tem, e permitir que ele olhes os vizinhos existentes, mesmo se não for os 4, for 2, 3 ou 4.
Você também pode tentar esclarecer melhor o que você tem que fazer usando método recursivo, para tentarmos te ajudar a desenvolver a lógica.

1 curtida

O meu objetivo é pegar uma matriz nesse formato:

E por exemplo, olhar o primeiro char, contar todos eles e criar um objeto passando essa quantidade, por exemplo se eu tiver o ‘=’, eu crio o objeto Muralha(String name, int units).

Muralha a = new Muralha(“Muralha da china”, ContaCharR(int row, int col, String direction)

que no caso do txt. criaria uma muralha com 62 units.

Mas se por exemplo eu tiver ‘+’ que aparece em conjuntos separados dentro da matriz. Como no caso do txt. Eu tenho que criar objetos diferentes. Exemplo com o char ‘+’ do txt que anexei:

BancoDaPraca a = new BancoDaPraca(“a”,14);

e

BancoDaPraca b = new BancoDaPraca(“b”,19);

onde esse 14 e 19 provêm do método recursivo que conta os vizinhos com o mesmo char.

Esse segundo banco eu crio porque tenho ’ ’ == “espaço” entre os dois, ou seja, são objetos diferentes. Sempre que os chars não estão juntos, eu devo criar um outro objeto.

Vou fazer as alterações propostas e vejo se o erro persiste.

Obrigado!

pelo que eu entendi você tem uma matriz de char, que quer pegar o agrupamento. Se ele estiver em diagonal conta como vizinho? exemplo:
+/
/+
assim contaria como 2,(muito importante saber se isso pode acontecer, se sim depois comenta) se sim muda um pouco. Outra coisa, se você passar uma letra para ele comparar no seu exemplo se for algo genérico que você não sabe onde está cada coisa, quantos agrupamentos tem, fica muito difícil fazer. Acho que você precisaria de uma outra classe que armazenasse o caractere, quantas aparições ele teve e quantas vezes ele repetiu.

1 curtida

No meu método eu só posso pegar em vertical e horizontal. Estou rodando alguns testes para achar os erros restantes. Eu no momento estou trabalhando com duas recursões para fazer isso, uma que caminha pela matriz e a outra que procura os vizinhos iguais e conta o número de caracteres iguais.

Obrigado!

Então, nos vizinhos se você usar as 4 direções um que já foi contado, vai ser contado de novo, pois pense, você está na posicão 0,0, você verifica se tem direita, esquerda, cima e baixo, nesse primeiro só vai ter direita e baixo, ai ele vai para a posição 0,1 e 1,0. Depois ele vai na 0,1 e vê que tem esquerda, direita e baixo, então vai para 0,0 0,2 e 1,1. A Posição 0,0 já havia sido contada, então será contada de novo e não terá fim a sua recursão, pois irá para 0,0 toda hora. Se fosse só para procurar 1 caractere específico eu já tinha a lógica toda pensada, mas como você precisa que conte todos e tem alguns que o caracter repete, a única forma até agora que imaginei fazer foi criando uma classe com atributos: caracter, contagem, linhaFinal e linhaInicial, depois fazendo um array para armazenar esses diversos tipos. Nesse exercício o desenvolvimento da lógica acaba sendo mais essencial do que o código de fato. Estou aqui ainda tentando pensar em uma maneira, e se conseguir te passo a lógica.

1 curtida

Não não, a lógica eu mesmo devo desenvolver, são certas dúvidas sobre o código em java que acabam me trancando. Aceito dicas, mas a lógica completa me é um tanto quanto “inútil”, pois aí não consigo aprender hehe. Por isso vou refazendo o código e melhorando a minha lógica, assim que mais dúvidas irem surgindo, vou postando elas, com o intuito de melhorar em ambos os tópicos.
A vida sem o sentido de no pain no gain é sem graça heh.

Obrigado e vou ir refazendo o código com as dicas.

P.S.:Tenho a classe para contar os caracteres e fazer a contagem.

1 curtida

Você está certo, qualquer coisa então que for desenvolvendo e for dando erro eu te ajudo aqui. Algo que eu utilizo para me ajudar a fazer a lógica é resolver primeiro manualmente o problema no papel e caneta assim me facilita para depois passar para um programa. Mesmo colocando apenas vizinho a direita e baixo tem que tomar cuidado com alguns cenários como no exemplo abaixo



nesse exemplo tanto o vetor na posição 0,1 e o da 1,0 vão chamar o 1,1 e vai contar ele 2 vezes, mais os que ele for gerando.

1 curtida

Para esse tipo de situação eu tenho uma matriz de booleanos, que olha se a posição já foi visitada, se ela foi, segue para outro lado.

1 curtida

Consegui resolver as inconsistências que estavam me incomodando, os comentários me ajudaram bastante a melhorar o meu código e lógica hehe.
Muito obrigado pelas dicas!