# Создание структуры данных лабиринта:
MAZE = """
#######################################################################
#S# # # # # # # # # #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# # # # # # # # # # # # # # # # # # # #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
# # # # # # # # # # # # # # # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
# # # # # # # # # # # # # # # # # #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # # # # # # # # # # # # # # # # # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
# # # # # # # # # # # # # # # # #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
# # # # # # # # # # # # # # # # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
# # # # # # # # # # # # # # # # # #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
# # # # # # # # # E#
#######################################################################
""".split('\n')
# Константы, используемые в этой программе:
EMPTY = ' '
START = 'S'
EXIT = 'E'
PATH = '.'
# Получаем высоту и ширину лабиринта:
HEIGHT = len(MAZE)
WIDTH = 0
for row in MAZE: # Устанавливаем WIDTH на ширину самой широкой строки.
if len(row) > WIDTH:
WIDTH = len(row)
# Преобразуем каждую строку лабиринта в список шириной WIDTH:
for i in range(len(MAZE)):
MAZE[i] = list(MAZE[i])
if len(MAZE[i]) != WIDTH:
MAZE[i] = [EMPTY] * WIDTH # Делаем эту строку пустой.
def printMaze(maze):
for y in range(HEIGHT):
# Печатаем каждую строку.
for x in range(WIDTH):
# Печатаем каждый столбец в этой строке.
print(maze[y][x], end='')
print() # Печатаем новую строку в конце строки.
print()
def findStart(maze):
for x in range(WIDTH):
for y in range(HEIGHT):
if maze[y][x] == START:
return (x, y) # Возвращаем координаты старта.
def solveMaze(maze, x=None, y=None, visited=None):
if x == None or y == None:
x, y = findStart(maze)
maze[y][x] = EMPTY # Убираем 'S' из лабиринта.
if visited == None:
visited = [] # Создаём новый список посещённых точек.
if maze[y][x] == EXIT:
return True # Найден выход, возвращаем True.
maze[y][x] = PATH # Отмечаем путь в лабиринте.
visited.append(str(x) + ',' + str(y))
#printMaze(maze) # Раскомментировать, чтобы просмотреть каждый шаг вперёд.
# Исследуем соседнюю точку на севере:
if y + 1 < HEIGHT and maze[y + 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y + 1) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x, y + 1, visited):
return True # БАЗОВЫЙ СЛУЧАЙ
# Исследуем соседнюю точку на юге:
if y - 1 >= 0 and maze[y - 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y - 1) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x, y - 1, visited):
return True # БАЗОВЫЙ СЛУЧАЙ
# Исследуем соседнюю точку на востоке:
if x + 1 < WIDTH and maze[y][x + 1] in (EMPTY, EXIT) and \
str(x + 1) + ',' + str(y) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x + 1, y, visited):
return True # БАЗОВЫЙ СЛУЧАЙ
# Исследуем соседнюю точку на западе:
if x - 1 >= 0 and maze[y][x - 1] in (EMPTY, EXIT) and \
str(x - 1) + ',' + str(y) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x - 1, y, visited):
return True # БАЗОВЫЙ СЛУЧАЙ
maze[y][x] = EMPTY # Восстанавливаем пустое пространство.
#printMaze(maze) # Раскомментировать, чтобы просмотреть каждый шаг назад.
return False # БАЗОВЫЙ СЛУЧАЙ
printMaze(MAZE)
solveMaze(MAZE)
printMaze(MAZE)
#include
#include
#include
using namespace std;
// Создание структуры данных лабиринта
const string MAZE[] = {
"#######################################################################",
"#S# # # # # # # # # #",
"# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###",
"# # # # # # # # # # # # # # # # # # # #",
"# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #",
"# # # # # # # # # # # # # # # # #",
"######### # # # ##### # ### # ########### ####### # # ##### ##### ### #",
"# # # # # # # # # # # # # # # # # #",
"# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #",
"# # # # # # # # # # # # # # # # # # #",
"### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #",
"# # # # # # # # # # # # # # # # #",
"# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###",
"# # # # # # # # # # # # # # # # #",
"### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #",
"# # # # # # # # # # # # # # # # # #",
"# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #",
"# # # # # # # # # E#",
"#######################################################################"
};
const char EMPTY = ' ';
const char START = 'S';
const char EXIT = 'E';
const char PATH = '.';
// Получаем высоту и ширину лабиринта:
const int HEIGHT = sizeof(MAZE) / sizeof(MAZE[0]);
int WIDTH = 0;
// Преобразуем лабиринт в двумерный вектор:
vector> maze(HEIGHT);
void initializeMaze() {
for (int i = 0; i < HEIGHT; i++) {
maze[i] = vector(MAZE[i].begin(), MAZE[i].end());
if (MAZE[i].length() > WIDTH) {
WIDTH = MAZE[i].length();
}
}
// Устанавливаем пустые символы для строк, длина которых меньше максимальной ширины
for (int i = 0; i < HEIGHT; i++) {
while (maze[i].size() < WIDTH) {
maze[i].push_back(EMPTY);
}
}
}
void printMaze() {
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
cout << maze[y][x];
}
cout << endl;
}
cout << endl;
}
pair findStart() {
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
if (maze[y][x] == START) {
return { x, y };
}
}
}
return { -1, -1 }; // Не найдено
}
bool solveMaze(int x, int y, vector>& visited) {
if (maze[y][x] == EXIT) {
return true; // Найден выход
}
maze[y][x] = PATH; // Отмечаем путь
visited[y][x] = true;
// Проверяем соседние клетки (север, юг, восток, запад)
if (y + 1 < HEIGHT && (maze[y + 1][x] == EMPTY || maze[y + 1][x] == EXIT) && !visited[y + 1][x]) {
if (solveMaze(x, y + 1, visited)) {
return true;
}
}
if (y - 1 >= 0 && (maze[y - 1][x] == EMPTY || maze[y - 1][x] == EXIT) && !visited[y - 1][x]) {
if (solveMaze(x, y - 1, visited)) {
return true;
}
}
if (x + 1 < WIDTH && (maze[y][x + 1] == EMPTY || maze[y][x + 1] == EXIT) && !visited[y][x + 1]) {
if (solveMaze(x + 1, y, visited)) {
return true;
}
}
if (x - 1 >= 0 && (maze[y][x - 1] == EMPTY || maze[y][x - 1] == EXIT) && !visited[y][x - 1]) {
if (solveMaze(x - 1, y, visited)) {
return true;
}
}
maze[y][x] = EMPTY; // Восстанавливаем пустое пространство
return false;
}
int main() {
initializeMaze();
printMaze();
auto [startX, startY] = findStart();
if (startX == -1 || startY == -1) {
cout << "Start point not found!" << endl;
return 1;
}
vector> visited(HEIGHT, vector(WIDTH, false));
if (solveMaze(startX, startY, visited)) {
cout << "Path found:" << endl;
}
else {
cout << "No path found!" << endl;
}
printMaze();
return 0;
}