Добрый вечер. Очень нужна ваша помощь. Нужно реализовать все функции в виде методов. Дополнительно реализовать ввод и вывод данных через операторы << и >>, конструктор == и !=. и оператор сравнения == и !=.
Разделять реализацию и интерфейс класса на 2 файла обязательно(ClassName.h, ClassName.cpp)
Создать программу, отыскивающую проход по лабиринту. Лабиринт
представляется в виде матрицы, состоящей из квадратов. Каждый
квадрат либо открыт, либо закрыт. Вход в закрытый квадрат
запрещен. Если квадрат открыт, то вход в него возможен со
стороны, но не с угла. Каждый квадрат определяется его
координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного
входа. После отыскания прохода программа выводит найденный
путь в виде координат квадра- тов. Для хранения пути использовать
стек.
Код:
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <limits>
template <class T>
class Stack {
public:
Stack() : head(0), size(0) {}
Stack(const Stack& other) : head(0), size(0) {
copyFrom(other);
}
virtual ~Stack() {
clear();
}
void copyFrom(const Stack &other) {
clear();
Node *otherNode = other.head;
Node *lastNode = 0;
while (otherNode != 0) {
Node *newNode = new Node(otherNode->value, 0);
if (lastNode == 0)
head = lastNode;
else
lastNode->next = newNode;
lastNode = newNode;
otherNode = otherNode->next;
++size;
}
}
void push(const T &value) {
head = new Node(value, head);
++size;
}
T pop() {
if (isEmpty()) throw std::underflow_error("stack is empty");
T result = head->value;
Node *newHead = head->next;
delete head;
head = newHead;
--size;
return result;
}
const T &top() const {
if (isEmpty()) throw std::underflow_error("stack is empty");
return head->value;
}
int isEmpty() const { return head == 0; }
int getSize() const { return size; }
void clear() {
while (head != 0) {
Node *newHead = head->next;
delete head;
head = newHead;
}
size = 0;
}
private:
Stack &operator=(const Stack&);
struct Node {
T value;
Node *next;
Node(const T &value, Node *next) : value(value), next(next) {}
};
Node *head;
int size;
};
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
};
std::ostream &operator<<(std::ostream &stream, const Point &p) {
return stream << "[" << p.x << ":" << p.y << "]";
}
class Maze {
public:
Maze(int height, int width) : height(height), width(width),
maze(createMatrix(height, width, 0)) {}
virtual ~Maze() {
deleteMatrix(maze, height);
}
void generate() {
Stack<Point> points;
points.push(Point(width / 2, height / 2));
while (!points.isEmpty()) {
Point thisPoint = points.pop();
int rnd = rand() % 2;
int shiftX = rnd ? ((rand() % 2) ? -1 : 1) : 0;
int shiftY = rnd ? 0 : ((rand() % 2) ? -1 : 1);
if (thisPoint.x + shiftX * 2 > -1 && thisPoint.x + shiftX * 2 < width &&
thisPoint.y + shiftY * 2 > -1 && thisPoint.y + shiftY * 2 < height &&
!maze[thisPoint.y + shiftY * 2][thisPoint.x + shiftX * 2]) {
maze[thisPoint.y + shiftY][thisPoint.x + shiftX] = 1;
thisPoint.x += shiftX * 2;
thisPoint.y += shiftY * 2;
for (int i = 0; i < 10; ++i)
points.push(Point(thisPoint.x, thisPoint.y));
maze[thisPoint.y][thisPoint.x] = 1;
}
}
maze[0][0] = maze[height - 1][width - 1] = 1;
}
Stack<Point> getSolution() const {
static const Point shifts[] = {Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0)};
int **solutionMatrix = createSolutionMatrix();
Stack<Point> stack;
if (solutionMatrix[height - 1][width - 1] < std::numeric_limits<int>::max()) {
Point point(width - 1, height - 1);
stack.push(point);
do {
int thisValue = solutionMatrix[point.y][point.x];
for (const Point *shift = shifts; shift < shifts + 4; ++shift) {
Point thisPoint = point + *shift;
if (thisPoint.x > -1 && thisPoint.y > -1 &&
thisPoint.x < width && thisPoint.y < height &&
solutionMatrix[thisPoint.y][thisPoint.x] == thisValue - 1) {
point = thisPoint;
stack.push(point);
break;
}
}
} while (point.x != 0 || point.y != 0);
}
deleteMatrix(solutionMatrix, height);
return stack;
}
int get(int y, int x) const { return maze[y][x]; }
int getHeight() const { return height; }
int getWidth() const { return width; }
private:
Maze(const Maze&);
Maze &operator=(const Maze&);
static int **createMatrix(int height, int width, int defaultValue) {
int **maze = new int*[height];
for (int i = 0; i < height; ++i) {
maze[i] = new int[width];
for (int j = 0; j < width; ++j) {
maze[i][j] = defaultValue;
}
}
return maze;
}
static void deleteMatrix(int **matrix, int height) {
for (int i = 0; i < height; ++i)
delete [] matrix[i];
delete [] matrix;
}
int **createSolutionMatrix() const {
static const Point shifts[] = {Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0)};
int **matrix = createMatrix(height, width, std::numeric_limits<int>::max());
Stack<Point> stack;
matrix[0][0] = 0;
stack.push(Point(0, 0));
while (!stack.isEmpty()) {
Point point = stack.pop();
int value = matrix[point.y][point.x];
for (const Point *shift = shifts; shift < shifts + 4; ++shift) {
Point thisPoint = point + *shift;
if (thisPoint.x > -1 && thisPoint.x < width &&
thisPoint.y > -1 && thisPoint.y < height &&
matrix[thisPoint.y][thisPoint.x] > value + 1 &&
maze[thisPoint.y][thisPoint.x]) {
matrix[thisPoint.y][thisPoint.x] = value + 1;
stack.push(thisPoint);
}
}
}
return matrix;
};
int height;
int width;
int **maze;
};
std::ostream &operator<<(std::ostream &stream, const Maze &maze) {
for (int j = 0; j < maze.getWidth() + 2; ++j) stream << '#';
stream << std::endl;
for (int i = 0; i < maze.getHeight(); ++i) {
stream << '#';
for (int j = 0; j < maze.getWidth(); ++j) {
stream << ((maze.get(i, j)) ? ' ' : '#');
}
stream << '#' << std::endl;
}
for (int j = 0; j < maze.getWidth() + 2; ++j) stream << '#';
stream << std::endl;
return stream;
}
int main(int argc, char **argv) {
srand(time(0));
// значения лучше подбирать опытным путем
Maze maze(9, 21);
maze.generate();
std::cout << maze << std::endl;
Stack<Point> result = maze.getSolution();
while (!result.isEmpty()) {
Point point = result.pop();
std::cout << point << (result.isEmpty() ? "\n" : "->");
}
std::cin.get();
return 0;
}