Принципы динамического программирования
Подсказки к ДЗ: 1) Структура данных (возможна оптимизация): //открываем файл для чтения; //читаем из него m,n - количество строк и столбцов поля setlength(pole,m+2,n+2);//здесь строки поля 1..m, а колонки 1..n. Остальное - стенка //читаем из файла xs,ys - координаты стартовой клетки (начало координат: [1,1]) //читаем xe,ye - координаты конечной клетки (здесь x-строка, считая сверху, а y-колонка) //читаем в цикле по строкам от 1 до m и столбцам от 1 до n из файла //веса v всех клеток, и заполняем массив pole, учитывая, что: // начальное значение S задаем равным большому числу // если v=-1, то это стенка, задаем f=1, иначе f=0 //для нулевой и m+1 - й строки задаем f=1 (стенка) //для нулевого и n+1 - й колонки задаем f=1 (стенка) //для клетки (xs,ys) (стартовой) задаем s=0 type pp=record x,y:integer;//координаты предшественника v:integer;//"вес" клетки f:integer;//флаг: стенка: f=-1, обычное поле: f=0 s:integer;//путь до клетки (сумма весов по маршруту) end; var pole:array [,] of pp;//двумерный массив записей xs,ys,xe,ye,m,n:integer; 2) Описание модуля Rread - процедуры подготовки данных (возможна оптимизация): 3) Описание модуля Pathfinder(I,j) - процедуры (или функции?) поиска кратчайшего пути из (xs, ys) в (xe, ye): Пусть (i, j) – текущая клетка, а соответствующий ей элемент массива: pole[I, j]. Если клетка [i+1, j] - не стенка и pole[i, j].s + pole[i+1, j].v, …, ->(xe, ye) End. Pas-файл с выполненным заданием выслать в мой E-mail адрес: LEOMTL@MAIL.RU, прикрепив к письму и указав в «Теме» ФИО, класс и подгруппу, например: Иванов Иван, 11Т1 (в названии класса-подгруппы всё писать подряд и латиницей) 16 16 - строк и столбцов 12 8 - строка и столбец стартовой клетки 4 10 - строка и столбец конечной клетки Поле (первая строка и первый столбец – нумерация, для удобства) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 3 1 1 1 1 -1 1 1 -1 1 1 -1 1 -1 1 1 1 4 1 -1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 5 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 6 1 1 1 1 1 1 -1 1 -1 1 1 1 -1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 10 1 1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 1 11 1 -1 -1 -1 1 -1 1 1 1 1 1 1 -1 1 1 1 12 1 1 -1 1 1 -1 1 0 -1 1 1 -1 1 1 1 1 13 1 1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 1 14 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 15 1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1