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

[TarasBer]

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

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

[Lapp]

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

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

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