Como solucionar um labirinto em Java?
Olá, Quero criar um Labirinto em Java usando as seguintes classes genéricas: Pilha, Fila e Coordenada(que armazena a coordenada [x, y] atual). O programa lê um arquivo de texto contendo um labirinto, transferindo-o para uma matriz e, a partir da posição inicial, procura e move para espaços vazios até encontrar a posição final.
Este é o arquivo de texto:
5
8
########
E #
### ####
### ####
###S####
Como as classes genéricas Fila, Pilha, e Coordenada devem estar presentes no programa, devem ser criados 4 objetos:
-Um objeto da classe Pilha chamado "path" e um objeto da classe Pilha> chamado "possibilidades", ambos capazes de armazenar 40 coordenadas (5 x 8 - 5 linhas e 8 colunas);
-Um objeto da classe Fila chamado "Fila" que armazena 3 coordenadas e filas os espaços vazios ou o char 'S' em torno da posição atual que são encontrados ao pesquisar todas as 4 direções. (Na primeira busca, por exemplo, a fila seria: [(1,1),,] Como 1,1 é o primeiro espaço vazio encontrado na posição inicial, que é então adicionado à fila.)
-Um objeto da classe Coordinate chamado "corrente", que representa a posição atual.
5 representa o número de linhas. 8 representa o número de colunas. O char '#' representa uma parede, um terreno inviável. O caractere 'E' é a posição de início, o caractere 'S' é a saída e os espaços vazios (char '') representam espaços transitáveis. Assim, o programa primeiro transfere o labirinto no arquivo de texto para uma matriz com o número especificado de linhas e colunas nele (5 e 8), e então encontra o caractere 'E', que é a posição de início e instancia o "atual" Objeto, armazenando sua coordenada nele ((1,0) no caso).
A partir daí, ele procura todas as 4 direções em torno da posição atual no sentido horário (para cima, para a direita, para baixo e para a esquerda, nessa ordem) e armazena as coordenadas dos espaços vazios (ou char 'S') encontrados no objeto "fila" E remove a primeira coordenada da "fila", armazenando essa coordenada no objeto "atual", que representa a posição atual. Então, na matriz, coloca um char '*' na posição representada pelo objeto "atual" (coordenada), indicando que um passo foi dado. Em seguida, empilha o objeto "atual" no objeto "caminho" e empilha o objeto "fila" no objeto "possibilidades". Em seguida, repete essas etapas até encontrar a saída (char 'S'), impressão da matriz e fechamento do programa.
No final, como cada posição é marcada com um '*', a matriz teria que se parecer com isso: (O arquivo de texto é inalterado).
5
8
########
E*** #
###*####
###*####
###S####
Até agora, eu criei as classes:
O que estou tendo problemas é a criação desses objetos e inseri-los em outros objetos, como no armazenamento de coordenadas encontradas na "fila" e empilhamento do objeto "atual" no objeto "caminho". Qual é a maneira correta de fazer este programa?
Desculpe pela longa pergunta.
Este é o arquivo de texto:
5
8
########
E #
### ####
### ####
###S####
Como as classes genéricas Fila, Pilha, e Coordenada devem estar presentes no programa, devem ser criados 4 objetos:
-Um objeto da classe Pilha chamado "path" e um objeto da classe Pilha> chamado "possibilidades", ambos capazes de armazenar 40 coordenadas (5 x 8 - 5 linhas e 8 colunas);
-Um objeto da classe Fila chamado "Fila" que armazena 3 coordenadas e filas os espaços vazios ou o char 'S' em torno da posição atual que são encontrados ao pesquisar todas as 4 direções. (Na primeira busca, por exemplo, a fila seria: [(1,1),,] Como 1,1 é o primeiro espaço vazio encontrado na posição inicial, que é então adicionado à fila.)
-Um objeto da classe Coordinate chamado "corrente", que representa a posição atual.
5 representa o número de linhas. 8 representa o número de colunas. O char '#' representa uma parede, um terreno inviável. O caractere 'E' é a posição de início, o caractere 'S' é a saída e os espaços vazios (char '') representam espaços transitáveis. Assim, o programa primeiro transfere o labirinto no arquivo de texto para uma matriz com o número especificado de linhas e colunas nele (5 e 8), e então encontra o caractere 'E', que é a posição de início e instancia o "atual" Objeto, armazenando sua coordenada nele ((1,0) no caso).
A partir daí, ele procura todas as 4 direções em torno da posição atual no sentido horário (para cima, para a direita, para baixo e para a esquerda, nessa ordem) e armazena as coordenadas dos espaços vazios (ou char 'S') encontrados no objeto "fila" E remove a primeira coordenada da "fila", armazenando essa coordenada no objeto "atual", que representa a posição atual. Então, na matriz, coloca um char '*' na posição representada pelo objeto "atual" (coordenada), indicando que um passo foi dado. Em seguida, empilha o objeto "atual" no objeto "caminho" e empilha o objeto "fila" no objeto "possibilidades". Em seguida, repete essas etapas até encontrar a saída (char 'S'), impressão da matriz e fechamento do programa.
No final, como cada posição é marcada com um '*', a matriz teria que se parecer com isso: (O arquivo de texto é inalterado).
5
8
########
E*** #
###*####
###*####
###S####
Até agora, eu criei as classes:
public class Fila <T> {
private Object[objfila] = null;
private int quantidade,posinicial,posfinal;
public void inserir(Object x) throws Exception
{
if(quantidade==objfila.length)
throw new Exception("Queue is full");
x=objfila(posfinal);
quantidade++;
posfinal++;
}
public void remover() throws Exception
{
if(quantidade==0){
throw new Exception("there are no elements on the queue");
}
quantidade--;
posinicial++;
}
public Fila(int capacidade)
{
this.posinicial=0;
this.posfinal=0;
Object objfila=new Object();
}
}
Stack:
public class Pilha <T> {
private Object[] objpilha = null;
private int topo;
public void inserir(T x) throws Exception
{
if(topo==objpilha.length-1){
throw new Exception("the stack is full.");
}
topo++;
objpilha[topo]=x;
}
public void remover() throws Exception
{
if(topo==-1){
throw new Exception("there are no elements to be removed.");
}
topo--;
}
public Pilha(int capacidade){
objpilha=new Object[capacidade];
topo=-1;
}
}O que estou tendo problemas é a criação desses objetos e inseri-los em outros objetos, como no armazenamento de coordenadas encontradas na "fila" e empilhamento do objeto "atual" no objeto "caminho". Qual é a maneira correta de fazer este programa?
Desculpe pela longa pergunta.
Felipe Pereira
Curtidas 1