Задача по языку C++: "Ловушка Лабиринта"

Эта задача подчеркивает важность креативного мышления и оптимального использования ресурсов.

Задача: Поиск Выхода из Лабиринта

Представьте себе лабиринт, представленный двумерным массивом. Каждая ячейка может быть стеной (#), проходом (.), стартом (S) или выходом (E). Задача заключается в написании программы на C++, которая определит, существует ли путь из точки старта до выхода в лабиринте.

#include <iostream>
#include <vector>

using namespace std;

// Функция проверки валидности ячейки лабиринта
bool is_valid(int x, int y, int rows, int cols, vector<vector<char>>& maze, vector<vector<bool>>& visited) {
 return x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] != '#' && !visited[x][y];
}

// Рекурсивная функция поиска пути в лабиринте
bool solve_maze(int x, int y, int rows, int cols, vector<vector<char>>& maze, vector<vector<bool>>& visited) {
	// Если достигнут выход, возвращаем true
	if (x == rows - 1 && y == cols - 1)
		return true;

	// Если текущая ячейка валидна
	if (is_valid(x, y, rows, cols, maze, visited)) {
		// Помечаем текущую ячейку как посещенную
		visited[x][y] = true;

		// Рекурсивный поиск в соседних ячейках
		if (solve_maze(x + 1, y, rows, cols, maze, visited) ||
			solve_maze(x - 1, y, rows, cols, maze, visited) ||
			solve_maze(x, y + 1, rows, cols, maze, visited) ||
			solve_maze(x, y - 1, rows, cols, maze, visited)) {
			return true;
		}

		// Если нет пути, отмечаем ячейку как недоступную
		visited[x][y] = false;
	}

	return false;
}

// Функция проверки возможности добраться до выхода из лабиринта
bool can_escape(vector<vector<char>>& maze) {
	int rows = maze.size();
	int cols = maze[0].size();

	// Создаем массив для отслеживания посещенных ячеек
	vector<vector<bool>> visited(rows, vector<bool>(cols, false));

	// Начинаем поиск с точки старта
	return solve_maze(0, 0, rows, cols, maze, visited);
}

// Основная функция программы
int main() {
	// Пример использования:
	vector<vector<char>> maze = {
		{'S', '.', '#', '#', '#'},
		{'#', '.', '#', '#', '#'},
		{'#', '.', '.', '#', '#'},
		{'#', '#', '.', '#', '#'},
		{'.', '#', '.', '.', 'E'}
	};

	// Проверяем, существует ли путь из старта в выход
	if (can_escape(maze))
		cout << "Путь из старта в выход существует.\n";
	else
		cout << "Нет пути из старта в выход.\n";

	return 0;
}

Комментарии:

1. Функция is_valid: Проверяет, является ли ячейка в лабиринте валидной (не стена, не посещена, не выходит за границы).
2. Функция solve_maze: Рекурсивно ищет путь из текущей ячейки к выходу, используя глубину поиска.
3. Функция can_escape: Инициализирует массив для отслеживания посещенных ячеек и запускает рекурсивный поиск из точки старта.
4. Основная функция main: Создает пример лабиринта, вызывает функцию can_escape и выводит результат.

В данной программе используется рекурсивный алгоритм для поиска пути в лабиринте, начиная с точки старта (S). Программа проверяет соседние ячейки и решает, можно ли добраться до выхода (E). Решение задачи требует внимания к деталям логики и эффективного управления процессом поиска в лабиринте.