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.