|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
27.10.2011, 20:55 | #1 |
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
Прохождение лабиринта (волновой алгоритм)
Добрый день.
Решаю задачу №129 с сайта acm.mipt.ru. http://acm.mipt.ru/judge/problems.pl...2a362a981a81c7 Для тех, кто не знает: это сайт с автоматической проверкой написанных программ с помощью некоторого количества тестов (версия компилятора С++ 3.4.6). По сути дела, задача сводится к написанию программы для прохождения лабиринта. На входе указывается его размерность, количество и координаты препятствий, а также стартовая и конечная позиции. На выходе программа выдает длину пути и его описание. На данный момент я написал следующую программу (Т.к. весь код не помещается в одно сообщение, он поделен на две части. Возможно, он кажется большим, но это только из-за того, что я соблюдал структурность). Код:
Последний раз редактировалось Alexander_A; 27.10.2011 в 22:08. |
27.10.2011, 20:57 | #2 |
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
Продолжение кода.
Код:
Подскажите, где может быть ошибка. P.S.: Буду рад, если кто-нибудь сможет предложить нестандартные примеры для тестирования моей программы. Тесты принимаются как в формате входных данных (как в примере на сайте), так и в форме рисунка лабиринта (прямоугольного леса). Жду ваших предложений и интересных тестов. Заранее, спасибо за ответы. Последний раз редактировалось Alexander_A; 27.10.2011 в 21:12. |
27.10.2011, 21:36 | #3 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
1) Вы бы хоть на подпрограммы разбили. От такой простыни натурально дурно.
2) На каждом шаге волны перебирать наново весь массив - это крутой подход. Рискуете на очередном тесте не уложиться по времени. Вообще, причина провала на пятом тесте - "неверный ответ"? 3) Я так понимаю, что последний блок - это тестовая печать, которой нет в сдаваемой программе? 4) Из условия непонятно, можно ли проходить по краю леса (т.е. через узлы вида (0,3)). Пробовали разрешать это программе? |
27.10.2011, 22:03 | #4 | ||||
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
Цитата:
Цитата:
А причину провала вы правильно определили. Цитата:
Цитата:
"По крайним просекам преступник также может перемещаться". Вообще, эту фразу можно трактовать по-разному. В зависимости от того, что считать просекой. |
||||
27.10.2011, 22:17 | #5 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Трудности перевода
Цитата:
Тогда отдельно обращаю внимание, что в нынешнем варианте все координаты жёстко больше нуля. |
|
27.10.2011, 22:23 | #6 |
Форумчанин
Регистрация: 20.10.2011
Сообщений: 433
|
Чувствую себя ****мом, если сравнить задачи те, что я пытаюсь решить и эти ...
Ох ... |
28.10.2011, 18:58 | #7 | |
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
Цитата:
После того как я отредактировал код, убрав возможность передвижения по периметру леса, программа стала выдавать неверный ответ на четвертом тесте. Замечу, что в примере с сайта провода начинаются на краю леса. Т. е. преступник теоретически мог там пройти. Думаю, что проблема в чем-то другом. |
|
28.10.2011, 21:20 | #8 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
И что значит - "убрав"? В приведённом здесь варианте программа, насколько могу видеть, не пытается вести волну через клетки с одной из координат ноль, соответственно, на карте Код:
Или я ошибаюсь? |
|
28.10.2011, 21:37 | #9 | |
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
Цитата:
Но у вас в четвертой строке ошибка, в примере на сайте строка начинается с 0, а не с 2. Код:
Последний раз редактировалось Alexander_A; 28.10.2011 в 22:23. |
|
30.10.2011, 19:52 | #10 |
Пользователь
Регистрация: 27.10.2011
Сообщений: 13
|
После долгих поисков я наконец-то нашел ошибку. Оказалось, что проблема была в той части программы, которая наносит провода на карту. Я не учел то, что коэффициент «В» уравнения «У = К*Х + В» может быть нецелым числом.
Теперь программа работает без ошибок. Спасибо Abstraction за уделенное внимание. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Надо поправить код.(Волновой алгоритм, Pascal) | DoubleTrouble | Помощь студентам | 1 | 26.06.2011 18:23 |
Волновой алгоритм сферическая волна | ArtInt | Общие вопросы Delphi | 2 | 24.04.2010 15:43 |
Алгоритм прохождения лабиринта | PAVEL315 | Общие вопросы Delphi | 13 | 02.01.2010 01:22 |
Волновой алгоритм поиска | Merkator | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 8 | 12.02.2009 16:15 |
Прохождение подземного лабиринта Джаффара | МаксимNEWProgramm | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 12.04.2008 19:52 |