Problema do Labirinto-->SOMA MÁXIMA

Gente é o seguinte tenho que achar o caminho em um labirinto de strings, sendo que no labirinto há números espalhados pelo caminho e posições posições bloqueadas. A saída do programa tem que ser o caminho que maximize a soma dos números espalhados no labirinto, e que forme um caminho possível. Ok, eu consegui fazer o labirinto e conseguir fazer com que o programa retorne um caminho, o problema que eu tô tendo é que o caminho que ele percorre nem sempre é o máximo, e não tenho ideia de como fazer pro programa sempre percorrer o caminho maximal. Por enquanto tô fazendo a implementação para 4 chamadas recursivas(cima,baixo,esq,direita), sem usar backtracking. Se alguém puder dar uma luz eu agradeceria mtttttt.

EXEMPLO DE ENTRADA
X(POSIÇÃO BLOQUEADA)
8 9 (TAMANHO DO LABIRINTO)
…
.XXX.XXX2
2XXX.XXX2
.XXX7XXX2
.XXX1XXX2
3XXX.XXX2
.XXX.XXX2
…
0 4 COMEÇO
7 4 FIM

SAIDA
16 12 (TAMANHO DO CAMINHO E TOTAL DA SOMA)
(POSIÇÕES DO CAMINHO)
0 4
0 5
0 6
0 7
0 8
1 8
2 8
3 8
4 8
5 8
6 8
7 8
7 7
7 6
7 5
7 4

Aqui vai o código que tenho até agora:

public class Procura {

private static char[][] mapa;

private static final char LIVRE = ‘.’;

private static final char OCUPADO = ‘X’;

private static final char PASSO = ‘*’;

private static int soma=0;

private static int caminhoTotal=0;

private static int[] Tlin= new int[50];

private static int[] Tcol= new int[50];

public static boolean verifica(char [][] t, int lin, int col){
	try{
		if(t[lin][col] == LIVRE){
			return true;
		}else if(t[lin][col]=='1'){
			return true;
		}else if(t[lin][col]=='2'){
			return true;
		}else if(t[lin][col]=='3'){
			return true;
		}else if(t[lin][col]=='4'){
			return true;
		}else if(t[lin][col]=='5'){
			return true;
		}else if(t[lin][col]=='6'){
			return true;
		}else if(t[lin][col]=='7'){
			return true;
		}else if(t[lin][col]=='8'){
			return true;
		}else if(t[lin][col]=='9'){
			return true;
		}	
	}
	catch(Exception e){
	}

	return false;
}
public static void imprime(char [][] t){
	for(int i = 0; i < t.length; i++){
		for(int j = 0; j < t[i].length; j++){
			if(t[i][j] ==OCUPADO)
				System.out.print(" X ");
			else if(t[i][j] == LIVRE)
				System.out.print(" . ");
			else 
				System.out.printf("%2c ", t[i][j]);
		}			
		System.out.println();
	}
	System.out.println();
}
public static boolean encontraCaminho(char[][]m,int lin, int col,int d_lin, int d_col,char passo){
	if(verifica(m,lin,col)){
		caminhoTotal++;		
		if(m[lin][col]=='1'){
			soma+=1;
		}else if(m[lin][col]=='2'){
			soma+=2;
		}else if(m[lin][col]=='3'){
			soma+=3;
		}else if(m[lin][col]=='4'){
			soma+=4;
		}else if(m[lin][col]=='5'){
			soma+=5;
		}else if(m[lin][col]=='6'){
			soma+=6;
		}else if(m[lin][col]=='7'){
			soma+=7;
		}else if(m[lin][col]=='8'){
			soma+=8;
		}else if(m[lin][col]=='9'){
			soma+=9;
		}		
		m[lin][col]=PASSO;
		for (int i = 0; i < Tlin.length;i++ ) {
			if(Tlin[i]==-1){
			Tlin[i]=lin;	
			break;
			}
		}
		for (int i = 0; i < Tcol.length;i++ ) {
			if(Tcol[i]==-1){
			Tcol[i]=col;	
			break;
			}
		}
		imprime(m);
		
		if(lin==d_lin && col ==d_col){
			imprime(m);
			return true;
		} 
		if(verifica(m,lin+1,col))
			return encontraCaminho(m, lin+1, col, d_lin, d_col, passo);
		else if(verifica(m,lin,col-1)){
			encontraCaminho(m, lin, col-1, d_lin, d_col, passo);
		}else if(verifica(m,lin-1,col)){
			encontraCaminho(m, lin-1, col, d_lin, d_col, passo);
		}else if(verifica(m,lin,col+1)){
			encontraCaminho(m, lin, col+1, d_lin, d_col, passo);
		}else{
			soma=0; caminhoTotal=0;
			for (int i = 0; i < Tlin.length; i++) {
				Tlin[i]=-1;
			}
			for (int i = 0; i < Tcol.length; i++) {
				Tcol[i]=-1;
			}
		}
	}
	return false;	
}
public static void leMatriz(){
	Scanner in = new Scanner(System.in);
	int lin = in.nextInt();
	int col = in.nextInt();
	mapa = new char[lin][col];
	in.nextLine();

	for (int i = 0; i < lin; i++) {
		String linha = in.nextLine();
		
		for (int j = 0; j < col; j++) {
			mapa[i][j] = linha.charAt(j);
			if(mapa[i][j]=='1'){
				//AQUI DEVEMOS FAZER A SOMA DA COLUNA
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='2'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='3'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='4'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='5'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='6'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='7'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='8'){
				System.out.println(mapa[i][j]);
			}else if(mapa[i][j]=='9'){
				System.out.println(mapa[i][j]);
			}	
		}
	}
	//endereço de origem
	int i_lin=in.nextInt();
	int i_col=in.nextInt();
	//endereço de chegada
	int d_lin=in.nextInt();
	int d_col=in.nextInt();
	
	encontraCaminho(mapa, i_lin, i_col, d_lin, d_col,'0');
	
}
public static void main(String[] args){
		
	
	for (int i = 0; i < Tlin.length; i++) {
		Tlin[i]=-1;
	}
	for (int i = 0; i < Tcol.length; i++) {
		Tcol[i]=-1;
	}
	
	leMatriz();
	//leitura dos dados finais
	System.out.printf("%d %d",caminhoTotal,soma);

	System.out.println();
	for (int i = 0; i < Tlin.length; i++) {
		if(Tlin[i]!=-1 || Tcol[i]!=-1){
			System.out.print(Tlin[i]+" ");
			System.out.println(Tcol[i]);
		}
	}
}

}

1 Resposta

Topicos relacionados