Não estudei o seu código a fundo, mas me pareceu ser muito mais complicado que o necessário. Executando ele neste pequeno labirinto que você deu, ele estoura o tempo limite.
Uma abordagem mais simples é a de usar a busca em profundidade. Ela é boa especialmente para resolver labirintos.
A ideia da busca em profundidade é fazer mais ou menos como a lenda grega de Teseu no labirinto de Creta. Com um novelo de lã, vá traçando o caminho percorrido e quando quiser voltar para tentar outro caminho, recolha a lã de volta para o novelo.
O algoritmo da busca em profundidade é recursivo: Em um determinado lugar, tente seguir por um caminho o máximo que puder, retornando sempre que não puder prosseguir. Se não der por esse caminho, tente por outro, retornando sempre que não puder prosseguir. Se nenhum caminho do lugar onde você está leva a lugar nenhum, então dê um passo atrás para tentar outro caminho.
Utilizarei <
, >
, v
e ^
para traçar o caminho.
A implementação fica assim:
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;
}
No main
, só algumas poucas mudanças são necessárias:
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;
}
O resultado foi esse:
Entrada:
XOSXX
OOOXX
OXXXX
OXXOX
OXXOX
OOOEX
Saída:
X>SXX
>^OXX
^XXXX
^XXOX
^XXOX
^<<<X
Veja aqui funcionando no ideone.
Ainda falta imprimir o caminho da forma como você precisa. Mas tendo o labirinto do jeito que está, basta ir rastreando os <
, >
, ^
e v
e você deve conseguir isso facilmente.
Tentei também com um labirinto maior e deu certo também:
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