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);
}