Achar saída de um labirinto e imprimir o caminho.[ C ]

25/08/2018

0

C

Galera alguem pode me ajuda , 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 duvida é 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);
}
Pedro

Pedro

Responder

Que tal ter acesso a um e-book gratuito que vai te ajudar muito nesse momento decisivo?

Ver ebook

Recomendado pra quem ainda não iniciou o estudos.

Eu quero
Ver ebook

Recomendado para quem está passando por dificuldades nessa etapa inicial

Eu quero

Utilizamos cookies para fornecer uma melhor experiência para nossos usuários, consulte nossa política de privacidade.

Aceitar