задаача на волновой алгоритм

@tennisru · Регистрация: 10.09.2011

Студворк — интернет-сервис помощи студентам

задан граф m* n, невзвешенный, нужно чтобы все свободные клетки были покрыты маршрутом, проверить возможно ли такое, надо чтобы из исохдной(любой точки графа) пришли в исходную побывай во всех (по каким можно пройти)клетках 1 раз,например
0 0 1 1
1 1 1 1
1 1 0 0
1 1 0 0
ответ Нет

0 0 1 1
1 1 1 1
1 1 1 1
ответ Да

тут можно же применить волновой алгоритм но,r как он дейтвует на квадратной матрице?
верно ли применять тут его?

@Rayne · 06.01.2012, 01:30

Вообще применять для поиска пути можно, вопрос в том можно ли пройти каждую клетку один раз - это уже совсем другое свойство будет, едва ли с алгоритмом связано

@tennisru · 06.01.2012, 08:52 **[ТС]**

можете объясниь как работает волновой алгоритм для двухмерной матрицы лии сылку кинуть?

@Rayne · 08.01.2012, 02:56

http://ru.wikipedia.org/wiki/Волновой_алгоритм , википедия, как обычно.
Если будут какие-то проблемы с написанием - пиши в лс, или на icq лучше, 388529925. Со стандартным алгоритмом отлично разобрался, сейчас улучшаю его по мелочам

Добавлено через 1 час 7 минут
не написано как обратный путь проложить, когда волна достигнет точки Б:

От точки Б в 4 (или 8) направлениях ищём клетку с наименьшим номером волны, записываем её координаты в массив N, далее от неё - следующую клетку с наименьшим номером, и так далее, пока не цикл не достигнет точки А. Точки массива N составят кратчайший путь.

@tennisru · 08.01.2012, 12:15 **[ТС]**

в задаче про волновой алгоритм, я хочу спросить.
Как сделать волновой алгоритм, чтобы он строил новую матрицу расстояний из заданной вершины, чтобы в клетках было расстояние?

например из
1 0 0
0 0 0
0 0 0
взяли произвлдную вершину и сделали вот так
inf 0 1
2 1 2
3 2 3
inf - бесконечность.
на викепедию можете не отправлять, там не написано как это сделать, возможно я не прав

@Rayne · 08.01.2012, 21:03

здесь пример на дельфи. Возникала какая-то странная ошибка с обработчиком клика одной кнопки, перепиши в новую форму если вдруг ошибки возникнут. Оставил черновой вариант, без лишних сообщений что путь не найден и т.д.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179

	задаача на волновой алгоритм 05.01.2012, 13:43. Показов 1225. Ответов 5 Метки нет (Все метки) задан граф m* n, невзвешенный, нужно чтобы все свободные клетки были покрыты маршрутом, проверить возможно ли такое, надо чтобы из исохдной(любой точки графа) пришли в исходную побывай во всех (по каким можно пройти)клетках 1 раз,например 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 0 ответ Нет 0 0 1 1 1 1 1 1 1 1 1 1 ответ Да тут можно же применить волновой алгоритм но,r как он дейтвует на квадратной матрице? верно ли применять тут его? 0

@Rayne 76 / 62 / 23 Регистрация: 11.07.2009 Сообщений: 730
	06.01.2012, 01:30
	Вообще применять для поиска пути можно, вопрос в том можно ли пройти каждую клетку один раз - это уже совсем другое свойство будет, едва ли с алгоритмом связано 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	06.01.2012, 08:52 [ТС]
	можете объясниь как работает волновой алгоритм для двухмерной матрицы лии сылку кинуть? 0

@Rayne 76 / 62 / 23 Регистрация: 11.07.2009 Сообщений: 730
	08.01.2012, 02:56
	http://ru.wikipedia.org/wiki/Волновой_алгоритм , википедия, как обычно. Если будут какие-то проблемы с написанием - пиши в лс, или на icq лучше, 388529925. Со стандартным алгоритмом отлично разобрался, сейчас улучшаю его по мелочам Добавлено через 1 час 7 минут не написано как обратный путь проложить, когда волна достигнет точки Б: От точки Б в 4 (или 8) направлениях ищём клетку с наименьшим номером волны, записываем её координаты в массив N, далее от неё - следующую клетку с наименьшим номером, и так далее, пока не цикл не достигнет точки А. Точки массива N составят кратчайший путь. 1

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	08.01.2012, 12:15 [ТС]
	в задаче про волновой алгоритм, я хочу спросить. Как сделать волновой алгоритм, чтобы он строил новую матрицу расстояний из заданной вершины, чтобы в клетках было расстояние? например из 1 0 0 0 0 0 0 0 0 взяли произвлдную вершину и сделали вот так inf 0 1 2 1 2 3 2 3 inf - бесконечность. на викепедию можете не отправлять, там не написано как это сделать, возможно я не прав 0