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 é 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.
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