ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите, пожалуйста!!!
25 сообщений из 26, страница 1 из 2
  1  все
Помогите, пожалуйста!!!
    #38874150
Qwea
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Qwea
Участник
Дан лабиринт размером N*N.Форма лабиринта записана в текстовом файле, стена обозначается символом М, отсутствие стены - символом пробела. Даны координаты мышки в лабиринте(x,y) и координаты сыра(xc,yc). Нужно посчитать длину самого длинного пути выхода из лабиринта. Длина пути определяется числом клеток, на которые должна ступить нога мышки.
...
Рейтинг: 0 / 0
08.02.2015, 14:05
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874191
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NekZ
Участник
Qwea,

Используй волновой алгоритм
...
Рейтинг: 0 / 0
08.02.2015, 16:55
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874195
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
QweaДан лабиринт размером N*N.
Это граф, где каждая вершина - проходимая клетка, а дуга - переход из одной клетки на другую.

QweaНужно посчитать длину самого длинного пути выхода из лабиринта.
При наличии цикла в этом графе, ответ - бесконечность.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
08.02.2015, 17:11
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874197
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Точнее, нет. При условии что
QweaДлина пути определяется числом клеток, на которые должна ступить нога мышки.

задача сводится к подсчёту проходимых клеток, доступных из положения мыши. При чём тут сыр
- неясно.

Если в лабиринте нет изолированных участков, то задача упрощается до подсчёта количества
пробелов в файле, поскольку в этом случае мышь может наступить на абсолютно все проходимые
клетки прежде чем выберется из лабиринта.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
08.02.2015, 17:16
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874227
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Qwea,

Вопрос к С++ не относится.
Если не знаешь как решить задачу - это вопрос по алгоритму. Обсуждается в Программировании.
Если тебе лень решать задачу - иди в форум Работа и сразу публикуй с какой суммой готов расстаться за решение задачи.

Прочитай это: 12553838
...
Рейтинг: 0 / 0
08.02.2015, 18:54
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874259
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
QweaДан лабиринт размером N*N.Форма лабиринта записана в текстовом файле, стена обозначается символом М, отсутствие стены - символом пробела. Даны координаты мышки в лабиринте(x,y) и координаты сыра(xc,yc). Нужно посчитать длину самого длинного пути выхода из лабиринта. Длина пути определяется числом клеток, на которые должна ступить нога мышки.
С коротким путём всё было-бы ясно.

Но вот с длинным у меня есть вопросы. Как его получить?

Может просто посчитать все свободные клетки лабиринта?

Это не длинный? А почему? Обоснуйте.
...
Рейтинг: 0 / 0
08.02.2015, 20:33
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874261
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожет просто посчитать все свободные клетки лабиринта?

Это не длинный? А почему? Обоснуйте.
Это минимально длинный, т.к. еще надо возвращаться из тупиков, т.е. повторно проходить по уже пройденному.

ИМХУ, не считая, правильный ответ: самый длинный путь = бесконечность, ну или сколько там там может пробежать мышь (пока не помрет) шарахаясь из тупика в тупик.
...
Рейтинг: 0 / 0
08.02.2015, 20:38
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874277
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я так понимаю что надо генерировать все (!) маршруты (каким-то образом
дать определение что такое маршрут) и из всех выбрать самый неоптимальный.

Но даже в этой постановке на шаге определения мы можем спорить по поводу
того сколько раз мышь может заходить в один и тот-же тупик. Это сильно влияет
на решение задачи.

Пускай автор даст рисунок лабиринта и ПРИМЕР того где по его мнению
находится САМЫЙ ДЛИННЫЙ ПУТЬ.
...
Рейтинг: 0 / 0
08.02.2015, 21:13
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874283
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Странно, обычно ищут самый короткий путь...
...
Рейтинг: 0 / 0
08.02.2015, 21:37
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874293
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
MasterZivСтранно, обычно ищут самый короткий путь...
Мы не ищем лёгких путей
...
Рейтинг: 0 / 0
08.02.2015, 22:10
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874345
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Qwea, попробуйте разобраться с алгоритмом Дейкстры, возможно получится его изменить.
Сомневаюсь что подразумевается подсчёт пустых клеток. Скорее требуется найти некоторый аналог седлового значения
...
Рейтинг: 0 / 0
09.02.2015, 02:04
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874801
ALKIR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALKIR
Участник
? зачем даны координаты сыра, если мышь должна выйти из лабиринта ?

ищем неоптимальный путь
из условия, если мышка ступит на одну и ту же клетку несколько раз, то в зачет пойдет 1 единица дистации
т.е. мышь может наступить на все клетки до которых она может дойти
если предположить, что это нормальный лабиринт, в котором есть выход, и нет заданных клеток, на которые не может наступить мышь,
то, длинна неоптимального пути будет равна количеству "пробелов" в файле
...
Рейтинг: 0 / 0
09.02.2015, 14:17
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874808
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ALKIRдлинна неоптимального пути будет равна количеству "пробелов" в файле
KO 17234983
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
09.02.2015, 14:25
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874851
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Сыр в условии - вообще не в тему. Неясно совпадает ли сыр с выходом.
...
Рейтинг: 0 / 0
09.02.2015, 15:01
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874860
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСыр в условии - вообще не в тему
Сыр на закусь, т.к. без бутылки тут не разобраться
...
Рейтинг: 0 / 0
09.02.2015, 15:06
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874887
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Полностью согласен. Требуем к сыру координаты бутылку.

Хорошо бы еще и координаты выхода из лабиринта. Вдруг "замуровали демоны" ( C )

 

В пещере каменной нашли наперсток водки,
Комарик жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли стопарик водки,
Бельчонок жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не-нашему, это не по-русски.

В пещере каменной нашли стаканчик водки,
Зайчишка жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли бутылку водки,
Цыпленок жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли графинчик водки,
Кабанчик жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли бочонок водки,
И мишка жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли цистерну водки,
И мамонт жареный лежал на сковородке.
Мало, мало водки, мало и закуски-
Это не по-нашему, это не по-русски.

В пещере каменной нашли источник водки,
И стадо мамонтов паслось на сковородке.
Хватит, хватит водки, хватит и закуски-
Это вот по-нашему, это вот по-русски.
...
Рейтинг: 0 / 0
09.02.2015, 15:23
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874892
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я вот нашёл лабиринт. И хочу попросить автора чтобы он
(вручную) указал здесь самый длинный путь.

От рыбки до моря.



Без клеточек и без подсчёта.

Я хочу просто понять логику ВЫБОРА самого длиннного пути.
...
Рейтинг: 0 / 0
09.02.2015, 15:26
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874899
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonЯ хочу просто понять логику ВЫБОРА самого длиннного пути.
Лично для меня, перебрать все возможные пути и найти из них самый длинный.

Тут правда, вопрос, можно ли ходить по своим следам. Если можно - получаются циклы. Но вообще то, тогда в любом лабиринте > 2 клеток самый длинный путь бесконечность - вошли/вышли, вошли/вышли... Явно вместо водки бутират налит был ))) или другое хорошее психо-активное вещество
...
Рейтинг: 0 / 0
09.02.2015, 15:30
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А сколько раз ходить по циклам? А дважды залядывать в тупик? Топтаться?
...
Рейтинг: 0 / 0
09.02.2015, 15:31
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874919
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
ВОт именно, как правильно заметил Дмитрий Сибиряков, если есть хотя бы один цикл в графе, то макс. путь -- бесконечность.
А тупик уже означает цикл (петля сама на себя через N других вершин), так что тупиков в лабиринте тоже не может быть в такой
постановке вопроса.

А если тупиков не может быть, то любой путь от входа должен приводить к выходу, а если так, то на любой развилке можно идти в любом направлении, и ты должен всё равно дойти до выхода, так должен быть построен этот лабиринт.

Вроде бы так.
...
Рейтинг: 0 / 0
09.02.2015, 15:45
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38874934
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
MasterZivна любой развилке можно идти в любом направлении, и ты должен всё равно дойти до выхода
Не должен если есть хотя бы два пути. Можно начать ходить по кругу, т.е. максимальный путь опять бесконечность.
...
Рейтинг: 0 / 0
09.02.2015, 15:55
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38875099
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Dima TMasterZivна любой развилке можно идти в любом направлении, и ты должен всё равно дойти до выхода
Не должен если есть хотя бы два пути. Можно начать ходить по кругу, т.е. максимальный путь опять бесконечность.

Почему же ?

Цикл будет , но он будет проходить через узел "выход", т.е. таким образом будет разорван.
...
Рейтинг: 0 / 0
09.02.2015, 18:33
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38875165
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
MasterZivDima Tпропущено...

Не должен если есть хотя бы два пути. Можно начать ходить по кругу, т.е. максимальный путь опять бесконечность.

Почему же ?

Цикл будет , но он будет проходить через узел "выход", т.е. таким образом будет разорван.
Код: plaintext
1.
2.
3.
4.
    |----|
    |    |
ВХОД  --  ВЫХОД
    |    |
    |----|

Что мешает пойти по кругу в поисках самого длинного пути?
...
Рейтинг: 0 / 0
09.02.2015, 20:11
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38875178
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
Dimitry SibiryakovПри чём тут сыр
- неясно.

Это, пожалуй, самый актуальный вопрос.
...
Рейтинг: 0 / 0
09.02.2015, 20:46
| Ответить | Цитировать | Написать  
Помогите, пожалуйста!!!
    #38875204
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Dima TMasterZivпропущено...


Почему же ?

Цикл будет , но он будет проходить через узел "выход", т.е. таким образом будет разорван.
Код: plaintext
1.
2.
3.
4.
    |----|
    |    |
ВХОД  --  ВЫХОД
    |    |
    |----|

Что мешает пойти по кругу в поисках самого длинного пути?

То, что по любому из этих путей ты сразу же дойдёшь до выхода.

Ты немного неправильно нарисовал.


Код: plaintext
1.
2.
3.
4.
5.
6.
    
    |----|
    |    |
  ВХОД--ВЫХОД
    |    |
    |----|

Т.е. пойдя по нижнему пути ты уже приходиш на "ВЫХОД" и заканчиваешь путешествие (формируя один маршрут от входа к выходу),
и назад ко входу по центральному маршруту ты идти уже не можешь.

Если бы было можно, то это вообще превращает в бред всю задачу -- ты можешь тогда бесконечно бегать от выхода обратно ко входу, а затем обратно к выходу, и таким образом увеличивать максимальный маршрут до бесконечности.
...
Рейтинг: 0 / 0
09.02.2015, 21:33
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите, пожалуйста!!!
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]