TaskMaze.cpp

/*
Самое главное что нужно знать, что в односвязном лабиринте к точке выхода ведет всегда только один путь. 
Еще один момент, который нужно учитывать, что добраться до выхода можно используя "Правило руки":
"...Один из методов состоит в том, чтобы в каждой узловой точке выбирать одно и то же направление. 
Например, можно всегда сворачивать на крайнюю правую ветвь. Если этот путь закончится тупиком, следует вернуться к узловой точке 
и выбрать следующую ветвь (если считать справа). Может оказаться, что в результате вы пройдете по каждой ветви дважды — по одному разу 
в каждом направлении, но в конце концов вы доберётесь до цели. На обратном пути можно либо продолжать выбирать крайние правые ветви 
в каждом узле (и в этом случае вы, вероятно, пройдёте по новым областям лабиринта), либо каждый раз сворачивать на крайнюю левую ветвь 
(и тогда вы в точности повторите первоначальный маршрут). Метод выбора одной и той же — правой или левой — ветви я называю 
соответственно правилом правой или левой руки..."
Исходя из этого мы можем "запоминать" уже посещенные ячейки. И если, поблуждав в каком-то тупике, мы возвращаемся на правильный маршрут, 
мы можем исключить все дважды посещенные точки из списка с посещаемыми точками. Длинна этого списка, в конечном итоге, 
и будет являться длинной кратчайшего маршрута.
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

// Чтение файла input.txt и сохранение символьного лабиринта в двумерный массив
std::vector<std::vector<char>> read_maze_file()
{
	// Инициализируем двумерный массив как вектор векторов с символами
	std::vector<std::vector<char>> maze;
	// Строка для считывания очередной строки из файла
	std::string line;
	// Открываем файл
	std::ifstream myfile("input.txt");
	// Если он открыт
	if (myfile.is_open())
	{
		// Читаем по строчно до самого конца
		while (std::getline(myfile, line))
		{
			// Сохраняем строку в вектор символов
			std::vector<char> maze_row;
			// И выводим на экран
			std::cout << line << '\n';
			// Проверяем, чтобы строка была не пустая
			if (line.size() >= 3) {
				// Сохраняем каждый символ в вектор
				for (auto ch : line)
					maze_row.push_back(ch);
				// И добавляем очередную строку лабиринта
				maze.push_back(maze_row);
			}
		}
		// Закрываем файл
		myfile.close();
	}
	// Возвращаем символьный массив с лабиринтом
	return maze;
}

// Введем понятие "направление"
enum DirectionEnum { up, left, right, down };
// И структуру позиции в лабиринте
struct point
{
	unsigned int x;
	unsigned int y;
	// Перегрузка оператора '<' требуется для её использования в std::map
	bool operator < (const point &p1) const
	{
		if (y < p1.y) return true;
		if (y > p1.y) return false;
		if (y == p1.y) return x < p1.x;
		return false;
	}
};

// Функция поиска кратчайшего пути
unsigned int get_short_way_lenght(std::vector<std::vector<char>> maze)
{
	// Заведем словарь с именем map, где все посещенные точки будем отмечать как true
	std::map<point, bool> map;
	// И вектор из точек, для хранения кратчайшего пути
	std::vector<point> short_way;
	
	// Зададим начальное значение направление нашей робо-мыши
	DirectionEnum direction = right;
	// И найдем в массиве точку входа в лабиринт и запомним её позицию
	point pos{ 0, 0 };
	for (size_t i = 0; i < maze.size(); ++i) 
	{
		for (size_t j = 0; j < maze[0].size(); j++)
			if (maze[i][j] == '1')
			{
				pos = point{ j, i };
				break;
			}
		if ((pos.x != 0) && (pos.y != 0))
			break;
	}
	// Помечаем точку входа, как уже посещенную
	map[pos] = true;
	short_way.push_back(pos);

	// И ищем путь до тех пор, пока не доберемся до выхода
	while (maze[pos.y][pos.x] != '0')
	{
		// Определим проверяемую впереди себя ячейку
		point forward_cell{ pos.x, pos.y };
		// И повернем против часовой стрелки (налево), чтобы проверить, что у нас находиться по левую сторону
		direction = direction == up ? left : direction == left ? down : direction == down ? right : up;

		do {
			// обнулим значение проверяемой ячейки
			forward_cell = pos;
			// Скорректируем координаты проверяемой ячейки в зависимости от текущих позиции и направления
			forward_cell.x += direction == right ? 1 : direction == left ? -1 : 0;
			forward_cell.y += direction == up ? -1 : direction == down ? 1 : 0;
			// и повернем по часовой стрелке
			direction = direction == up ? right : direction == right ? down : direction == down ? left : up;			
		} while (maze[forward_cell.y][forward_cell.x] == '#'); // Если проверяемая ячейка - это стена, то повторим процедуру проверки ячейки
		
		// Когда нашли свободную ячейку (не стену), то нужно скорректировать наше направление повернув обратно один раз против часовой стрелки
		direction = direction == up ? left : direction == left ? down : direction == down ? right : up;
		// Проверим новую ячейку
		auto foundedIter = map.find(forward_cell);
		// Если мы в ней уже были
		if (foundedIter != map.end())
		{
			// И коллекция с кратчайшим путем не пустая
			if (!short_way.empty()) 
			{
				// То будем удалать последний объект из коллекции кратчайшего пути до тех пор, пока там есть элементы или пока не найдем уже посещенную ранее ячейку
				while ((!short_way.empty()) && ((short_way.back().x != foundedIter->first.x) || (short_way.back().y != foundedIter->first.y)))
					short_way.erase(--short_way.end());
				// Если коллекция не пустая
				if (!short_way.empty())
					// То удалим и последний элемент (саму ячейку)
					short_way.erase(--short_way.end());
			}
		}

		// Обновляем текущую позицию
		pos = forward_cell;
		// Отмечаем, что мы здесь уже были
		map[pos] = true;
		// И добавляем ячейку в коллекцию кратчайшего пути
		short_way.push_back(pos);
	}
	// И вернем длинну кратчайшего пути (за исключением точки входа)
	return short_way.size() - 1;
}

// Тест
int main()
{
	// Тест
	std::cout << "Shortest path lenght = " << get_short_way_lenght(read_maze_file()) << std::endl;

	return 0;
}