Skip to main content
2 de 4
Outro labirinto.
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189

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

Veja aqui funcionando no ideone.

Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189