Achar sa�da de um labirinto e imprimir o caminho.[ 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

Curtir t�pico + 0

Responder