Лабиринт, 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 19:14

[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 - 17.07.2010 21:41