Skip to main content
adicionou 5 caracteres ao conteúdo
Fonte Link
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189

Uma abordagem mais simples é a de usar a busca em profundidade. Ela é boa especialmente para resolver labirintos.

Uma abordagem mais simples é usar a busca em profundidade. Ela é boa especialmente para resolver labirintos.

Uma abordagem mais simples é a de usar a busca em profundidade. Ela é boa especialmente para resolver labirintos.

Explicação sobre a busca em profundidade.
Fonte Link
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189

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.

Utilizarei <, >, v e ^ para traçar o caminho.

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.

Outro labirinto.
Fonte Link
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189
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.,
    // Esteentã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;
}

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.

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

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.

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

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.

Fonte Link
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189
Carregando