Поиск пути
Содержимое ячейки таблицы на пересечении строки i и столбца j соответствует значению map [ i, j ].
Помимо массива тар нам потребуются массив road (дорога) и массив incl (от include – включать). В road мы будем записывать номера пройденных городов. В момент достижения конечной точки он будет содержать номера всех пройденных точек, т. е. описание маршрута.
В inci [i] будем записывать true, если точка с номером i включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку (не ходить по кругу).
Так как мы используем рекурсивную процедуру, то надо обратить особое внимание на условие завершения рекурсивного процесса. Процедура должна прекратить вызывать сама себя, если текущая точка совпала с заданной конечной точкой.
На рис. 12.11 приведена блок-схема алгоритма процедуры выбора очередной точки формируемого маршрута, а диалоговое окно – на рис. 12.12.
Для ввода массива, представляющего описание карты, используется компонент stringGridl (значения его свойств приведены в таблице 12.1), для вывода результата (найденного маршрута) – поле метки Label 1. Начальная и конечная точки маршрута задаются вводом значений в поля редактирования Edit1 и Edit2. Процедура поиска запускается щелчком кнопки Поиск (Button1). Поля меток Label2, Label3 и Label4 используются для вывода поясняющего текста.
Рис. 12.11. Блок-схема процедуры выбора точки маршрута
Рис. 12.12. Окно программы Поиск маршрута