Алгоритм решения задачи на графы в С++

[Fiamma]

Текст задачи:
Необходимо найти кратчайший путь выхода из лабиринта. Лабиринт представляет собой прямоугольник размером N х M, со всех сторон окружённый стенами, и состоящий из квадратных клеток размера 1 x 1. Лабиринт снабжен K выходами, до одного из которых необходимо добраться. В некоторых клетках лабиринта находятся стены. Можно перемещаться из клетки в любую из четырех соседних с ней, если в той клетке, куда вы хотите переместиться, нет стены. Кроме того, лабиринт снабжён системой гипертуннелей, способных перемещать из одной клетки лабиринта (вход в гипертуннель) в другую (выход из гипертуннеля). Когда вы находитесь в клетке, где есть вход в гипертуннель, вы можете (но не обязаны) им воспользоваться. Начальное положение известно. Вам необходимо найти кратчайший путь (то есть путь, проходящий через минимальное количество клеток) до любого из выходов.

Input. В первой строке входного файла записаны числа N и M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000), задающие размеры лабиринта: N — количество строк в плане лабиринта, M — количество столбцов. Во второй строке записаны начальные координаты XA, YA (1 ≤ XA ≤ N, 1 ≤ YA ≤ M). Первая координата задает номер строки, вторая — номер столбца. Строки нумеруются сверху вниз, столбцы слева направо. Далее следуют N строк по M чисел, задающих описание стен внутри лабиринта: 1 соответствует стенке, 0 — её отсутствию. Далее в отдельной строке записано число H (0 ≤ H ≤ 1000) — количество гипертуннелей. В последующих H строках идут описания гипертуннелей. Каждый гипертуннель задается 4 числами: X1, Y1, X2, Y2 (1 ≤ X1, X2 ≤ N; 1 ≤ Y1, Y2 ≤ M) — координатами входа и выхода гипертуннеля. Никакие два гипертуннеля не имеют общего входа. После этого в отдельной строке следует число K (1 ≤ K ≤ 10) — количество выходов из лабиринта. В последующих K строках идут описания выходов из лабиринта. Каждый выход задается двумя координатами X и Y (1 ≤ X ≤ N; 1 ≤ Y ≤ M). Гарантируется, что начальные координаты не совпадают ни с одним из выходов и он не стоит в клетке, занятой стеной. Никакие входы и выходы гипертуннелей, а также выходы из лабиринта не находятся в клетках, занятых стенами. Никакой вход в гипертуннель не совпадает с выходом из лабиринта.

Output. Если выход невозможен, выведите единственную строку с надписью "Impossible". В противном случае в первой строке выведите число L — количество клеток в кратчайшем пути выхода. В последующих L строках последовательно выведите координаты клеток кратчайшего пути выхода. Если решений несколько, то выведите любое из них.

Input#1

4 5
2 1
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
2
1 2 1 4
3 1 1 4
1
2 4
Output#1

4
2 1
3 1
1 4
2 4




Input#2

3 3
1 1
0 1 0
0 1 0
0 1 0
0
1
3 3

Output#2

Impossible



Проблема заключается в представлении графа в памяти программы. Матрица смежности - не вариант - слишком много памяти жрет. А списки смежных вершин не получается реализовать, к тому же требуется их организация в иерархический объект, то есть, что-то вроде динамического массива векторов структур(vector<*my_struct>) или динамического массива структур, в которых одно из полей - вектор с номерами связанных вершин...
В общем, нужен красивый алгоритм. Я же пока не получила ничего, кроме access violation. Помогите, кто может.

[rrrFer]

матрица смежности требует в вашей задаче до 1Мб памяти - это вроде бы не слишком много

[Abstraction]

Матрица самого лабиринта и волна по ней - не вариант?

[Son Of Pain]

Матрица в "диком" виде займет в памяти около пяти мегабайт. У тебя настолько суровые ограничения по памяти? ) Тогда храни sparse matrix, или список смежности. И напусти на данные любой алгоритм поиска кратчайшего пути (волновой, например).

[Fiamma]

Мне не нравится матрица смежности даже не из-за занимаемой памяти - отведенный объем согласно задаче 16 мб. Но вот обход ее мне представляется достаточно длительным процессом, а ограничение по времени там имеется. К тому же, если честно, я не представляю, как по ней реализовать обход графа.

[rrrFer]

К тому же, если честно, я не представляю, как по ней реализовать обход графа.

Сразу бы так.
Матрица смежности - это весьма распространенный формат представления графа, значит про алгоритм обхода может быть написано в обычных книжках(где то в начале раздела по теории графов).
Скорее всего сможете найти материалы на интуите. Не исключено что в книжках найдете исходники, ну или алгоритмы на псевдокоде.

[Son Of Pain]

Действительно, матрицу смежности обходить "волной" - не лучший вариант. Потому мы и советуем хранить матрицу лабиринта в чистом вите - единица для стены, 0 для прохода....

В общем, стукни ближе к вечеру мне в аську, расскажу подробнее, если что.