VPF::задача на рекурсию - Форум программистов

tennisru

Дата 23.7.2012, 12:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 3.12.2011

Репутация: нет
Всего: нет

Карта лабиринта представляет квадратное поле размером N*N. Некоторые квадраты этого поля запрещены для прохождения. Шаг в лабиринте представляет собой перемещение из одной разрешенной клетки к другой разрешенной клетке, смежной с первой по стороне. Путь - это некоторая последовательность таких шагов. Требуется подсчитать количество различных путей из клетки (1,1) в клетку (N,N) ровно за K шагов (то есть ,оказаться в клетке (N,N) после K-того шага. Каждую клетку, включая начальную и конечную можно посещать несколько раз. Начальная и конечная клетки всегда разрешены для прохождения.
1 < N ≤ 20
0 < K ≤ 50

Пример ввода #1:
3 6
000
101
100

ответ 5

алгоритм такой: от 1 1 идем в стороны если можем,одновременно считаем текущий шаг. выдало тай лимит, немного усовершенствовал если расстояние в клеток от текущей до n,n меньше чем осталось то выход прошло еще пару тестов а дальше не знаю что делать
мой код, если надо

Код


var s:string;
ans,n,st,i,j,k,l:longint;
a:array[1..30,1..30] of longint;
mas:array[-11..430] of char;
ch:Char;
procedure rec(i,j,sum:longint);
begin
if (i=n)and(j=n)and(sum=k) then begin inc(ans);end;
 
{     writeln(i, ' ',j, ' ',sum);}
     if (i+1<=n)and(a[i+1,j]=1)and(sum+1<=k)and((n-i)+(n-j)<= k - sum)then rec(i+1,j,sum+1);
     if (i-1>=1)and(a[i-1,j]=1)and(sum+1<=k)and((n-i)+(n-j)<= k - sum) then rec(i-1,j,sum+1);
     if (j-1>=1)and(a[i,j-1]=1)and(sum+1<=k)and((n-i)+(n-j)<= k - sum) then rec(i,j-1,sum+1);
     if (j+1<=n)and(a[i,j+1]=1)and(sum+1<=k)and((n-i)+(n-j)<= k - sum) then rec(i,j+1,sum+1);
 
 
end;
 
begin
 
assign(input, 'input.txt'); reset(input);
 assign(output, 'output.txt'); rewrite(output);
readln(n,k);
 
for i:=1 to n do
begin  for j:=1 to n do
  begin read(ch);if ch='0' then a[i,j]:=1 else a[i,j]:=0;end;
  readln;
  end;
{for i:=1 to n do
begin  for j:=1 to n do
      write(a[i,j]);
      writeln;end;
}rec(1,1,0);
writeln(ans);
end.

magesi

Дата 26.7.2012, 20:58 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 120
Регистрация: 20.5.2012

Репутация: нет
Всего: -4

Цитата(tennisru @ 23.7.2012, 12:58

)

Пример ввода #1:
3 6
000
101
100

ответ 5

а что за параметры на входе?

обычно в олимпиадных задачках аля ACM , расписывают еще, что именно подается на input stream? распиши пожалуйста у этой задачи, у тебя есть id , чтобы посмотреть в бд задач олимпиадных? ( им обычно дают уникальных id на всяких ACM )

судя по параметрам, там наверное расписаны кол-во препятствий ( запрещ. квадратов ) и длина пути возможная и тд

Это сообщение отредактировал(а) magesi - 26.7.2012, 20:59

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »