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

C

25/08/2018

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

Curtidas 0
POSTAR