5

Galera, alguém pode me ajudar. Preciso implementar uma função recursiva que recebe um labirinto e uma posição atual.

O labirinto é dado por uma matriz de caracteres (“char”) onde ‘X’ representa uma parede, ‘0’ representa um caminho, ‘E’ representa a entrada e ‘S’ representa a saída. O objetivo é imprimir na tela um caminho válido que leve da entrada até a saída, esse caminho não precisa ser o mais curto, mas ele não pode passar duas vezes pela mesma casa. O labirinto é indexado de [0 .. largura – 1][0 .. altura – 1], onde largura e altura são a quantidade de casas no eixo X e no eixo Y respectivamente, por exemplo, o labirinto abaixo tem largura 5 e altura 6. A entrada está na casa (3, 0) e a saída na casa (2,5):

XOSXX
OOOXX
OXXXX
OXXOX
OXXOX
OOOEX

Um exemplo de uma solução para esse problema seria o seguinte caminho: (3, 0)(2, 0)(1, 0)(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)(1, 4)(1, 5)(2, 5)

Minha dúvida é como posso estar imprimindo na tela um caminho que leve da entrada até a saída. Código até agora:

#include <stdio.h>
#include <stdlib.h>
void print_position(int x, int y);
void print_maze(char **maze, int largura, int altura);
int labirinto(int x_atual, int y_atual, char **maze, int largura, int 
altura){
int imaior = x_atual;
int imenor = x_atual;
int ybaixo = y_atual;
int ycima = y_atual;
while ( imaior < largura - 1){
if(maze[x_atual + 1][y_atual] != 'X' && maze[x_atual + 1][y_atual] != 
'P'){
       maze[x_atual][y_atual] = 'P';
       x_atual += 1;
}
imaior++;
}
while(imenor > 0){
if(maze[x_atual - 1][y_atual] != 'X'  && maze[x_atual -1][y_atual] != 
'P') {
     maze[x_atual][y_atual] = 'P';
       x_atual -= 1;
   }
imenor--;
}
while(ycima > 0){
if(maze[x_atual][y_atual - 1] != 'X' && maze[x_atual][y_atual - 1] != 
'P'){
    maze[x_atual][y_atual] = 'P';
    y_atual -= 1;
}
ycima--;
}
while(ybaixo < altura - 1){
if(maze[x_atual][y_atual + 1] != 'X' && maze[x_atual][y_atual + 1] != 
'P'){
    maze[x_atual][y_atual] = 'P';
    y_atual += 1;
}
ybaixo++;
}
maze = labirinto(x_atual , y_atual,maze , largura , altura);
}
int main(void){
int largura, altura, x_saida, y_saida, x, y;
scanf("%d %d\n", &largura, &altura);
char ** a = malloc(largura * sizeof(char*));
for(x = 0; x < largura; x++){
a[x] = malloc(altura * sizeof(char));
}
for(y = altura - 1; y >= 0; y--){
for(x = 0; x < largura; x++){
  a[x][y] = getchar();
  if(a[x][y] == 'S'){
    x_saida = x;
    y_saida = y;
  }
}
getchar(); //pegar a quebra de linha
}
print_maze(a, largura, altura);
 //eu acredito que seja mais facil comecar a busca pela saida
labirinto(x_saida, y_saida, a, largura, altura);
printf("\n");
return 0;
}
void print_maze(char **maze, int largura, int altura){
int x, y;
for(y = altura - 1; y >= 0; y--){
for(x = 0; x < largura; x++){
  printf("%c", maze[x][y]);
}
printf("\n");
}
}
void print_position(int x, int y){
  printf("(%d, %d)", x, y);
}
8
  • Parece um exercicio de machine learning, o melhor metodo era usar grafos e achar o caminho Commented 25/08/2018 às 23:03
  • 2
    Não vejo a relação com machine learing labirintos são algoritmos "simples". Faz muito tempo que não programo em C, se quiser eu posso deixar um exemplo em C# ou javascript. Commented 25/08/2018 às 23:52
  • poderia deixar um exemplo em C# ou explicar a lógica ? ajudaria muito.
    – ptr0x
    Commented 25/08/2018 às 23:55
  • Para sair de qualquer labirinto, basta encostar uma das mãos em uma das paredes e seguir andando sem desencostar. O algorítimo basicamente é: escolha entre esquerda ou direita e só vire para esse lado, sempre que a posição à frente não estiver disponível vire para esse lado até poder seguir e assim recursivamente. Uma hora você chegará na saída Commented 26/08/2018 às 0:14
  • Para registrar o caminho, crie um vetor para guardar o xy a cada avanço. E para obter o melhor caminho possível, é só você procurar duplicatas de xy e remover esses segmentos Commented 26/08/2018 às 0:16

1 Resposta 1

1

Não estudei o seu código a fundo, mas me pareceu ser muito mais complicado que o necessário. Executando ele neste pequeno labirinto que você deu, ele estoura o tempo limite.

Uma abordagem mais simples é a de usar a busca em profundidade. Ela é boa especialmente para resolver labirintos.

A ideia da busca em profundidade é fazer mais ou menos como a lenda grega de Teseu no labirinto de Creta. Com um novelo de lã, vá traçando o caminho percorrido e quando quiser voltar para tentar outro caminho, recolha a lã de volta para o novelo.

O algoritmo da busca em profundidade é recursivo: Em um determinado lugar, tente seguir por um caminho o máximo que puder, retornando sempre que não puder prosseguir. Se não der por esse caminho, tente por outro, retornando sempre que não puder prosseguir. Se nenhum caminho do lugar onde você está leva a lugar nenhum, então dê um passo atrás para tentar outro caminho.

Utilizarei <, >, v e ^ para traçar o caminho.

A implementação fica assim:

int labirinto(int x_atual, int y_atual, char **maze, int largura, int altura) {
    // Se tentou sair do labirinto, este não é o caminho certo.
    if (x_atual < 0 || x_atual >= largura || y_atual < 0 || y_atual >= altura) return 0;

    char aqui = maze[x_atual][y_atual];

    // Verifica se achou a saída.
    if (aqui == 'S') return 1;

    // Se bateu na parede ou voltou para algum lugar que já esteve,
    // então este não é o caminho certo.
    if (aqui == 'X' || aqui == '>' || aqui == '<' || aqui == 'v' || aqui == '^') return 0;

    // Tenta ir para cima.
    maze[x_atual][y_atual] = '^';
    if (labirinto(x_atual, y_atual + 1, maze, largura, altura)) return 1;

    // Tenta ir para baixo.
    maze[x_atual][y_atual] = 'v';
    if (labirinto(x_atual, y_atual - 1, maze, largura, altura)) return 1;

    // Tenta ir para a esquerda.
    maze[x_atual][y_atual] = '<';
    if (labirinto(x_atual - 1, y_atual, maze, largura, altura)) return 1;

    // Tenta ir para a direita.
    maze[x_atual][y_atual] = '>';
    if (labirinto(x_atual + 1, y_atual, maze, largura, altura)) return 1;

    // Não deu, então volta.
    maze[x_atual][y_atual] = 'O';   
    return 0;
}

No main, só algumas poucas mudanças são necessárias:

int main(void) {
    int largura, altura, x_entrada, y_entrada;
    scanf("%d %d\n", &largura, &altura);
    char **a = malloc(largura * sizeof(char*));
    for (int x = 0; x < largura; x++) {
        a[x] = malloc(altura * sizeof(char));
    }
    for (int y = altura - 1; y >= 0; y--) {
        for (int x = 0; x < largura; x++) {
            a[x][y] = getchar();
            if (a[x][y] == 'E') {
                x_entrada = x;
                y_entrada = y;
            }
        }
        getchar(); //pegar a quebra de linha
    }
    printf("Entrada:\n");
    print_maze(a, largura, altura);
    labirinto(x_entrada, y_entrada, a, largura, altura);
    printf("\nSaída:\n");
    print_maze(a, largura, altura);
    return 0;
}

O resultado foi esse:

Entrada:
XOSXX
OOOXX
OXXXX
OXXOX
OXXOX
OOOEX

Saída:
X>SXX
>^OXX
^XXXX
^XXOX
^XXOX
^<<<X

Veja aqui funcionando no ideone.

Ainda falta imprimir o caminho da forma como você precisa. Mas tendo o labirinto do jeito que está, basta ir rastreando os <, >, ^ e v e você deve conseguir isso facilmente.

Tentei também com um labirinto maior e deu certo também:

Entrada:
OOOOOOOOOO
OXXOXXOXXO
OOXOOXOXXX
XOXXXXSXOO
OOOXOXXXOX
XOXXOOOOOX
OOXXOXXXEX
OXXXOOOXXX
OXOXOXOOOO
OOOOOXOXOX

Saída:
>>>>>>vOOO
^XXOXXvXXO
^<XOOXvXXX
X^XXXXSXOO
O^OXOXXXOX
X^XXv<<<<X
>^XXvXXX^X
^XXXvOOXXX
^XOXvXOOOO
^<<<<XOXOX

Veja aqui 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 .