Travessia de labirinto. A grade a seguir é uma representação
do array de duplo subscrito de um labirinto.
Os símbolos # representam as paredes do labirinto, e os
pontos (.) representam quadrados pelo caminho que,
possivelmente, levam à saída do labirinto.
Existe um algoritmo simples usado para percorrer o labirinto
que garante que encontremos a saída (supondo que
exista uma). Se não existir uma saída, você chegará ao
ponto de partida novamente. Coloque sua mão direita na
parede à sua direita e comece a caminhar para a frente.
Nunca remova sua mão da parede. Se o labirinto virar
para a direita, você seguirá a parede para a direita. Desde
que não remova sua mão da parede, por fim você chegará
à saída do labirinto. Pode ser que haja um caminho mais
curto que aquele que você tomou, mas o mais longo garante
sua saída do labirinto.
Escreva a função recursiva mazeTraverse para percorrer
o labirinto. A função deverá receber como argumentos
um array de 12 por 12 caracteres que represente o
labirinto e o local em que labirinto começa. À medida
que mazeTraverse tenta localizar a saída do labirinto,
ele deverá colocar o caractere X em cada quadrado no
caminho. A função deverá exibir o labirinto após cada
movimento para que o usuário possa observar enquanto
o labirinto é resolvido.
Passo 1
Neste exercício, escreveremos um programa que encontrará uma saída para um labirinto de 12por 12caracteres
Esta é uma tarefa bastante complicada e há mais de uma maneira de resolvê-la. Usaremos uma abordagem, seguindo as instruções da tarefa tanto quanto possível.
Primeiro, incluiremos a biblioteca stdio.h e declararemos duas variáveis globais startX e startY.
Qualquer parte deste programa terá acesso a essas duas variáveis e poderá alterá-las.
Também escreveremos o protótipo da função para a função recursiva mazeTraverse(). Conforme instruído na tarefa, esta função terá como argumentos o array (o labirinto) e dois inteiros representando uma posição no labirinto. No entanto, se quisermos implementar o algoritmo que segue a parede à direita, devemos adicionar mais um parâmetro a esta função, que é a direção.
Como limitamos a função a esses quatro parâmetros, tivemos que definir essas variáveis globais.
Também definiremos quatro macros que representarão as quatro direções possíveis. É importante para o algoritmo que as direções sejam representadas com esses valores (ou alguns outros valores sequenciais, mas na mesma ordem).
#include "stdio.h"
#define RIGHT 3
#define DOWN 2
#define LEFT 1
#define UP 0
int startX, startY;
int mazeTraverse(char maze[][12], int currentX, int currentY, int direction);
Passo 2
Na função main(), leremos os caracteres que o usuário digitará que representarão o labirinto.
Vamos armazená-los em um array de 1212 por 1212 caracteres chamado maze.
Depois disso, usaremos um loop for para verificar todos os caracteres externos do array para encontrar a posição inicial. Vamos definir as variáveis startX e startY para os subscritos deste elemento. Dependendo da posição inicial, também definiremos a direção para uma das quatro direções possíveis.
No final da função main(), passaremos o array do labirinto e as variáveis startX e startY para a função recursiva mazeTraverse(). O valor da direção também será passado.
int main()
{
char maze[12][12];
for (int i = 0; i
for (int j = 0; j
scanf(" %c", &maze[i][j]);
}
}
puts("");
int direction;
for (int i = 1; i
if (maze[0][i] == '.') {
startX = 0;
startY = i;
direction = DOWN;
break;
}
else if (maze[11][i] == '.') {
startX = 11;
startY = i;
direction = UP;
break;
}
else if (maze[i][0] == '.') {
startX = i;
startY = 0;
direction = RIGHT;
break;
}
else if (maze[i][11] == '.') {
startX = i;
startY = 11;
direction = LEFT;
break;
}
}
mazeTraverse(maze, startX, startY);
}
Agora, vamos escrever a função mazeTraverse().
São necessários quatro parâmetros: maze - uma matriz de caracteres, currentX - integer, currentY - integer e direction - integer
No início desta função, definiremos o valor do elemento atual do labirinto para o caractere X.
Logo em seguida, exibiremos o conteúdo do array do labirinto, para que o usuário possa acompanhar passo a passo como a saída está sendo encontrada.
void mazeTraverse(char maze[][12], int currentX, int currentY, int direction)
{
// placing X at current position
maze[currentX][currentY] = 'X';
// displaying the current path
for (int i = 0; i
for (int j = 0; j
printf("%c ", maze[i][j]);
}
printf("\n");
}
puts("");
Passo 3
Em seguida, na função mazeTraverse(), verificaremos se estamos atualmente na posição de saída. Para isso, verificaremos se o valor currentX ou currentY é igual a 0 ou 11, pois são subscritos nas bordas do array. Outra condição é que o outro valor seja diferente do valor startX ou startY. Para ter certeza de que não estamos na posição inicial.
Se a saída for encontrada, exibiremos uma mensagem indicando isso e a função retornará, o que encerrará todas as outras chamadas recursivas também.
if (((currentX == 0 || currentX == 11) && currentY != startY) ||
((currentY == 0 || currentY == 11) && currentX != startX)) {
printf("\n\nExit found!!!\n");
return;
}
Se a posição atual não for uma posição de saída, usaremos um loop for para verificar as quatro direções possíveis. As direções possíveis são DIREITA, CIMA, ESQUERDA e BAIXO. Vamos verificá-los nessa ordem, já que a variável nextDirection é incrementada, o que significa que ela mudará nessa ordem. Esta ordem é crucial para o bom funcionamento do algoritmo.
Antes de percorrer uma direção, vamos nos certificar de que existe um caminho (o caractere deve ser . ou X). Também devemos ter certeza de que não estamos saindo dos limites do array.
Após cada chamada recursiva para a função mazeTraverse(), há uma instrução de retorno que será executada para encerrar a função assim que a saída for encontrada.
else {
int nextDirection = direction;
for(int i = 0; i
// go right if possible
if (nextDirection == RIGHT) {
if (currentY + 1
&& maze[currentX][currentY + 1] != '#') {
mazeTraverse(maze, currentX,
currentY + 1, DOWN);
return;
}
}
// go left if possible
else if (nextDirection == LEFT) {
if (currentY - 1 >= 0
&& maze[currentX][currentY - 1] != '#') {
mazeTraverse(maze, currentX,
currentY - 1, UP);
return;
}
}
// go up if possible
else if (nextDirection == UP) {
if (currentX - 1 >= 0
&& maze[currentX - 1][currentY] != '#') {
mazeTraverse(maze, currentX - 1,
currentY, RIGHT);
return;
}
}
// go down if possible
else if (nextDirection == DOWN) {
if (currentX + 1
&& maze[currentX + 1][currentY] != '#') {
mazeTraverse(maze, currentX + 1,
currentY, LEFT);
return;
}
}
// update the next direction for next iteration
nextDirection = (nextDirection + 1) % 4;
}
}
}
Uma coisa importante a ser observada no código da etapa anterior é que o valor nextDirection é incrementado, o que significa que as direções são verificadas na seguinte ordem: RIGHT, UP, LEFT, DOWN.
No entanto, por exemplo, se o valor de nextDirection for RIGHT, passamos o valor DOWN como direção para a próxima variável, que é igual a RIGHT - 11. Podemos dizer que passamos o valor de nextDirection decrementado.
A razão para isso é lógica. Por exemplo. se estamos subindo no labirinto, estamos seguindo a parede à nossa direita. Quando precisarmos fazer uma curva, primeiro verificaremos a direção DIREITA, porque essa é a primeira direção que a parede à direita pode seguir.
Resposta
#include "stdio.h"
#define UP 0
#define RIGHT 3
#define DOWN 2
#define LEFT 1
int startX, startY;
void mazeTraverse(char maze[][12], int currentX, int currentY, int direction)
{
maze[currentX][currentY] = 'X';
for (int i = 0; i
for (int j = 0; j
printf("%c ", maze[i][j]);
}
printf("\n");
}
puts("");
if (((currentX == 0 || currentX == 11) && currentY != startY) ||
((currentY == 0 || currentY == 11) && currentX != startX)) {
printf("\n\nExit found!!!\n");
return;
}
else {
int nextDirection = direction;
for(int i = 0; i
if (nextDirection == RIGHT) {
if (currentY + 1
&& maze[currentX][currentY + 1] != '#') {
mazeTraverse(maze, currentX,
currentY + 1, DOWN);
return;
}
}
else if (nextDirection == LEFT) {
if (currentY - 1 >= 0
&& maze[currentX][currentY - 1] != '#') {
mazeTraverse(maze, currentX,
currentY - 1, UP);
return;
}
}
else if (nextDirection == UP) {
if (currentX - 1 >= 0
&& maze[currentX - 1][currentY] != '#') {
mazeTraverse(maze, currentX - 1,
currentY, RIGHT);
return;
}
}
else if (nextDirection == DOWN) {
if (currentX + 1
&& maze[currentX + 1][currentY] != '#') {
mazeTraverse(maze, currentX + 1,
currentY, LEFT);
return;
}
}
nextDirection = (nextDirection + 1) % 4;
}
}
}
int main()
{
char maze[12][12];
for (int i = 0; i
for (int j = 0; j
scanf(" %c", &maze[i][j]);
}
}
puts("");
int direction;
for (int i = 1; i
if (maze[0][i] == '.') {
startX = 0;
startY = i;
direction = DOWN;
break;
}
else if (maze[11][i] == '.') {
startX = 11;
startY = i;
direction = UP;
break;
}
else if (maze[i][0] == '.') {
startX = i;
startY = 0;
direction = RIGHT;
break;
}
else if (maze[i][11] == '.') {
startX = i;
startY = 11;
direction = LEFT;
break;
}
}
mazeTraverse(maze, startX, startY, direction);
}