Recursividade e Matriz

por favor editer seu codigo e coloque entre as tags ‘code’
e explique melhor oq a função passo deve fazer, vc quer q ela encontre uma saida do labirinto?

t+

quikkoo:

por favor editer seu codigo e coloque entre as tags ‘code’
e explique melhor oq a função passo deve fazer, vc quer q ela encontre uma saida do labirinto?

t+

isso uma saída do labirinto

wellington.nogueira:

felp10:

Bom dia a todos, olha nóis aki de novo.

Bem eu tenho que fazer um labirinto simples só para aparecer no console mesmo.

Só que me embananei todo no meu código gostaria de um help dêem uma olhada.

public class Labirinto {
	int labirinto[][];
	String caminho[];
	int posicao;
	
	public void geraLabirinto(int tamanho){
		
		caminho = new String [Math.pow(2, tamanho)];
		
		labirinto = new int[tamanho][tamanho];
		
		for(int i = 0; i < tamanho; i++){
			for(int j = 0; j < tamanho; j++){
				labirinto[i][j] = 0 ;
				
			}
		}
	}
	public void passo(int lado, int casa){
		if(labirinto[lado][casa+1] == 0 &&  caminho[posicao-1].equals(""+lado+","+(casa+1)){
			caminho[posicao] = " "+ lado + "," +(casa+1);posicao++;
			passo(lado,casa+1);

			}
			if(labirinto[lado+1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1)){
			passo(lado+1,casa);
				}
			if(labirinto[lado-1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1)){
			passo(labirinto-1, casa);
			
					}	

				}
			
			}
		}

	}
	
}

Bem estou com dúvida nesse segundo método nao estou conseguindo fazer passar de casa. Alguém pode me dar uma luz?
Vlw galera!

Eu não entendi o método geraLabirinto…
você criou um array bidimensional de inteiros int[][] labirinto
E associou a cada casa o char zero (‘0’)

No método passo, você compara labirinto[indice1][indice2] com o inteiro zero (0).
‘0’ é diferente de 0 (‘0’ != 0). Apesar de int aceitar atribuição de char.

Pode ser isso…
Sem o resto do código fica difícil saber…

Hum é mesmo corrigindo, na verdade o método labirinto eu gostaria que criasse o labirinto com zeros e uns se 0 vai encontrando a saída.

Tá vamos por partes o método geraLabirinto do jeito que está o que falta para gerar o Labirinto com 0 e 1 sendo 0 o caminho que ele vai seguir e 1 desvia. A matriz será dada entrada por JOptionPane

Pessoal me ajuda por favor comecei a main assim:

ackage br.com.labirinto;

public class Principal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Labirinto lab = new Labirinto();
		
		lab.geraLabirinto(4);
		
	}

}

// o codigo da classe Labirinto novamente

package br.com.labirinto;
import java.lang.*;


public class Labirinto {
	int labirinto[][];
	String caminho[];
	int posicao;
	
	public void geraLabirinto(int tamanho){
		
		caminho = new String [(int) Math.pow(2, tamanho)];
		
		labirinto = new int[tamanho][tamanho];
		
		for(int i = 0; i < tamanho; i++){
			for(int j = 0; j < tamanho; j++){
				labirinto[i][j] = 0 ;
				
			}
		}
	}
	public void passo(int lado, int casa){
		if(labirinto[lado][casa+1] == 0 &&  caminho[posicao-1].equals(""+lado+","+(casa+1))){
			caminho[posicao] = " "+ lado + "," +(casa+1);posicao++;
			passo(lado,casa+1);

			}
			if(labirinto[lado+1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo(lado+1,casa);
				}
			if(labirinto[lado-1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo (lado-1,casa);
			
					}	

				}
	public void imprimeCaminho(){
		
			
			}
		}

Fico no aguardo de uma orientação para que eu possa continuar, não quero o exercício não somente uma explicação para continuar.

kara o enunciado é esse aki :

o	Criar o labirinto com um Array Bidimensional [X][X]. Pedir o valor de X para o usuário;

o	Gerar de forma aleatória o labirinto onde, o caractere _ é o caminho e o caractere | é parede. A posição [0][0] é a entrada e a posição [X][X] é a saída. Usar a função RANDOM para gerar caminho (_) ou parede (|). Sugestão: valores maiores que 0,5 é parede, menor ou igual é caminho ou qualquer outra lógica para gerar o labirinto;

o	Usar recursividade para encontrar o caminho, pois as regras são as mesmas para cada posição da matriz sendo que uma encruzilhada tem que ser avaliado todas os caminhos possíveis até encontrar a saída;

o	Não se esqueça de tratar caminhos repetidos. Ou seja, caminhos já verificados, não devem ser verificados novamente;

o	Uso da recursividade;

o	Uso do array bidimensional;

o	Funcionalidade;

Acho que com o enuciado fica melhor. Estou no caminho certo ou não?

Obrigado!

opa blz sem querer abusar mas ja abusando eu estou usando o eclipse e o que esta ocorrendo e que so esta imprimindo no console assim:
0
0
0
0

o correto era para estar imprimindo em matriz o que esta errado?aaa to perdidaco rsrs

Dei uma implementada porem na linha 21 esta dando erro porque?

package br.com.labirinto;
import java.lang.*;
import java.util.Random;


public class Labirinto {
	int labirinto[][];
	String caminho[];
	Random rd = new Random();
	
	int posicao;
	
	public void geraLabirinto(int tamanho){
		
		caminho = new String [(int) Math.pow(2, tamanho)];
		
		labirinto = new int[tamanho][tamanho];
		
		for(int i = 0; i < tamanho; i++){
			for(int j = 0; j < tamanho; j++){
				labirinto[i][j] = nextInt(2);
				System.out.println(labirinto[i][j]);
			}
		}
	}
	public void passo(int lado, int casa){
		if(labirinto[lado][casa+1] == 0 &&  caminho[posicao-1].equals(""+lado+","+(casa+1))){
			caminho[posicao] = " "+ lado + "," +(casa+1);posicao++;
			passo(lado,casa+1);

			}
			if(labirinto[lado+1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo(lado+1,casa);
				}
			if(labirinto[lado-1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo (lado-1,casa);
			
					}	

				}
	public void imprimeCaminho(){
		
			
			}
		}


	
//principal

package br.com.labirinto;

import javax.swing.JOptionPane;

public class Principal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Labirinto lab = new Labirinto();
		
		lab.geraLabirinto(Integer.parseInt(JOptionPane.showInputDialog(null, "Digite o tamanho do labirinto")));
		
	}

}

vlws

Galerinha do bem dando continuidade fiz algumas coisinhas mas ainda falta muito se puder me ajudar alguem, por favor:

//principal

package br.com.labirinto;

import javax.swing.JOptionPane;

public class Principal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Labirinto lab = new Labirinto();
		
		lab.geraLabirinto(Integer.parseInt(JOptionPane.showInputDialog(null, "Digite o tamanho do labirinto")));
		
	}

}

package br.com.labirinto;
import java.lang.*;
import java.util.Random;


public class Labirinto {
	int labirinto[][];
	String caminho[];
	Random rd = new Random();
	
	int posicao;
	
	public void geraLabirinto(int tamanho){
		
		caminho = new String [(int) Math.pow(2, tamanho)];
		
		labirinto = new int[tamanho][tamanho];
		
		for(int i = 0; i < tamanho; i++){
			for(int j = 0; j < tamanho; j++){
				 
				labirinto[i][j] = rd.nextInt(2);
				System.out.println(labirinto[i][j]);
				passo(i,j);
			}
		}
	}
	
	public void passo(int lado, int casa){
		if(labirinto[lado][casa+1] == 0 &&  caminho[posicao-1].equals(""+lado+","+(casa+1))){
			caminho[posicao] = " "+ lado + "," +(casa+1);posicao++;
			passo(lado,casa+1);
			imprimeCaminho();

			}
			if(labirinto[lado+1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo(lado+1,casa);
			imprimeCaminho();
			
				}
			if(labirinto[lado-1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1))){
			passo (lado-1,casa);
			imprimeCaminho();
			
					}	

				}
	public void imprimeCaminho(){
			
				System.out.println("_");
			
		
			}
		}

/*Exception:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
	at br.com.labirinto.Labirinto.passo(Labirinto.java:30)
	at br.com.labirinto.Labirinto.geraLabirinto(Labirinto.java:24)
	at br.com.labirinto.Principal.main(Principal.java:14)
*/

Ajuda por favor

O teu problema é quando chegas às bordas do tabuleiro… Não podes verificar o valor de uma casa se ela não existe!

Assim, antes de acederes a posições [qqcoisa + 1] tens de verificar se qqcoisa não é já o limite do tabuleiro. Da mesma forma que [var-1] só pode ser feito se var for diferente de 0 senão vai cair fora do tabuleiro.

Deu para perceber?

pmlm:

O teu problema é quando chegas às bordas do tabuleiro… Não podes verificar o valor de uma casa se ela não existe!

Assim, antes de acederes a posições [qqcoisa + 1] tens de verificar se qqcoisa não é já o limite do tabuleiro. Da mesma forma que [var-1] só pode ser feito se var for diferente de 0 senão vai cair fora do tabuleiro.

Deu para perceber?

Hum não entendi, isso é devido a exception que está dando é isso? cara to perdido mesmo preciso me redirecionar no programa bem o método geraLabirinto entao esta com problema o que está faltando ou o que eu preciso corrigir depois vou ver se realmente é necessário criar uma outra array para guardar as casas que já passei como me indicou o amigo wellington

No método passo, antes de cada if tens de validar que não vais cair fora do tabuleiro (ArrayIndexOutOfBoundsException)

Onde tens: if(labirinto[lado][casa+1] == 0 ...
tens de ter if( casa != labirinto[0].length-1 && labirinto[lado][casa+1] == 0 ...

Nota que isto é só para não dar a Exception. Não me debrucei sobre o algoritmo e não sei se vai achar o caminho correctamente.

Então a idéia é fazer um novo método boolean por exemplo para verificar isso ?

felp10:

Bom dia a todos, olha nóis aki de novo.

Bem eu tenho que fazer um labirinto simples só para aparecer no console mesmo.

Só que me embananei todo no meu código gostaria de um help dêem uma olhada.

public class Labirinto {
	int labirinto[][];
	String caminho[];
	int posicao;
	
	public void geraLabirinto(int tamanho){
		
		caminho = new String [Math.pow(2, tamanho)];
		
		labirinto = new int[tamanho][tamanho];
		
		for(int i = 0; i < tamanho; i++){
			for(int j = 0; j < tamanho; j++){
				labirinto[i][j] = '0' ;
				
			}
		}
	}
	public void passo(int lado, int casa){
		if(labirinto[lado][casa+1] == 0 &&  caminho[posicao-1].equals(""+lado+","+(casa+1)){
			caminho[posicao] = " "+ lado + "," +(casa+1);posicao++;
			passo(lado,casa+1);

			}
			if(labirinto[lado+1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1)){
			passo(lado+1,casa);
				}
			if(labirinto[lado-1][casa] == 0 && caminho[posicao-1].equals(""+lado+","+(casa+1)){
			passo(labirinto-1, casa);
			
					}	

				}
			
			}
		}

	}
	
}

Bem estou com dúvida nesse segundo método nao estou conseguindo fazer passar de casa. Alguém pode me dar uma luz?
Vlw galera!

No método passo, você compara labirinto[indice1][indice2] com o inteiro zero (0).
‘0’ é diferente de 0 (‘0’ != 0). Apesar de int aceitar atribuição de char.

Pode ser isso…
Sem o resto do código fica difícil saber…

Mudou alguma coisa?

Precisa-se, para ajudá-lo, saber o que quer fazer realmente…

Pra mim, após criar o labirinto seria chamar o passo passando por onde inicia (se é um labirinto, talvez fosse necessário informar a chegada.

E, por fim, imprimir o ccaminho.

Para o array caminho, mudaria o tipo dela para uma nova classe chamada Point com x e y como atributos (pode ser do contrutor mesmo) e um toString (sobrescrito) no formato que precisa ao invés de ser do tipo String.

Está dificil ajudar sem fornecer mais detalhes…

Hmm…

Tem que alterar (não sei se prentende fazer isso depois) o método que gera labirinto para que possua um de dois possíveis valores.

Eu criaria um array extra de mesmo tamanho onde ficariam marcadas as “casas” pela qual já passei.

É mais simples comparar no método recursivo.
Aliás, é importante prever uma forma de parar a recursividade.
Não testei o método mas parece que ele vai dar um StackOverflowError ou um ArrayOutOfBoundsExcecption. Vc não confirma se é a última casa ou não, só vai incrementando o valor.

Sua verificação com o caminho indica apenas o de onde veio, não caminhos percorridos e inválidos. É bom observar melhor isso.

Obs.: O problema da forma descrita pode criar um labirinto sem saída, mas blz.