Форум программистов, компьютерный форум CyberForum.ru

Определить является ли лабиринт правильным - C++

Восстановить пароль Регистрация
 
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
02.02.2014, 13:24     Определить является ли лабиринт правильным #1
карта представляет собой лабиринт 1=стена, 0=проход
карта представляет собой лабиринт
надо определить является ли лабиринт правильным
правильный лабиринт - такой лабиринт, в котором из любого места в любое другое можно попасть только одним способом.

Пример.
1 1 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1
1 1 1 1 0 1
1 1 1 1 1 1
1 1 1 1 1 1
Это неправильный лабиринт.

1 1 1 1 1 1
1 0 0 0 0 1
1 1 1 1 0 1
1 1 1 1 0 1
1 1 1 1 1 1
1 1 1 1 1 1
Правильный.



1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1
Неправильный
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 13:24     Определить является ли лабиринт правильным
Посмотрите здесь:

C++ Определить, является ли x четным
Определить, является ли строка правильным скобочным выражением (Перевод кода из Паскаля в С++) C++
C++ Проверить является ли скобочное выражение правильным
Определить является ли лабиринт правильным. C++
Определить, является ли текст является записью четного числа в семеричной системе C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
02.02.2014, 13:53     Определить является ли лабиринт правильным #2
virtuos553, если я правильно понял, то просто пробегаете по всему двумерному массиву и проверяете, чтобы каждому нолику соответствовал ещё хотя бы один с любой из четырех сторон. Так же есть вырожденный случай, когда нолик один.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
02.02.2014, 14:04     Определить является ли лабиринт правильным #3
nexen, сходу можно придумать контрпример. Тут нет одиночных нулей, но из синей ячейки в зеленую ведет 0 путей.
1 1 1 1 1 1
1 0 1 1 1 1
1 0 1 1 0 1
1 0 1 1 0 1
1 1 1 1 0 1
1 1 1 1 1 1
mms_ua
35 / 35 / 5
Регистрация: 06.09.2010
Сообщений: 71
02.02.2014, 15:14     Определить является ли лабиринт правильным #4
Правильный лабиринт - лабирит которой будет пройден весь, если на каждом перекрестке сворачивать в крайний проход по одну и ту же руку. Отмечаете пройденные ветви, если после перекрестка попадаете в уже посещенную ветвь, тогда проверяете лабиринт на присутсвие "ноликов". Дальше все очевидно...
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
02.02.2014, 22:53  [ТС]     Определить является ли лабиринт правильным #5
можете помочь с кодом?
Yandex
Объявления
02.02.2014, 22:53     Определить является ли лабиринт правильным
Ответ Создать тему
Опции темы

Текущее время: 16:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru