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.