Добавлено: 18 ноя 2004, 22:58
Romeo, отличный алгоритм кстати 
. Можно оптимизировать чуть при желании - запоминать координаты последних измененных соседей, чтобы не отыскивать их потом по всей таблице(ну это актуально лишь для достаточно больших матриц).
Я когда-то делал иначе, причем с реальным лабиринтом =). Попытаюсь описать на уровне идеи.
1. В начальную ячейку пишем "1",кладем координаты начальной ячеки в очередь(массив, или связный список структур, включающих в себя координаты ячейки; очередь имеет голову и хвост - указатели на последний внесенный элемент и первый)
2. Достаем из очереди координаты ячейки; затем пробегаем вверх по массиву от этой ячейки, пока не "упремся в стену" или край лабиринта или значение, которое хотим записать больше того, что уже есть в клеточке. Каждый раз увеличиваем значение при каждом перемещении на одну клеточку и записываем в клеточку; кладем координаты этой клеточки в очередь. Аналогично двигаемя вправо влево и вниз.
3. Если хвост "догнал" голову, останавливаемся, иначе смотри п.2. В итоге, будем иметь заполненный массив с длинами путей(кратчайших) до всех ячеек лабиринта, или нули(или что там по умолчанию) для ячеек, путей к которым нету.
Работает это дело примерно так: сначала у нас где-то есть единница. Потом от нее "вырисовывается крестик 123456....." . Потом заполняются строки и столбцы, перпендикулярные сторонам "крестика" и тд. Как найти обратный путь уже предложил Romeo (я тоже так искал.)
Исходничек у меня де-то валялся, на Паскале правда. Если сильно нада - могу попробовать поискать =)...
. Можно оптимизировать чуть при желании - запоминать координаты последних измененных соседей, чтобы не отыскивать их потом по всей таблице(ну это актуально лишь для достаточно больших матриц).Я когда-то делал иначе, причем с реальным лабиринтом =). Попытаюсь описать на уровне идеи.
1. В начальную ячейку пишем "1",кладем координаты начальной ячеки в очередь(массив, или связный список структур, включающих в себя координаты ячейки; очередь имеет голову и хвост - указатели на последний внесенный элемент и первый)
2. Достаем из очереди координаты ячейки; затем пробегаем вверх по массиву от этой ячейки, пока не "упремся в стену" или край лабиринта или значение, которое хотим записать больше того, что уже есть в клеточке. Каждый раз увеличиваем значение при каждом перемещении на одну клеточку и записываем в клеточку; кладем координаты этой клеточки в очередь. Аналогично двигаемя вправо влево и вниз.
3. Если хвост "догнал" голову, останавливаемся, иначе смотри п.2. В итоге, будем иметь заполненный массив с длинами путей(кратчайших) до всех ячеек лабиринта, или нули(или что там по умолчанию) для ячеек, путей к которым нету.
Работает это дело примерно так: сначала у нас где-то есть единница. Потом от нее "вырисовывается крестик 123456....." . Потом заполняются строки и столбцы, перпендикулярные сторонам "крестика" и тд. Как найти обратный путь уже предложил Romeo (я тоже так искал.)
Исходничек у меня де-то валялся, на Паскале правда. Если сильно нада - могу попробовать поискать =)...