Собственно задача одна из многих на нахождение кратчайшего пути. В наших олимпиадах таких задач было несколько (см. http://shgpi.edu.ru/solver/).
Задача.
Пусть имеются две точки (x1,y1) и (x2,y2). Некто передвигается из первой точки во вторую. За один раз можно делать:
1. Шаг влево x-1
2. Шаг вправо x+1
3. Шаг вверх y+1
4. Шаг вниз y-1
1. Необходимо определить минимальное количество шагов от первой точки ко второй.
2. Найти все возможные маршруты с минимальным количеством шагов.
Собственно, если оставить только первый вопрос, то для нахождения минимального количества шагов программы писать не надо.
Действительно минимальное количество шагов можно вычислить по формуле abs(x1-x2) + abs(y1-y2). И все!
А вот что касается второго вопроса, то здесь без программы не обойтись. Типичная задача на нахождения самого короткого пути.
И типичнейшая же проблема - как в процессе перебора шагов отбрасывать пути, заведомо не ведущие к правильному результату.
В разных задачах этот критерий может быть разным. В данном случае критерий очевиден: если на очередном ходу расстояние до
целевой точки увеличилось, то этот шаг сразу следует аннулировать. Заметим, что если не вводить критерий, то движение
шагающего приведет скорее всего к переполнению стека. Вот собственно и все.
- Код: Выделить всё
var
x1,y1,x2,y2,i,j,n,min:integer;...
r:integer;
a:array[1..100] of integer;
b:array[1..100] of integer;
procedure shag(x,y,rr:integer);
var
rt:integer;
begin
a[n]:=x; b[n]:=y; inc(n);
if (x=x2) and (y=y2) then
begin
<------>if min>n-1 then min:=n-1;<----->
<------>for j:=1 to n-1 do.
<------>begin
<------> write(a[j],' ',b[j],'; ');
<------>end;
<------>writeln;
end
else
begin
<------>if rr>(x-x2)*(x-x2)+(y-y2)*(y-y2) then
<------>begin
<------> rt:=(x-x2)*(x-x2)+(y-y2)*(y-y2);
<------> shag(x+1,y,rt);.
<------> shag(x,y+1,rt);.
<------> shag(x-1,y,rt);.
<------> shag(x,y-1,rt);.
<------>end;
end;
dec(n);
end;
{-------------------------------}....
begin
readln(x1,y1);
readln(x2,y2);
for i:=1 to 100 do
begin
<------>a[i]:=0;b[i]:=0;
end;
min:=200;
if (not((x1=x2) and (y1=y2))) then
begin<-----><------>
r:=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
n:=1;
shag(x1+1,y1,r);....
n:=1;
shag(x1,y1+1,r);....
n:=1;
shag(x1-1,y1,r);....
n:=1;
shag(x1,y1-1,r);....
end
<------>else
<------> min:=0;<------>
writeln(min);
end.
Остается только добавить, что вместо расстояния используется его квадрат, что, конечно, удобнее.
Заметим также, что в задаче предполагается, что минимальное количество шагов не может превзойти 100.
Обычное ограничение.
Замечание.
Однако вот вопрос. Нельзя ли улучшить алгоритм, основываясь на том факте, что минимальное количество шагов может быть вычислено заранее? Подумайте.