Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > задача на рекурсию

Автор: tennisru 23.7.2012, 12:58

Карта лабиринта представляет квадратное поле размером 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

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

)

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

ответ 5

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

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

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