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

Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. - C++

Восстановить пароль Регистрация
 
maximality
Сообщений: n/a
08.12.2011, 17:55     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #1
Доброго времени суток всем!
Вот такая задача, ничего не могу даже сообразить по ней, подкиньте идеи, пожалуйста (ну или код в C++ )
Дан массив А(м х м), заполненный "1" и "0". С клавиатуры вводятся координаты i,j двух точек мас-сива. Определить, существует ли путь от первой ко второй точке, состоящий из одних "0". Вывести найденный путь в удобной форме.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 17:55     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки.
Посмотрите здесь:

C++ Массив состоит из нулей и единиц. Сформировать массив,состоящий из нулей и подсчитать их количество
C++ Наименьший путь от одной точки до другой
Найти самый короткий путь от точки до точки в матрице C++
Как найти координаты точки на прямой удаленной от заданной точки на х C++
C++ не получается задачка (Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.12.2011, 21:06     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #2
1) Поиск кратчайшего пути в графе
2) Поиск пути в графе
В данном случае граф несколько специфический, но это не помешает решить задачу
maximality
Сообщений: n/a
08.12.2011, 22:10     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #3
Цитата Сообщение от odip Посмотреть сообщение
1) Поиск кратчайшего пути в графе
2) Поиск пути в графе
В данном случае граф несколько специфический, но это не помешает решить задачу
Ну ведь путь как-то еще вывести надо.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
09.12.2011, 05:11     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #4
Вывести путь не проблема
Выводим массив из "0", "1"
Например путь указывается цифрами "2" вместо "0"
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.12.2011, 06:30     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #5
maximality, Заводишь еще один массив m*m. Заполняешь его значениями -1. Значению второй точки ставишь в этом массиве 0 и вторую точку заносишь в стек. Далее делашь так:
Берешь очередную точку из стека и смотришь (по первому массиву) куда из нее можно пойти. Если можно куда-то перейти и эта точка во втором массиве равна -1, то эту точку заносишь в стек а значение ее во втором массиве делаешь: значение очередной точки из стека (во втором массиве)+1.
Можешь продолжать делать таким образом пока стек не опустеет.
Затем смотришь значение 1-ой точки во втором масссиве. Если равно -1, то пути нет.
Если не равно -1, то берешь значение 1-ой точки во втором массиве и идешь обратно по убыванию до 0 (это и будет кратчайший путь).

Добавлено через 46 минут
маленькая поправка: стек заменить на очередь.
Yandex
Объявления
09.12.2011, 06:30     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки.
Ответ Создать тему
Опции темы

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