вощем есть задача, дана карта. Матрица m*n. Заполенная цифрам от 0 до 9. Есть стартовый и конечный пункт движения. Для простоты будет считать стартовым левый верхний угол матрицы. А конечный пункт правый нижний.
Нужно попасть из начального пункта движения в конечный пункт движения. Продвигать можно по вертикали и горизонтали. Нужно найти такой маршрут, при прохождении по которому сумма цифр в клетках по которым лежит маршрут была минимальной.

Вот я тут написал, но она глючит. Скорее всего происходит переполнение стека.

Код

{Algoritm obhoda karti} program kart; uses crt; const maxit=20; var mas:array[1..10,1..10] of byte; masb:array[0..11,0..11] of byte; mascor:array[1..100,1..2] of byte; kolcor:integer; prio:array[1..4] of byte; {1-UP, 2-DOWN, 3-RIGHT, 4-LEFT} it:byte; n,m:byte; x,y:byte; f:text; sum,oldsum:integer; procedure cout(code:integer); var x,y:byte; begin writeln; writeln; if code=0 then   for x:=0 to n+1 do   begin        for y:=0 to m+1 do            write(masb[x,y]:2);        writeln;   end; if code=1 then   for x:=1 to n do   begin        for y:=1 to m do            write(mas[x,y]:2);        writeln;   end; end; procedure gomap(c1,c2,prior:byte); var nc1,nc2:byte; begin {where go} if (it<=maxit) then begin it:=it+1; nc1:=c1; nc2:=c2; if prior=1 then {UP}   nc1:=c1-1; if prior=2 then {DOWN}   nc1:=c1+1; if prior=3 then {RIGHT}   nc2:=c2-1; if prior=4 then {LEFT}   nc2:=c2+1; {map set} {mapb[nc1,nc2]=3;} if ((masb[nc1,nc2]<>0)and(masb[nc1,nc2]<>3)) then {main cond} begin     if (masb[nc1,nc2]<>4) then     begin          masb[nc1,nc2]:=3;          gomap(nc1,nc2,prio[1]);          gomap(nc1,nc2,prio[2]);          gomap(nc1,nc2,prio[3]);          gomap(nc1,nc2,prio[4]);     end     else   {if end go point}     begin          sum:=0;          for x:=1 to n do              for y:=1 to m do                  if masb[x,y]=3 then                     sum:=sum+mas[x,y];          if sum>oldsum then          begin               kolcor:=1;               oldsum:=sum;               for x:=1 to n do                   for y:=1 to m do                       if masb[x,y]=3 then                       begin                            mascor[kolcor,1]:=x;                            mascor[kolcor,2]:=y;                            kolcor:=kolcor+1;                       end;         { writeln(sum);}          end;     end; end; masb[nc1,nc2]:=1; end; it:=it-1; end; begin clrscr; {draw karta} assign(f,'kart.in'); reset(f); readln(f,n,m); for x:=1 to n do begin     for y:=1 to m do     begin         read(f,mas[x,y]);         masb[x,y]:=1;     end;     readln(f); end; close(f); {writeln('asd');} for x:=0 to m+1 do begin     masb[0,x]:=0;     masb[n+1,x]:=0; end; for x:=0 to n+1 do begin     masb[x,0]:=0;     masb[x,m+1]:=0; end; masb[1,1]:=3; masb[n,m]:=4; for x:=1 to 4 do  {set prioritets of move}    prio[x]:=x; oldsum:=0; it:=0; gomap(1,1,prio[1]); gomap(1,1,prio[2]); gomap(1,1,prio[3]); gomap(1,1,prio[4]); cout(0); cout(1); writeln(sum); readln; end.

Цитата(Alexandr87 @ 7.1.2005, 20:18)

Вот я тут написал, но она глючит. Скорее всего происходит переполнение стека.

Если дело не в алгоритме, то может это в раздел Дельфи?

Он уже лижит в паскале, с темой "ошибка". Но там люди говорят, что мол алгоритм кривой (может быть и такое так как писал в спешке.)
Так вот, нужно чтоб ктондь посотрел на это, разобрался и сказал, что не так (если таковое имеется). Или может есть какие еще мысли

если вопрос по алгоритму, то его лучше описать словами, а то код читать очень неудобно, да и большое количество людей, программирующих, например, на C и не знающих Pascal, отсекается

Ну лано тады вощем:
Задание
Написать программу, которая по заданной карте определить наиболее удобный маршрут из пункта А в пункт Б.
Карта представляет собой двумерный массив с элементами целочисленного типа. Каждый элемент массива содержит цифру в десятичной СС (от 0 до 9). Наиболее удобным считается маршрут, при прохождении которого сумма цифр, содержащихся в элементах, находящихся на маршруте будет минимальной.
Входные данные:
координаты начальной точки движения и конечной точки движения
размерность карты
ну и собественно сама карта.

Мой алгоритм решения
Существует две матрицы, одна исходная с числами, другая рабочая размер рабочей матрицы размер исходной +2 столба и 2строки. Для границ. Границы заполняются нулями. Все остальные числа рабочей матрицы заполняются 1(код свободности участка). Начальный пункт движения обозначается 3, конечный пункт движения 4.
Вощем сделал я функцию с тремя параметрами (старая координата х, страрая координата у, направления движения)
функция выполняет следующее:
1.первоначально из входных параметров определяется текущее местоположение.
2.Затем идет условие проверки, если в рабочей матрице на текущей позиции не стоит 3 или 0, т.е. это не граница и мы уже там не были то переходим к следующему пункту, иначе переходим к шагу 5
4.Если это не конечный пункт движения то вызываем эту же функцию 4 раза со следующими параметрами (первые два параметра - текущее местоположение), третий параметр - направление (поэтому и 4 раза). Если все же конечный, то подсчитвыем сумму всех элементов по которым прошли. и если она меньше суммы, которая была получена раньше, то переписываем её а также координаты
5.Так как главное условие позади, записываем в массив, в текущие координаты цифру 1. Тобиш мы здеся не были.

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

Мое решение:

Цитата(Fedor)

Идешь это первой клетки ко всем соседям. Соседей этих сохраняешь в очередь, а в ячейки новой матрицы в клетки, соотв этим соседям, пишеш путь от первой вершины. Далее береш первого из очереди и ДЛЯ ВСЕХ его соседей делаешь ту же саму операцию только с оговрокой что если ты эту клетку уже находил, то идешь в нее только в том случае если это уменьшает число, которое в ней находится. Если нужно потом узнать путь, по которому прошел, то идешь от последней клетки второй матрицы (матрицы путей) и берешь на каждом шаге минимального ее соседа. Так получаешь с обратной стороны твой путь.

Fedor
Большое спасибо

Это называется метод динамического программирования.

Цитата(Fedor @ 8.1.2005, 16:09)

Мое решение: Цитата(Fedor) Идешь это первой клетки ко всем соседям. Соседей этих сохраняешь в очередь, а в ячейки новой матрицы в клетки, соотв этим соседям, пишеш путь от первой вершины. Далее береш первого из очереди и ДЛЯ ВСЕХ его соседей делаешь ту же саму операцию только с оговрокой что если ты эту клетку уже находил, то идешь в нее только в том случае если это уменьшает число, которое в ней находится. Если нужно потом узнать путь, по которому прошел, то идешь от последней клетки второй матрицы (матрицы путей) и берешь на каждом шаге минимального ее соседа. Так получаешь с обратной стороны твой путь.

В классике динамического программирования делается наоборот: сначала обратный ход, затем восстановление оптимального пути прямым проходом.

есть линки или инфа по методу динамического программирования

Цитата

Wizard, 10.1.2005,  11:18]Это называется метод динамического программирования.

Нет. Это - похоже на динамическое программирование.
В динамике мы решаем задачу n-той размерности если мы знаем как решать задачу размерности n-1. А тут не так немного. Мы ж можем и назад вернуться...
Добавлено @ 19:20
Alexandr87 Вообще, если ты хочешь серьезно заниматься олимпиадным программированием, советую тебе не задавать вопросы на форумах, а самому рыться в литературе.
Вот например классная (просто супер) книга - Кормен, Лейзерсон, Ривест - "Алгоритмы. Построение и анализ". Просто незаменимая книга. Но стоит порядка 25 букозоидов.

2Fedor
Спасибо учту

Задача класическая.
Возми любой учебник по иследованию операций или математическому программированию.

Однозначно необходимо применить известнейший алгоритм Дейкстры - поиск кратчайшего пути в весовом графе.
Твою структуру (таблицу с ячейками) можно полностью отождествить с направленным весовым графом.

Дейкстра пишется в несколько строк и работает быстро. Описание алгоритма можешь легко найти в поисковиках. Данное решение является лучшим и самым быстрым.

Искать ошибку в твоём огромном коде - дело гиблое. Так как реализация на самом деле гораздо проще, и лучше тебе написать заново.

Надеюсь, мой ответ тебе помог.

Я также решал эту задачу с немного модифицированным алгоритмом Дийкстры. Мне это нужно было для соединения блоков в блок-схеме.