Сижу пухну

Если кто-нибудь решит это через час я ему памятник поставлю

"Помоги спелеологу"

Вы попали в трехмерную пещеру и вам необходимо найти кратчайший путь к выходу. Пещера представляет собой куб, в котором есть проходы. Перемещение в любом направлении (вверх, вниз, вправо, влево, вперед, назад) занимает ровно одну минуту. Перемещаться по диагонали и через стены пещеры не разрешается. Возможен ли выход из такой пещеры и если «да», то сколько времени вам понадобится?

Входные данные

Входной файл INPUT.TXT состоит из описаний нескольких пещер. Описание каждой пещеры начинается со строки с тремя целыми числами L, R и C ( все числа не больше 30). L – количество уровней в пещере, R, C – количество строк и колонок в плане каждого этажа. Далее следуют L блоков данных, каждый из которых представляет R строк, содержащих C символов. Каждый символ описывает ячейку пещеры. Стены обозначены символом ‘#’, а ячейки где проход разрешен ‘.’ (точкой) . Начальная позиция указывается символом ‘S’, а выход символом ‘E’. После описания каждого уровня пещеры следует ровно одна пустая строка. Ввод завершается строкой, содержащей три нуля в качестве L, R, C.

Выходные данные

Каждой пещере в выходном файле OUTPUT.TXT должна соответствовать одна строка. Если Вы нашли выход, то вид строки следующий:

Вышли за x минут.

где x кратчайшее время, за которое возможен выход. Если вам не удалось найти выход, напечатайте строчку:

Ловушка!

Пример входных данных

3 4 5

S....

.###.

.##..

###.#

 

#####

#####

##.##

##...

 

#####

#####

#.###

####E

 

1 3 3

S##

#E#

###

 

0 0 0

Пример выходных данных

Выщли за 11 минут.

Ловушка!

Волновой алгоритм надо принимать. Для двухмерной карты считатся так (для трёхмерной, впрочем, также ):

Берётся выходная клетка. Вокруг неё во всех клетках пишем единичку. Переходим в каждую из этих клеток. Вокруг каждой из них в пустых клетках пишем двойку. Переходим в каждую клетку с двойкой... И так до конца. От входа выбираем соседнюю клетку с самым маленьким числом. У неё - опять с самым маленьким. Получается наикратчайший маршрут к выходу.

Наименьшее число в клетке у выхода и будет число минут на кратчайший маршрут в данном случае. Если всё у входа пусто - ловушка.

А можно подробнее
Что делать конкретно? :o

Это тебе к классическим алгоритмам: волна и т.п.

Что могу предложить сразу: заводишь массив пещеры, и заполняешь все его пустые ячейки, начиная от спелеолога следующим образом: соседние от спелеолога проходимые ячейки заполняешь единицами, соседние с ним - двойками и т.п. Если возникает конфликт, то записываешь меньшее число. Результат: перед выходом у тебя будет ячейка с числом минут, а двигаясь по ним назад, ты сможешь получить траекторию.

>Что могу предложить сразу: заводишь массив пещеры, и заполняешь все его пустые ячейки,
А как?

Можешь гнать волну и от входа и от выхода - иногда так быстрее.
2Balancer
Родственные души, однако

>Можешь гнать волну и от входа и от выхода
Т.е.?

Я программить не умею, но тут припело :huh:

2Super Tomcat
Не понял
Пещеру тебе все равно в массив считывать. Алгоритм заполнения рекурсивный. Если хочешь, могу завтра подкинуть исходник.

>Не понял
Это я ничего не понимаю
Мне бы нужно что-нибудь, что сгодилось бы за программу до 17:00
>Алгоритм заполнения рекурсивный.
 :o
>Если хочешь, могу завтра подкинуть исходник.
Будет интересно

Увы, у меня рабочий день закнчивается прямо сейчас

>Увы, у меня рабочий день закнчивается прямо сейчас
Очень жаль!
Но все равно спасибо

Вот готовая программка на PHP

1. <?
2.     // Считать первую непустую строку.
3.     function get_not_empty_string($file_handle)
4.     {
5.         while(!feof($file_handle))
6.         {
7.             $s = fgets($file_handle);
8.             if(trim($s))
9.                 return $s;
10.         }
11.         return "";
12.     }
13.  
14.     
15.     $fh=fopen("data.txt","rt");
16.     for(;;)
17.     {
18.         // Считываем строку и разбиваем на три числа, отделённых пробелами
19.         list($l,$r,$c) = preg_split("/\s+/", get_not_empty_string($fh));
20.         
21.         // Выход, если три нуля или конец файла
22.         if($l==0 && $r==0 && $c==0 || feof($fh))
23.             break;
24.  
25.         // Сброс начальных данных
26.         $start=0;
27.         $exit=0;
28.         $empty=array();
29.  
30.         // Считываем очередной блок данных
31.         for($z=0; $z<$l; $z++)
32.         {
33.             for($y=0; $y<$r; $y++)
34.             {
35.                 $row = get_not_empty_string($fh);
36.                 for($x=0; $x<$c; $x++)
37.                 {
38.                     $char = $row[$x];
39.                     if($char=="S")
40.                         $start=array($x,$y,$z);
41.                     if($char=="E")
42.                         $exit=array($x,$y,$z);
43.                     $empty[$z][$y][$x] = ($char=="#") ? 0 : 1;
44.                 }
45.             }
46.         }
47.  
48.         // Создаём пустой массив путей
49.         $array=array();
50.  
51.         // Вычисляем путь
52.         wave($exit[0],$exit[1],$exit[2]);
53.  
54.         // Для демонстрации печатаем карту пути
55.         for($z=0; $z<$l; $z++)
56.         {
57.             echo "\n";
58.             for($y=0; $y<$r; $y++)
59.             {
60.                 for($x=0; $x<$c; $x++)
61.                 {
62.                     $char=$array[$z][$y][$x];
63.                     echo $char ? ($char<10?$char:chr(ord('A')+$char-10)) : ".";
64.                 }
65.                 echo "\n";
66.             }
67.         }
68.  
69.         // Печатаем время
70.         $time=$array[$start[2]][$start[1]][$start[0]]-1;
71.         echo $time>0?"$time минут\n":"Ловушка!\n";
72.  
73.     }
74.  
75.     function wave($x,$y,$z,$n=1)
76.     {
77.         global $array, $empty, $l, $r, $c;
78.         // $array - волновой массив
79.         // $empty - массив препятствий
80.         // x/y/z - координаты тестируемой точки
81.         // l/r/c - размеры лабиринта
82.         // $n = уровень этой точки
83.  
84.  
85.         // Если вышли за пределы лабиринта - ничего не делаем
86.         if($x<0 || $x>=$c || $y<0 || $y>=$r || $z<0 || $z>=$l)
87.             return;
88.         
89.         // Если клетка занята, то ничего не делаем
90.         if(!$empty[$z][$y][$x])
91.             return;
92.  
93.         // Если клетку уже проверяли и путь более оптимальный, то опять ничего не делаем.
94.         if($array[$z][$y][$x] && $array[$z][$y][$x]<$n)
95.             return;
96.  
97.         // установим тестируемую клетку в нужный уровень
98.         $array[$z][$y][$x]=$n;
99.  
100.         // Новый уровень
101.         $n++;
102.  
103.         // Установим пустые соседние клетки
104.         // Проверяем в лоб, так экономичнее
105.         wave($x-1,$y,$z,$n);
106.         wave($x+1,$y,$z,$n);
107.         wave($x,$y-1,$z,$n);
108.         wave($x,$y+1,$z,$n);
109.         wave($x,$y,$z-1,$n);
110.         wave($x,$y,$z+1,$n);
111.     }
112.  
113.  
114. <font size="-2" color="#808080">[b]?[/b]>

[/html_font]
Пример вывода для вышеприведённых тестовых данных:

1. CBA98
2. D...7
3. E..56
4. ...4.
5.  
6. .....
7. .....
8. ..5..
9. ..432
10.  
11. .....
12. .....
13. .....
14. ....1
15. 11 минут
16.  
17. ...
18. .1.
19. ...
20. Ловушка!

Пардон, слово "минут" ещё просклонять нужно ("1 минута", "2 минуты", "5 минут"). Ну да лениво... Сам разберёшься

PHP был выбран из-за более простой работы с многомерными массивами

Кирилл, 25.09.2003 15:40:24:

Если возникает конфликт, то записываешь меньшее число.

 

Кстати, такой простой финт я и упустил. Сильно упростило дело, т.к. я вначале сдуру стал лепить рекурсию "ограниченного распространения" (не знаю, как правильно). Т.е. сперва проверка всех двоек, потом всех троек и т.п. Угрохал на это дело половину всего времени

Родственные души, однако

 

Интересно бы этот же алгоритм на Хаскелле реализовать... Наверняка сильно короче вышло бы

Спасибо большое, Balancer!
Вы меня просто выручили!
Еще раз спасибо!!!!

Интересно - волна. В теории графов представленная задача - это из матрицы смежности построить матрицу достижимости с оценкой пути. А откуда такое название - волна - честно не слышал.

Mishka, 25.09.2003 17:11:44:

Интересно - волна. В теории графов представленная задача - это из матрицы смежности построить матрицу достижимости с оценкой пути. А откуда такое название - волна - честно не слышал.

 

Подобный волновой алгоритм придумал какой-то японец вроде, для трассировки печатных плат.
Я уже не помню точно.
Давно это было, годах так в 89-90.
Я правда эту прогу видел на Прологе.

>Интересно - волна. В теории графов представленная задача - это из матрицы смежности построить матрицу достижимости с оценкой пути...
...
...
...

Мне на этот форум заходить стыдно Хоть бы словечко знакомое встретить

> Спасибо большое, Balancer!
> Вы меня просто выручили!
> Еще раз спасибо!!!!

А что?
Задание по программирование делал?
Непохоже вроде:

> Я программить не умею, но тут припело

В качестве первой задачки по учебному курсу - врядь ли

В инете нашел... ничего похожего не дает

Благородным делом, стало быть, занялся - друга выручал. Или подружку

ComputerMage, 25.09.2003 21:42:28:

Подобный волновой алгоритм придумал какой-то японец вроде, для трассировки печатных плат.
Я уже не помню точно.
Давно это было, годах так в 89-90.
Я правда эту прогу видел на Прологе.

 

Да какой японец, блин. Это давно известная штука в теории графоф - лабиринт любой размерности представляется графом - комнаты - вершины, а проходы - ребра. Как они реально в пространстве представлены - никого не волнует. На ребра можно навесить веса. Если граф ориентированный, то проход имеет направление. Соответственно можно сделать двери с замочками. Граф можно представлять разными способами. Один из них - это матрица размера NxN, где N число вершин. Если в позиции A[i,j] стоит число отличное от 0, то существует ребро между вершиной i и j - если граф не направленый, то в позиции A[j,i] стоит тоже число (матрица получается симметричной относительно главной диагонали), а, если ориентированный граф, то там может быть другое число (возвратиться обратно может занять больше времени), а может и 0 - назад ходу нет. Далее строится матрица достижимости из данной матрицы - она показывает, есть ли путь из вершины k в вершину l. Кроме указания достижимости, можно и веса посчитать. Вообще-то часто ищут не только самый короткий путь - это уже оптимизация на графах. Задачка коммивояжора тоже графофская.

Кому интересно, можно книжки разные почитать - это примерно 2 курс математического факультета (правда годовой, а потом еще спецкурсы). Есть книжки Зыкова или Евстегнеева. Еще много есть, но всех не помню - мы по ним учились в основном.

И эти результаты уже давно известны. Я закончил в 1986 - уже монографии были опубликованы достаточно давно.

ComputerMage, 26.09.2003 04:42:28:

Подобный волновой алгоритм придумал какой-то японец вроде, для трассировки печатных плат.
Я уже не помню точно.
Давно это было, годах так в 89-90.

 

Да вы смеетесь Он наверняка сотню лет известен. И вообще довольно очевиден. Я его сам "изобрел", когда Color Lines на ZX Spectrum писал Будучи еще школьником...

2Super Tomcat
К посту Balancer'а мне нечего добавить - мой пример на Дельфи практически полностью его повторяет.

Китайцем он был придумал. Звали китайца Ли. А вот год - это вопрос!

Alesandro, 26.09.2003 13:29:59:

Китайцем он был придумал. Звали китайца Ли. А вот год - это вопрос!

 

Это тот, который в IBM $1,000,000 зарплаты получил и участвовал в создании 8086?

Как я говорил, я графы проходил на 2 курсе - это 1982-1983 годы. Уже тогда в монографиях это было. Никогда алгоритм не назывался по имени, потому как тривиален - полным перебором идет решение. Причем рекурсия здесь элементарная, так что выражается несколькими вложенными циклами. Я попробую поднять американскую литературу и посмотреть, есть ли у этого алгоритма собственное имя.

Кстати, Евстигнеев-то из Новосибирского универа вроде, может кто может там его найти и спросить?