-
Notifications
You must be signed in to change notification settings - Fork 0
/
maze.h
107 lines (74 loc) · 2.09 KB
/
maze.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#ifndef MAZE_H
#define MAZE_H
#include <vector>
#include <stack>
#include <queue>
#include "png.h"
#include "dsets.h"
using namespace std;
class SquareMaze
{
public:
/*
* No parameter constructor
*/
SquareMaze();
/*
* Makes a new Square Maze of the given height and width.
*/
void makeMaze(int width, int height);
/*
* This uses your representation of the maze to determine whether it is possible
* to travel in the given direction from the square at the coordinates (x,y)
*/
bool canTravel(int x, int y, int dir) const;
/*
* Sets a specified wall within a cell to exist or not exist (based on parameter)
*/
void setWall(int x, int y, int dir, bool exists);
/*
* Solves this SquareMaze.
*/
std::vector<int> solveMaze();
/*
* Draws the maze without the solution.
*/
PNG * drawMaze() const;
/*
* This function calls drawMaze(), then solveMaze(); modifies the PNG from
* drawMaze() to show the solution path and the exit.
*/
PNG * drawMazeWithSolution();
private:
/*
* nested Cell class
*/
class Cell
{
public:
// Each cell has 2 walls, right & down.
// Left & up walls can be accessed from adjacent cells
bool hasRightWall;
bool hasDownWall;
// Number corresponding to place in disjoint set
int cellNumber;
// Constructor -- no parameters
Cell();
// Constructor -- param given to initialize cellNumber
Cell(int number);
};
int mazeWidth;
int mazeHeight;
int initialCellNum;
vector< vector<Cell> > grid; // grid implementation that holds the Cells
DisjointSets cellDSet;
// Helper function used by makeMaze()
void makeMazeHelper(int x, int y);
// Helper function -- determines if a cell is within bounds and hasn't been checked yet
bool isGood(int x, int y);
// Helper function used by drawMaze() -- draws walls for each cell
void drawWall(int x, int y, PNG * output) const;
// Helper function used by solveMaze() -- checks if a cell has been visited
bool visited(int x, int y, DisjointSets &visitedCells);
};
#endif