Find and show the way - labyrinth in C

I did not study your code thoroughly, but it seemed to me much more complicated than necessary. Running it in this little maze you gave, it bursts the timeout.

A simpler approach is to use the search in depth . She is 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 Cretan maze. With a ball of wool, trace the path traveled and when you want to go back to try another path, collect the wool back to the ball.

The search algorithm in depth is recursive: In a given place, try to follow a path as far as it can, returning whenever it can not proceed. If you do not go that way, try for another, returning whenever you can not proceed. If no path from where you are leads to nowhere, then step back to try another path.

I will use < , > , v and ^ to plot the path.

The implementation looks like this:

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% w / w, only a few changes are required:

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.

The way you need to print is still missing. But having the labyrinth just the way it is, you just have to crawl the main , < , > and ^ and you should get it easily.

I also tried a larger labyrinth and it worked out 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.