Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Июль 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Информационный Канал Subscribe.Ru

Олимпиадные задачи с решениями на Turbo Pascal #30

Подписчиков на 2002-07-13 - 3587 человек(а).
Главная Архив задач Конкурс Рассылки Форум Гостевая книга Контакты

Здравствуйте, уважаемые подписчики!

  Теперь быть в курсе всех обновлений на сайте вам поможет рассылка "Новости проекта Олимпиада.com.ru". В ней будет публиковаться информация об обновлениях в архиве задач, темы форума, и прочие новости сайта. Форма для подписки - в конце номера.
   Так же рекомендую посетить сайт http://algolist.manual.ru, на котором содержится описание огромного количества алгоритмов, методов и исходников. Кстати, задачки тоже есть ;). Правда, зайдите, не пожалеете!

ЗАДАЧИ

Лабиринт - 4 уровень

Условие:
Лабиринт задан с помощью таблицы (8x8), каждой ячейке которой соответствует "0", если пространство пустое, и "1", если прохода нет. Требуется найти кратчайший путь из начальной точки в конечную.

Техническое условие:
Ограничение по времени тестирования - 2 секунды на тест.

Формат входных данных:
Первая и вторая строки файла "Input.txt" содержат координаты начальной и конечной точки. На следующих восьми представлена схема лабиринта в виде двумерной таблицы.

Формат выходных данных:
В первой строке выходного файла "Output.txt" записывается количество ходов для найденного пути. В каждой последующей строке записываются координаты всех точек пути, начиная с первой, и заканчивая последней. В случае если пути в заданную точку не существует, вывести "No way!".

Пример файлов входных и выходных данных:

Input.txt

Output.txt
1 1
1 8
0 1 0 1 0 1 0 0
0 0 1 0 0 1 0 1
1 0 1 1 0 0 0 0
0 0 0 0 0 1 0 1
0 1 1 0 1 0 0 1
0 1 1 1 0 1 1 1
0 1 1 0 0 0 0 1
0 0 0 0 0 0 0 1		 14
1 1
2 1
2 2
3 2
4 2
4 3
4 4
4 5
3 5
3 6
3 7
2 7
1 7
1 8

Решение:
Конечно, сразу напрашивается рекурсия, но тогда нам надо искать ВСЕ пути и находить среди них наиболее короткий. Поэтому предлагаю следующий метод. В данной таблице заполнить числами пустые поля следующим образом. Во-первых, обводим единицами "границу" поля. Затем устанавливаем в начальной точке число "2" и все соседние с ней пустые клетки заполняем "тройками". После этого все соседние пустые поля с каждой "тройкой" заполняем "четверками", и так далее, пока не доберемся до конечной точки.
После этого осталось просто пройти из конечной точки в начальную, следуя по пути убывания чисел. При этом мы получим координаты всех точек самого короткого пути между двумя заданными точками.
Реализовать это не сложно с помощью динамических связанных списков.

const
  n=8;m=8;

type
  Prec=^Rec;
  Rec=record
    x,y,k:byte;
    next:Prec;
  end;
  PWay=^Way;
  Way=record
    x,y:byte;
    next:Pway;
  end;

var
  L:array [0..n+1,0..m+1] of byte;
  Xn,Yn,Xk,Yk:integer;
  x,y,k:integer;
  i,j:integer;
  Head,Tail:Prec;
  Track:Pway;

Procedure Add(x,y,k:integer);{Добавление в очередь}
var P:Prec;
begin
  New(P);
  P^.next:=nil;
  P^.x:=x;
  P^.y:=y;
  P^.k:=k;
  if Head=nil then Head:=P else Tail^.Next:=P;
  Tail:=P;
end;

Procedure Del(var x,y,k:integer);{Удаление из очереди}
var P:Prec;
begin
  P:=Head;
  Head:=Head^.Next;
  x:=P^.x;
  y:=P^.y;
  k:=P^.k;
  Dispose(P);
end;

Procedure Reading;{Читаем входные данные...}
begin
  assign(input,'input.txt');
  reset(input);
  readln(Xn,Yn);
  readln(Xk,Yk);
  for i:=1 to n do
    for j:=1 to m do
    read(L[i,j]);
  close(input);
end;

Procedure Zeroline;{Устанавливаем "границу" поля}
begin
  for i:=1 to m do
  begin
    L[0,i]:=1;
    L[n+1,i]:=1;
  end;
  for i:=1 to n do
  begin
    L[i,0]:=1;
    L[i,m+1]:=1;
  end;
end;

Procedure Writing;{Запись в файл}
var T:PWay;
begin
  assign(output,'output.txt');
  rewrite(output);
  if L[xk,yk]=0 then writeln('No way!') else
  begin
    writeln(L[xk,yk]-1);
    x:=xk;y:=yk;
    repeat
      if L[x+1,y]=(L[x,y]-1) then
      begin
        inc(x);
        New(T);
        T^.x:=x;
        T^.y:=y;
        T^.next:=Track;
        Track:=T;
      end else
      if L[x-1,y]=(L[x,y]-1) then
      begin
        inc(x,-1);
        New(T);
        T^.x:=x;
        T^.y:=y;
        T^.next:=Track;
        Track:=T;
      end else
      if L[x,y+1]=(L[x,y]-1) then
      begin
        inc(y);
        New(T);
        T^.x:=x;
        T^.y:=y;
        T^.next:=Track;
        Track:=T;
      end else
      if L[x,y-1]=(L[x,y]-1) then
      begin
        inc(y,-1);
        New(T);
        T^.x:=x;
        T^.y:=y;
        T^.next:=Track;
        Track:=T;
      end;
    until (x=xn) and (y=yn);
  end;
  T:=Track;
  while T<>nil do
  begin
    writeln(T^.x,' ',T^.y);
    T:=T^.Next;
  end;
  write(xk,' ',yk);
  close(output);
end;

begin
  Reading;
  Zeroline;
  L[Xn,Yn]:=2;
  Add(Xn,Yn,2);
  while Head<>nil do
  begin
    Del(x,y,k);
    if L[x+1,y]=0 then
    begin
      L[x+1,y]:=k+1;
      Add(x+1,y,k+1);
    end;
    if L[x-1,y]=0 then
    begin
      L[x-1,y]:=k+1;
      Add(x-1,y,k+1);
    end;
    if L[x,y+1]=0 then
    begin
      L[x,y+1]:=k+1;
      Add(x,y+1,k+1);
    end;
    if L[x,y-1]=0 then
    begin
      L[x,y-1]:=k+1;
      Add(x,y-1,k+1);
    end;
  end;
  Writing;
end.

ТЕОРИЯ
  Пишите, о чем бы вы хотели почитать в раздле "Теория": sapisoft@yandex.ru. Я хочу освещать интересные вам темы!
Реклама в рассылке:

RLE    

  

Подпишитесь на наши рассылки:

Новости проекта "Олимпиада.com.ru" [Алексей Шамис]
Новости проекта "Olimpiada.com.ru". Новые темы на форуме. Информация о пополнениях в архиве задач. Оперативно и своевременно!

Уроки программирования на Turbo Pascal [Галин Павел]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Шамис Алексей]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Содержит много теоретической информации. Периодичность - 2-3 раза в неделю.

 Задача в неделю. Олимпиадные задачи по информатике [Алексеев Александр]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются, и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть Вас на нашем сайте. Жду ваших предложений и замечаний, Алексей Шамис

Copyright © 2001-2002 by Shamis Alex.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное