Понятие «лабиринт» известно во всём мире с древних времён. Лабиринты всегда несли ощущение тайны и загадки. Один из первых лабиринтов, известных человечеству, - древнеегипетский лабиринт, в котором было около 3000 комнат – полторы тысячи наземных и столько же подземных помещений. Со временем лабиринты утратили своё религиозно-мистическое значение. В наши дни лабиринты используются в основном как развлекательный предмет.
Лабиринт – это какая-либо структура, состоящая из запутанных путей к выходу, которые могут также привести в тупик.
Лабиринты, не содержащие замкнутых маршрутов, т.е. таких, которые образуют замкнутую петлю (например, лабиринт, изображенный слева), называются «односвязными». Односвязный лабиринт - это лабиринт без отдельно стоящих стенок. Лабиринты с отдельно стоящими стенками содержат замкнутые маршруты в виде петли и называются «многосвязными» (таков, например, лабиринт на рис. 1 справа). При этом многосвязные лабиринты можно разделить на две группы: с петлёй, окружающей центр лабиринта или же с петлей, не окружающей его.
Есть 4 метода прохождения лабиринтов:
*Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведёт вас в тупик, то возвращайтесь назад и начинайте все сначала.
*Второй метод – МЕТОД ЗАЧЁРКИВАНИЯ ТУПИКОВ. Начнём последовательно зачёркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачёркнутая часть коридора будет выходом или маршрутом от входа к выходу или к центру.
*Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту нужно двигаться, не отрывая одной руки (правой или левой) от стены. Это правило не универсальное, но часто полезное. Им пользуются тогда, когда все стены хотя и имеют сложные повороты и изгибы, но составляют непрерывное продолжение наружной стены. Лабиринт должен быть односвязным.
*Четвёртый метод является универсальным алгоритмом прохождения любых лабиринтов и известен как алгоритм Люка-Тремо. Суть алгоритма заключается в следующем: выйдя из любой точки лабиринта, надо сделать отметку на стене или полу (в нашем случае это точка) и двигаться в произвольном направлении до тупика или перекрёстка; если перед вами тупик, то нужно вернуться назад и поставить крест, блокирующий путь, и идти в направлении, не пройденном ни разу, или пройденном один раз; если перекрёсток - идти по произвольному направлению, отмечая каждый перекрёсток на входе и на выходе точкой; если на перекрёстке точка уже имеется, то следует идти по чистому пути, если нет чистых путей – то по пути с точкой, заменив предварительно точку на крест. Мы разработали программу, в которой реализовали этот метод.
Код программы на C++:
#include <iostream>
using namespace std;
int height, width; // Size
int** maze; // Stores the maze (1 = path, 2 = wall)
bool** wasHere; // Strores visited cells
bool** correctPath; // Stores correct path
int startX, startY; // Beginning
int endX, endY; // Finish
bool solveMaze(void);
bool recursiveSolve(int, int);
bool solveMaze() {
// Initialization of matrices
for (int row = 0 ; row < height; row++) {
for (int col = 0; col < width; col++) {
wasHere[row][col] = false;
correctPath[row][col] = false;
}
}
return recursiveSolve(startX, startY);
}
bool recursiveSolve(int x, int y) {
// If in the end
if (x == endX && y == endY) {
wasHere[y][x] = true;
correctPath[y][x] = true;
return true;
}
// If on the wall or the cell was visited
if (maze[y][x] == 2 || wasHere[y][x]) {
return false;
}
wasHere[y][x] = true;
if (x != 0) { // Check if not on left edge
if (recursiveSolve(x-1, y)) { // Recalls method one to the left
correctPath[y][x] = true; // Sets that path value to true;
return true;
}
}
if (x != width - 1) { // Checks if not on right edge
if (recursiveSolve(x+1, y)) { // Recalls method one to the right
correctPath[y][x] = true;
return true;
}
}
if (y != 0) { // Checks if not on top edge
if (recursiveSolve(x, y-1)) { // Recalls method one up
correctPath[y][x] = true;
return true;
}
}
if (y != height - 1) { // Checks if not on bottom edge
if (recursiveSolve(x, y+1)) { // Recalls method one down
correctPath[y][x] = true;
return true;
}
}
return false;
}
int main() {
cout « "Enter the height of the maze" « endl;
cin » height;
cout « "Enter the width of the maze" « endl;
cin » width;
// Initialization of matrices
maze = new int*[height];
for (int i = 0; i < height; i++) {
maze[i] = new int[width];
}
wasHere = new bool*[height];
for (int i = 0; i < height; i++) {
wasHere[i] = new bool[width];
}
correctPath = new bool*[height];
for (int i = 0; i < height; i++) {
correctPath[i] = new bool[width];
}
cout « "Enter the maze" « endl;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
cin » maze[i][j];
}
}
// IMPORTANT: Coordinates start from 1
cout « "Enter the start row" « endl;
cin » startY;
startY--;
cout « "Enter the start column" « endl;
cin » startX;
startX--;
cout « "Enter the end row" « endl;
cin » endY;
endY--;
cout « "Enter the end column" « endl;
cin » endX;
endX--;
if (!solveMaze()) {
cout « "No solution" « endl;
}
else {
cout « "The path is:" « endl;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
cout « correctPath[i][j] « " ";
}
cout « endl;
}
}
return 0;
}
Работает программа следующим образом:
В программу вводится лабиринт, длину и ширину которого задаёт пользователь.
В результате в программе задаётся прямоугольник с произвольными сторонами. Здесь приведён лабиринт 10х10, в котором возможные пути обозначены единицами, а стены – цифрами 2.
Далее задаются координаты входа и выхода из лабиринта, и программа ищет выход из него, используя метод Люка-Тремо.
Несмотря на то, что лабиринты появились, изучались и изучаются людьми уже очень долгое время, нам кажется, что эта область изучена не полностью, и люди могут узнать о них ещё больше, если будут интересоваться этой темой. Мы постарались заинтересовать вас и надеемся, что у нас получилось.
Над статьёй работали студенты Московского государственного технического университета гражданской авиации
Корякина М.А., Зайцев Д.С.
Научный руководитель - к.ф.-м.н., доц.,зав. Каф. ВМ Дементьев Ю.И.