Labirintos de qualquer tamanho. Generalize as funções mazeTraverse e mazeGenerator dos exercícios 7.22 e 7.23 para processar labirintos de qualquer largura e altura.

Passo 1

Nos dois exercícios anteriores, escrevemos duas funções recursivas chamadas mazeTraverse() e mazeGenerator().

A função mazeTraverse() recebe um array char com subscrito duplo como um dos parâmetros e esse array representa o labirinto para o qual encontra a saída seguindo sempre a parede à direita.

A função mazeGenerator() também recebe um array de caracteres com subscrito duplo como um dos parâmetros e gera um labirinto aleatório.

Ambas as funções usam um array de tamanho 1212-by1212 e vamos mudar isso neste exercício, para que possamos gerar e percorrer arrays de vários tamanhos.

Passo 2

Como sabemos, não podemos usar variáveis ao definir o array, então isso não é uma opção agora. Não poderemos escrever um programa que pergunte ao usuário qual é o tamanho do array que representa o labirinto.

No entanto, vamos generalizar o código para que possamos simplesmente ajustar o tamanho do array. Usaremos macros para isso. Cada valor constante que representa o tamanho do array será substituído por uma dessas duas macros.

#define Xn

#define Y m

O n e m representam valores inteiros constantes, que descrevem o comprimento e a largura do labirinto. Dessa forma, podemos alterar o tamanho do array facilmente e o código ainda funcionará. No entanto, devemos primeiro substituir todos os valores constantes usados em nossos programas.

O programa para atravessar o labirinto

Vamos definir as duas novas macros no início do programa.

Na função mazeTraverse(), substituiremos cada ocorrência do número 1212 por X ou Y. Qual macro usaremos depende se a condição está se referindo ao comprimento ou à largura do labirinto.

Vamos demonstrar isso no cabeçalho da função.

void mazeTraverse(char maze[X][Y], int currentX, int currentY, int direction)

Devemos substituir valores constantes como 11 por X−1 também, pois esses valores também dependem do tamanho do array.

Passo 3

O programa usado para gerar um labirinto aleatório

Como no programa anterior, definiremos as duas macros no início.

Substituiremos cada valor constante conectado ao tamanho da matriz pela macro X ou Y.

A maioria desses valores constantes são os números 12 e 11 e vamos substituí-los por, por exemplo, X ou Y−1.

Passo 6

6 de 9

The complete code:

#include "stdio.h"

#include "stdlib.h"

#include "time.h"

#define X 15

#define Y 17

#define UP 0

#define LEFT 1

#define DOWN 2

#define RIGHT 3

void generateMaze(char maze[X][Y], int* x, int* y, int* end);

int main()

{

char maze[X][Y];

int start[2] = { -1, -1 };

int exit[2] = { -1, -1 };

srand(time(NULL));

for (int i = 0; i

for (int j = 0; j

maze[i][j] = '#';

}

}

generateMaze(maze, &start[0], &start[1], exit);

printf("Start: (%d, %d)\n", start[0], start[1]);

printf("Exit: (%d, %d)\n\n", exit[0], exit[1]);

for (int i = 0; i

for (int j = 0; j

printf("%c ", maze[i][j]);

}

printf("\n");

}

printf("\n");

}

void generateMaze(char maze[X][Y], int* x, int* y, int* exit)

{

if (exit[0] == -1 && exit[1] == -1 && *x == -1 && *y == -1) {

*x = rand() % X - 2 + 1;

*y = 0;

exit[0] = rand() % X - 2 + 1;

exit[1] = Y - 1;

maze[*x][*y] = '.';

maze[exit[0]][exit[1]] = '.';

}

if(*x != X - 1 && *y != Y - 1 && *x != 0 && *y != 0)

maze[*x][*y] = '.';

int randomDirections[4] = { UP, DOWN, RIGHT, LEFT };

for (int i = 0; i

int random = rand() % 4;

int tmp = randomDirections[i];

randomDirections[i] = randomDirections[random];

randomDirections[random] = tmp;

}

for (int i = 0; i

int offsetX = 0, offsetY = 0;

switch (randomDirections[i]) {

case UP:

offsetY = -1; break;

case LEFT:

offsetX = -1; break;

case DOWN:

offsetY = 1; break;

case RIGHT:

offsetX = 1; break;

}

int x2 = *x + 2 * offsetX;

int y2 = *y + 2 * offsetY;

if (x2 >= 0 && x2 = 0 && y2

if (maze[x2][y2] == '#' || (x2 == exit[0] && y2 == exit[1])) {

if (*x + offsetX != X - 1 && *y + offsetY != Y - 1

&& *x + offsetX != 0 && *y + offsetY != 0) {

maze[*x + offsetX][*y + offsetY] = '.';

generateMaze(maze, &x2, &y2, exit);

}

}

}

}

}

Agora, vamos testar essas duas funções. Vamos definir os valores das duas macros para 10 e 15.

Primeiro, vamos gerar um labirinto aleatório e depois vamos atravessá-lo.

Gerando um labirinto aleatório usando a função mazeGenerator():

Resposta

Ver o desenvolvimento.