|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
29.10.2009, 16:54 | #1 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Задача на графы типа лабиринт
Есть такая задача:
8—9.4. «Хитрый офис». Имеется прямоугольное одноэтажное офисное здание размера n x m комнат. При этом между какими-то соседними комнатами стоят глухие стены, а между какими-то имеются двери. Двери из здания наружу проектом не предусмотрены. Проблема заключается в том, что офисный компьютер, управляющий дверями, сошел с ума и, когда человек входит в какой-то офис, компьютер закрывает и блокирует дверь, через которую человек вошел, и дверь по левую сторону от вошедшего (если эта дверь в комнате существует). Иными словами, офис можно проходить или прямо, или поворачивая направо. Когда человек выходит из комнаты, блокировки со всех ранее заблокированных дверей снимаются. Клерк хочет пройти из своего офиса в офис начальника. Сможет ли он это сделать? Если сможет, через какое минимальное количество офисов (не считая своего офиса и офиса начальника) ему необходимо будет пройти? В начале все двери разблокированы. Также из своего офиса клерк может выйти в любую имеющуюся дверь. Формат ввода: В первой строке входного файла содержатся два натуральных числа n и m (1 <= n,m <= 20) — размеры здания. Далее графическим образом задается план здания: 2n + 1 строк по 2m + 1 символов в каждой. На плане символами «-» (дефис), «|» (вертикальная черта) и «+» (плюс) обозначены стены, символами « . » (точка) — двери, «*» (звездочка) — офисы, «С» («С» латинское заглавное) — офис клерка, «В» («В» латинское заглавное) — офис начальника. Четыре символа, смежные с символами офисов, всегда либо стены, либо двери (см. пример). Формат вывода: В первой строке выходного файла содержится либо строка NO, если клерк пройти к начальнику не сможет, либо YES, если сможет. В последнем случае вторая строка должна содержать целое число — количество офисов, через которые пройдет клерк на своем пути. Пример 1: input.txt 1 2 +-+-+ |C|B| +-+-+ output.txt NO Пример 2: input.txt 3 3 +-+-+-+ |B.*.*| +.+.+.+ |*|C|*| +.+-+.+ |*.*.*| +-+-+-+ output.txt YES 7 Я думаю, что алгоритм такой: - Составить граф на основе входа - Выбрать наименьшую дугу Вот то, что я сделал за 3 дня копания : Код:
|
29.10.2009, 18:06 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Решение - обход в ширину с начальной клетки до тех пор, пока не посетим искомую клетку.
Если это ваша первая задача на графы, советую начинать с чего-нибудь еще более простого в плане алгоритма (например, простой BFS без "левых ограничений"), и значительно более простого в плане кодинга (потренируйтесь на 0-1 матрицах). Когда натренируетесь на проостых задачах, с вот такими проблем не будет - так как они стандартные и ничего, кроме набитой руки, сдесь не требуется. По поводу BFS - для каждого элемента стека так же храним, откуда мы пришли - тогда даже не надо ничего блокировать/деблокировать, просто проверяем 2 возможных ветвления. |
29.10.2009, 20:23 | #3 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
BFS - это и есть поиск в ширину?
И еще, можно примеры простых задач? |
29.10.2009, 21:07 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Breadth-first search, он самый. В википедии и на сайтах алгормитмики есть и реализация, и объяснение, и доказательство. 2 самые простые задачи на эту тему:
1. Дана матрица из 0 и 1. Даны начальная координата и конечная координата (х и у двух клеток). Найти самый короткий путь между ними (путь существует, "двигаться" можно с клетки с нолем в любую соседнюю клетку с нолем). 2. Почти то же самое, но цель - найти выход из лабиринта. Дана координата клетки, из которой можна покинуть лабиринт и начальная координата "жертвы лабиринта". Найти длину кратчайшего пути к выходу. Таких задач много на АСМ-сайтах для новичков, можете потренироватся там. Сразу будете видеть, правильно ли решаете, а в форумах/обсуждениях сможете найти помощь относительно некоторых частых вопросов и проблем. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача на применение пользовательского типа запись | Маськ@ | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 07.05.2009 22:28 |
Задача (на графы) | Witaliy | Помощь студентам | 6 | 14.02.2009 17:47 |
Задача на Турбо Паскаль "Лабиринт" | H[o][o]K | Помощь студентам | 1 | 17.12.2007 18:46 |