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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
maximality
Сообщений: n/a
#1

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

08.12.2011, 17:55. Просмотров 725. Ответов 4
Метки нет (Все метки)

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

Найти самый короткий путь от точки до точки в матрице - C++
Народ, помогите... Такая задача, имеется массив символов(char arr) в котором в рандомных местах установлены препятствия(к примеру символы...

Найти минимальное расстояние от точки до точки - C++
В последнем цикле, который должен находить минимальное расстояние от точки до точки и его индекс, какая-то ошибка. Немогу её увидеть....

Наименьший путь от одной точки до другой - C++
Имеются N-точек, соединенных отрезками. Составить программу, находящую наименьший путь от одной точки до другой. Для реализации желательно...

Заменить все запятые на точки, а точки - на восклицательные знаки - C++
Помогите! 19. Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество сделанных...

Отсортировать и вывести точки по удаленности от некоторой заданной точки - C++
доброе время суток )помогите пожалуйста с задачкой,если кому не сложно ) На вход подается некоторое количество точек в пространстве...

Задача (вывести длину кратчайшего пути от точки до точки.) - C++
Пишу задачу, нужно вывести длину кратчайшего пути от точки до точки. проблема в том, что после генерации массива и задания ему...

Дан двумерный массив размером nm, заполненный случайным образом. Найти сумму отрицательных элементов - C++
Помогите, пожалуйста. Дан двумерный массив размером nm, заполненный случайным образом. Найти сумму отрицательных элементов.

найти точки пересечения y = ax^3 + bx^2 + cx + d и y = kx + m - C++
Задача: Определить, пересекаются ли линии y = ax^3 + bx^2 + cx + d и y = kx + m. Если пересекаются, найти точки пересечения ...

Дан массив n*m заполненный случайными числами. Найти минимальный эл-т в заданной строке и вывести его индексы - C++
В С++ builder 6. чет не работает програмка. randomize(); int min=1000000,i,j,n,m,a; cout<<"n="; cin>>n; cout<<"m="; ...

Найти точки экстремума функции - C++
Вечер добрый! Собственно вопрос: имеется такая функция f(x) = (1-x)^4 + 3*sin(x) +2*cos(x) Нужно найти в ней min и max (на графике...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
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
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
09.12.2011, 05:11     Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. #4
Вывести путь не проблема
Выводим массив из "0", "1"
Например путь указывается цифрами "2" вместо "0"
valeriikozlov
Эксперт C++
4669 / 2495 / 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. Найти путь, состоящий из нулей, от точки до точки.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru