Болото. Рекурсия

@CrazzyBeer · Регистрация: 24.03.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте.
Сегодня, участвуя в онлайн олимпиаде на a c m p столкнулся с этой задачей. Печально, но не успел её решить. Но мне все-таки интересно и, к тому же, я был очень близко к решению.

(Время: 1 сек. Память: 16 Мб Баллы: 100)
В 314 уровне компьютерной игры «Болото» лягушонку Квайту предстоит решить непростую задачу. На прямой расположены N листьев водяной лилии, на каждом из которых сидит большая муха. Находясь на одном из листьев, он может прыгнуть на соседний лист или перепрыгнуть через один лист в любую сторону и съесть сидящую там муху. Квайт уже большой лягушонок, а листья не очень надежные, поэтому, когда он прыгает на какой-то лист и съедает сидящую на нем муху, лист начинает тонуть, так что Квайт должен сразу же прыгать дальше.

Для того, чтобы продолжать приключения, Квайту необходимо съесть всех мух, начав свой путь с листа номер A и закончив на листе номер B (листья пронумерованы вдоль прямой последовательными натуральными числами, начиная с единицы).

Помогите Квайту пройти этот уровень.

Входные данные

Входной файл INPUT.TXT содержит три целых числа, разделенных пробелами: N, A и B (2 ≤ N ≤ 1000, 1 ≤ A, B ≤ N, A ≠ B).

Выходные данные

В выходной файл OUTPUT.TXT выведите n−1 число − последовательность прыжков, которые нужно сделать Квайту. Прыжок задается числом −2, −1, 1 или 2, которое означает разность между номером листа, на котором оказывается Квайт, и номером листа, на котором он находится перед прыжком. Если не существует пути, удовлетворяющего требованиям, выведите одно число 0.
Примеры

INPUT.TXT
5 2 4
OUTPUT.TXT
-1
2
2
-1

INPUT
4 2 3
OUTPUT
0

Так как я весь день промучился с ней и ничего не смог сделать - прошу помощи у вас.
Пробовал через рекурсивный поиск в глубину, заваливалось по времени даже при относительно маленьких ограничениях. Пробовал использовать еще и ленивую динамику - то ли я плохо использовал, то ли что-то другое - но проблема остается нерешенной.
Прошу советов. Может есть какой-то другой метод или же есть идеи по поводу менее жрущего времени рекурсивного поиска?

@Puporev · 20.09.2014, 16:54

Здесь
http://www.uz.denemetr.com/doc... -2702.html
есть разбор алгоритма на непонятном языке, после чего код на Basic и Delphi

@CrazzyBeer · 20.09.2014, 20:29 **[ТС]**

Тут я тоже был, но код не рабочий.
Кстати. Это ведь путь Эйлера?
Только у меня что-то не получается сделать его из вершины a в b. Только обычный.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var n,a,b,l,i:integer; 
    c,d:array[1..1000] of integer;
procedure find(i:integer);
   begin
    if (i>1) and (c[i-1]<>1) then begin c[i-1]:=1; find(i-1); end;
    if (i>2) and (c[i-2]<>1)  then begin c[i-2]:=1; find(i-2); end;
    if (i<n) and (c[i+1]<>1)  then begin c[i+1]:=1; find(i+1); end;
    if (i+1<n) and (c[i+2]<>1)  then begin c[i+2]:=1; find(i+2); end;
    inc(l);
    d[l]:=i;
  end;
Begin
assign(input, 'input.txt'); reset(input); 
assign(output, 'output.txt'); rewrite(output);
read(n,a,b);
c[a]:=1;
find(a);
for i:=2 to l do writeln(d[i]-d[i-1]);
End.

Добавлено через 1 час 23 минуты
Другими словами - вывести путь, с помощью которого можно попасть из вершины a в вершину b, используя каждую вершину только один раз.
Звучит легко, но решение заваливается на больших ограничениях

Добавлено через 20 минут

Pascal
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
var n,a,b,l,i,o:integer; 
    c,d:array[1..1000] of integer;
procedure find(i,t:integer);
   begin
     c[i]:=1;
     if (i=b) and (t=n) then begin o:=1; d[t]:=i; end;
     if (i<>b) and (t<n) then 
      begin
       if (o=0) and (i<n) and (c[i+1]<>1) then find(i+1,t+1);
       if (o=0) and (i+1<n) and (c[i+2]<>1) then find(i+2,t+1);
       if (o=0) and (i>1) and (c[i-1]<>1) then find(i-1,t+1);
       if (o=0) and (i>2) and (c[i-2]<>1) then  find(i-2,t+1);
       if o=1 then d[t]:=i; {Если где-то  на нижних уровнях рекурсии был найден путь - значит записываем эту вершину в массив, чтобы вывести}
      end;
      c[i]:=0;
 
  end;
Begin
assign(input, 'input.txt'); reset(input); 
assign(output, 'output.txt'); ; rewrite(output);
read(n,a,b);
find(a,1);
i:=1;
while d[i]<>0 do inc(i);
for l:=2 to i-1 do writeln(d[l]-d[l-1]);
End.

Что-то больше похожее на рабочую программу. Подскажет кто-то, как улучшить?

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	20.09.2014, 16:54
	Здесь http://www.uz.denemetr.com/doc... -2702.html есть разбор алгоритма на непонятном языке, после чего код на Basic и Delphi 1

Болото. Рекурсия

Решение