Лабиринт, pдача на рекурсию или ..? Опции

[xxx000]

Лабиринт размером M x N состоит из комнат размером 1 x 1 и стен размером 1 x 1. Дан план лабиринта, на котором цифрой 1 отмечены стены, а цифрой 0 - комнаты.

Выяснить, сможет ли человек выйти из лабиринта, если его поместить в комнату с координатами (A, B)?

Порядок ввода исходных данных:

M
N
p11 p12 ... p1N
p21 p22 ... p2N
. . .
pM1 pM2 ... pMN
A B
Здесь M - количество строк на рисунке плана, N - количество столбцов на рисунке плана, p(i, j) - цифра ноль или один, соответствующая клетке плана с координатами i, j. A, B - координаты человека в лабиринте.

Порядок вывода результатов:

Да | Нет
Пример ввода:

10
10
1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 1 1 1 1 0 1
1 1 1 0 1 1 1 1 0 1
1 1 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
2 2
Пример вывода:

Да



Эту задачу надо решать рекурсией??

Сообщение отредактировано: xxx000 - 14.07.2010 23:14

[volvo]

Не надо, а можно... Можно - рекурсией, можно - без рекурсии. Как тебе удобнее.

[xxx000]

Не надо, а можно... Можно - рекурсией, можно - без рекурсии. Как тебе удобнее.

А как без рекурсии, рекурсией она по времени не проходит.

[Unconnected]

А как без рекурсии, рекурсией она по времени не проходит.

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

Сообщение отредактировано: Unconnected - 16.07.2010 5:17

[Lapp]

Про время сначала вообще ни слова не было..

Не только про время - ни слова про ограничения на величины M и N.. Догадывайтесь сами, дорогие друзья, и делайте выводы - рекурсей решать или нет.. Никакого уважения к собеседникам.
Вообще, этот товарищ со значащим именем xxx000 все равно не особо заботится о том, что ему скажут, и не любит отвечать..

[TarasBer]

> А как без рекурсии, рекурсией она по времени не проходит.

Рекурсия - самый быстрый способ обхода, вообще-то.
Просто не надо обходить клетки, в которых уже был.

[Lapp]

Рекурсия - самый быстрый способ обхода, вообще-то.

Несколько странное утверждение. Рекурсия не есть алгоритм. Это всего лишь способ программирования. И рекурсию, как и явные итерации, можно проводить по-разному.. Хотя, я не стану утверждать, что этот способ не имеет обратного влияния на алгоритм. Но, безусловно, постоянные вызовы поцедур и дерганье стека, сильно замедляет программу (и ест память).

Впрочем, все эти разговоры все равно никому не нужны. Автор темы больше не покажется, проверено. До следующей "рдачи" (С), в которой он снова не даст достаточно данных.. ))

[Unconnected]

Да, кажется, действительно ест. Сделал так:

{$APPTYPE CONSOLE}

const mm=10;nn=10;

var mp:array[1..mm,1..nn] of char;
    m,n,a,b,i,j:byte;
    s:string;

Procedure yes;
begin
  writeln('Да');
  halt;
end;

Procedure no;
begin
  writeln('Нет');
  halt;
end;

Procedure rec(a,b:byte);
begin
  if a=m then yes else begin
    if ((a<m) and (mp[a+1,b]='0')) then rec(a+1,b) else
    if ((a>1) and (mp[a-1,b]='0')) then rec(a-1,b) else
    if ((b<n) and (mp[a,b+1]='0')) then rec(a,b+1) else
    if ((b>1) and (mp[a,b-1]='0')) then rec(a,b-1) else no;
  end;
end;

begin
  assign(input,'input.txt');
  readln(m);
  readln(n);
  for i:=1 to m do begin
    readln(s);
    while pos(' ',s)>0 do delete(s,pos(' ',s),1);
    for j:=1 to n do mp[i,j]:=s[j];
  end;
  read(a,b);
  assign(output,'output.txt');
  rec(a,b);
end.

, при размерах поля 10*10 вылетает с переполнением стека. А если урезать как минимум до 7*10, то не вылетает, и даже выдаёт правильный результат. Хотя, может это я чего намудрил)

ADDED: да, что-то совсем не то я сделал.. Мысля пришла опосля.

Сообщение отредактировано: Unconnected - 18.07.2010 1:41

[Unconnected]

{$APPTYPE CONSOLE}

const mm=10;nn=10;

var mp:array[1..mm,1..nn] of char;
    m,n,a,b,i,j:byte;
    s:string;

Procedure yes;
begin
  writeln('Да');
  halt;
end;

Procedure no;
begin
  writeln('Нет');
  halt;
end;

Procedure rec(a,b:byte);
begin
  if (a=1) or (a=m) or (b=1) or (b=n) then yes else begin
    mp[a,b]:='*';
    if mp[a+1,b]='0' then rec(a+1,b);
    if mp[a-1,b]='0' then rec(a-1,b);
    if mp[a,b+1]='0' then rec(a,b+1);
    if mp[a,b-1]='0' then rec(a,b-1);
    no;
  end;
end;

begin
  assign(input,'input.txt');
  readln(m);
  readln(n);
  for i:=1 to m do begin
    readln(s);
    while pos(' ',s)>0 do delete(s,pos(' ',s),1);
    for j:=1 to n do mp[i,j]:=s[j];
  end;
  read(a,b);
  assign(output,'output.txt');
  rec(a,b);
end.

Вот так вроде лучше, не вылетает и на больших полях (20*10 пробовал).

[volvo]

не вылетает и на больших полях

Правда и ответ неверный выдает, но это уже мелочи

10
10
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 1 1 1 1 0 1
1 1 1 0 1 1 1 1 0 1
1 1 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
2 2

Чего должно вывести? А выводит?

[Unconnected]

"Нет" выводит.. Как и должно.

Сообщение отредактировано: Unconnected - 18.07.2010 2:26

[volvo]

Правда?



Что я сделал не так?

[Unconnected]

Мм.. я на D2007 компилирую, может, в этом дело? Сейчас ещё раз скопировал с форума код и входные данные - всё равно нет. Качаю FPC, на нём попробую.

//Собсно, тут тоже алгоритм неправильный.

Сообщение отредактировано: Unconnected - 18.07.2010 3:47

[Unconnected]

{$APPTYPE CONSOLE}

const mm=10;nn=10;

var mp:array[1..mm,1..nn] of char;
    m,n,a,b,i,j:byte;
    s:string;

Procedure yes;
begin
  writeln('Да');
  halt;
end;

Procedure no;
begin
  writeln('Нет');
  halt;
end;

Procedure rec(a,b:byte);
begin
  if (a=1) or (a=m) or (b=1) or (b=n) then yes else begin
    if mp[a+1,b]='0' then begin
      mp[a,b]:='*';
      rec(a+1,b);
      mp[a,b]:='0';
    end;
    if mp[a-1,b]='0' then begin
      mp[a,b]:='*';
      rec(a-1,b);
      mp[a,b]:='0';
    end;
    if mp[a,b+1]='0' then begin
      mp[a,b]:='*';
      rec(a,b+1);
      mp[a,b]:='0';
    end;
    if mp[a,b-1]='0' then begin
      mp[a,b]:='*';
      rec(a,b-1);
      mp[a,b]:='0';
    end;
    no;
  end;
end;

begin
  assign(input,'input.txt');
  readln(m);
  readln(n);
  for i:=1 to m do begin
    readln(s);
    while pos(' ',s)>0 do delete(s,pos(' ',s),1);
    for j:=1 to n do mp[i,j]:=s[j];
  end;
  read(a,b);
  assign(output,'output.txt');
  rec(a,b);
end.

Тут правильный.

[Archon]

Что я сделал не так?

Ошибка локализации =)