Find and show the way - maze in C

Question

Guys, someone can help me. I need to implement a recursive function that gets a maze and a current position.

The labyrinth is given by an array of characters ("char") where ːX' represents a wall, ?0' represents a path, ?E' represents the input and’S' represents the output. The goal is to print on the screen a valid path that leads from the entrance to the exit, this path does not need to be the shortest, but it cannot go twice through the same house. The labyrinth is indexed by [0 .. largura – 1][0 .. altura – 1], where width and height are the number of houses on the X axis and on the Y axis respectively, for example, the labyrinth below has width 5 and height 6. The entrance is in the house (3, 0) and the exit in the house (2,5):

XOSXX
OOOXX
OXXXX
OXXOX
OXXOX
OOOEX

An example of a solution to this problem would be the following way: (3, 0)(2, 0)(1, 0)(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)(1, 4)(1, 5)(2, 5)

My question is how can I be printing on the screen a path that leads from the entrance to the exit. Code so far:

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

Answer 1

I didn’t study your code in depth, but it seemed to me to be much more complicated than necessary. Running it in this little maze you gave it, it bursts the time limit.

A simpler approach is to use the deep-sea search. She’s especially good at solving mazes.

The idea of searching in depth is to do more or less like the Greek legend of Theseus in the labyrinth of Crete. With a skein of wool, trace your way around and when you want to go back to try another way, collect the wool back into the skein.

The depth search algorithm is recursive: In a given place, try to go as far as you can, returning whenever you can’t go on. If you don’t find that way, try another way, returning whenever you can’t go on. If no path from where you are leads anywhere, then take a step back to try another way.

I will use <, >, v and ^ to trace the way.

The implementation is thus:

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

In the main, only a few changes are needed:

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

The result was this:

Entrada:
XOSXX
OOOXX
OXXXX
OXXOX
OXXOX
OOOEX

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

See here working on ideone.

Still have to print the way as you need. But having the maze the way it is, just go tracking the <, >, ^ and v and you should achieve this easily.

I also tried with a bigger maze and it worked too:

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

See here working on ideone.