#include <fstream.h>
#include <iostream.h>
int trien(int, int, int);
char ***a;
int i, j, k, l, m, n, right = 0, down = 0;
void main()
{
int x, y, z;
ifstream in;
in.open("F.IN", ios::in);
in>>l>>m>>n;
a = new char **[l];
for (i = 0; i < l; i++)
{
a = new char *[m];
for (j = 0; j < m; j++)
a[j] = new char [n];
}
for (i = 0; i < l; i++)
for (j = 0; j < m; j++)
for (k = 0; k < n; k++)
{
in>>a[j][k];
if (a[j][k] == '1')
{
x = i; y = j; z = k;
}
}
trien(x, y, z);
}
int trien (int x, int y, int z)
{
if (a[x][y][z] == '2')
{
cout<<"Konec zada4i"<<endl;
return 1;
}
if (a[x][y][z] == 'o')
return 0;
if (x < l - 1 && trien (x+1, y, z) == 1)
return 1;
else
{
if (z < n-1 && trien(x, y, z+1) == 1)
return 1;
if (y < m-1 && trien(x, y+1, z) == 1)
return 1;
if (z > 0 && trien (x, y, z-1) == 1)
return 1;
if (y > 0 && trien(x, y - 1, z) == 1)
return 1;
}
return 0;
}
(C++) Рекурсия. Поиск в лабиринте
Есть вот такая задача:
Кто-нибудь может решал такие задачи на олимпиадах, хочу узнать как именно...
Цитата:
Лабиринт состоит из h уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на m × n участков. На некоторых участках стоят колонны, поддерживающие потолок.
Принц начинает свое путешествие с верхнего уровня. За каждые 5 секунд он может: либо переместиться на любой соседний участок того же уровня (т.е. имеющий общую сторону с тем, где он стоит), если этот участок не содержит колонну; либо сместиться вниз (проломив пол), опять-таки если участок, куда он становится, не содержит колонну.
На одном из участков нижнего уровня Принца ждет Принцесса. Помогите ему добраться до нее, потратив как можно меньше времени.
Входной файл (F.IN): в первой строке находятся числа h, m и n (2≤ h, m, n ≤50).
Далее следуют h блоков, описывающих уровни лабиринта (от верхнего к нижнему).
Каждый блок содержит m строк, по n символов в каждой. «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o» ) обозначает участок с колонной, «1» обозначает положение Принца в начале пути, «2» обозначает положение Принцессы.
Соседние блоки разделены одной пустой строкой.
Выходной файл (F.OUT): одно число - минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Гарантируется, что Принц может это сделать.
Пример
Входной файл:
3 3 3
1..
oo.
...
ooo
..o
.oo
ooo
o..
o.2
Выходной файл:
60
Принц начинает свое путешествие с верхнего уровня. За каждые 5 секунд он может: либо переместиться на любой соседний участок того же уровня (т.е. имеющий общую сторону с тем, где он стоит), если этот участок не содержит колонну; либо сместиться вниз (проломив пол), опять-таки если участок, куда он становится, не содержит колонну.
На одном из участков нижнего уровня Принца ждет Принцесса. Помогите ему добраться до нее, потратив как можно меньше времени.
Входной файл (F.IN): в первой строке находятся числа h, m и n (2≤ h, m, n ≤50).
Далее следуют h блоков, описывающих уровни лабиринта (от верхнего к нижнему).
Каждый блок содержит m строк, по n символов в каждой. «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o» ) обозначает участок с колонной, «1» обозначает положение Принца в начале пути, «2» обозначает положение Принцессы.
Соседние блоки разделены одной пустой строкой.
Выходной файл (F.OUT): одно число - минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Гарантируется, что Принц может это сделать.
Пример
Входной файл:
3 3 3
1..
oo.
...
ooo
..o
.oo
ooo
o..
o.2
Выходной файл:
60
Как я понял, делать надо при помощи рекурсии. Но мой написанный код не работает как надо, т.е. при одном движении вниз на следующий раз движется вверх и так бесконечно.
Код:
Кто-нибудь может решал такие задачи на олимпиадах, хочу узнать как именно...