Перейти к содержимому


- - - - -

Кратчайший маршрут


В этой теме нет ответов

#1 yanush

    Пользователь

  • Пользователи
  • PipPip
  • 21 сообщений

Отправлено 22 декабря 2011 - 12:16

Условие:
Дана матрица n*m клеток состоящая из 0(клеточка где можно пройти) и -1(там где нельзя пройти).
Найти кратчайший маршрут от точки А до точки В. (обе точки вводятся)
И вывести сам путь.
Пример
Ввод:
5 5
1 1
1 5
0 -1 0 0 0
0 0 -1 0 -1
0 0 0 0 0
-1 0 0 -1 0
0 -1 0 0 0
Вывод:
1 -1 0 8 9
2 0 -1 7 -1
3 4 5 6 0
-1 0 0 -1 0
0 -1 0 0 0

Решение

1) Первым действием у нас процедура сосед которая смотрит если рядом стоящая клеточка пустая то забивает туда следующий номер пути.
2) Вторым действием мы читаем элементы создаём рамочки из -1 что бы не выйти за край и создаём очередь.
3) Третьим действием мы запускаем ваил в котором мы ищём возможные пути и помечаем их
4) Четвёртым действием(оно работает если только мы нашли путь) находим путь которым шли идя с конца мы смотри какое число идёт по убыванию за нами
5) Ну и вывод массива если вам надо вывести только элементы идти нужно с конца

var p:array[0..101,0..101] of integer;
q:array[1..2,1..1000] of integer;
nm,i,j,n,m,i1,j1,fi,fj,ci,cj,un,uk,f:integer;
// {-------------------------Часть №1-------------------------}
procedure  sosed(x,y:integer);
begin
if p[x,y]=0 then begin
         		q[1,uk]:=x;
         		q[2,uk]:=y;
         		uk:=uk+1;
         		p[x,y]:=p[i1,j1]+ 1;
         		end;
end;
 
//{-------------------------Часть №2-------------------------}
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(p[i,j]);
for i:=0 to m+1 do begin
             		p[i,0]:=-1;
             		p[i,m+1]:=-1;
             		end;
for j:=1 to m do begin
             		p[0,j]:=-1;
             		p[n+1,j]:=-1;
                     		end;
readln(ci,cj);
readln(fi,fj);
uk:=1;
un:=1;
p[ci,cj]:=1;
q[1,uk]:=ci;
q[2,uk]:=cj;
uk:=uk+1;
//{-------------------------Часть №3-------------------------}
while (un<>uk)and(p[fi,fj]=0) do begin
i1:=q[1,un]; j1:=q[2,un];
un:=un+1;
sosed(i1+1,j1);
sosed(i1-1,j1);
sosed(i1,j1+1);
sosed(i1,j1-1);
end;
if p[fi,fj]=0  then begin  writeln('NO'); exit; end
            	else writeln( p[fi,fj]);
 
//{-------------------------Часть №4-------------------------}
i:=0;
  i1:=fi;
  j1:=fj;
  nm:=p[fi,fj];
while i<p[fi,fj] do begin
 
  i:=i+1;
  q[1,i]:=i1;
  q[2,i]:=j1;
  f:=0;
  nm:=nm-1;
 
  if (f=0)and(p[i1+1,j1]= nm ) then begin f:=1; i1:=i1+1; end;
 
  if (f=0)and(p[i1-1,j1]= nm ) then begin f:=1; i1:=i1-1; end;
 
  if (f=0)and(p[i1,j1+1]= nm ) then begin f:=1; j1:=j1+1; end;
  
  if (f=0)and(p[i1,j1-1]= nm ) then begin f:=1; j1:=j1-1; end;
 
end;



#2 nogobsent

    Пользователь

  • Пользователи
  • PipPip
  • 10 сообщений
  • ГородTangier

Отправлено 22 июня 2020 - 19:21

Como Usar El Kamagra where to buy cialis online Propecia En Ligne cialis generic best price Cephalexin Over The Counter





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных