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

}