Доброго времени суток.
Есть массив размерностью X на X (в данном случае 4 на 4) в котором некоторые ячейки заняты "-1"
Подскажите пожалуйста как выполнить проверку на то можно ли пройти от одной стороны массива до другой (с право на лево или снизу вверх) по пути из "-1" как показано на рисунке:
Прохождение по массиву
-
- beginner
- Сообщения: 49
- Зарегистрирован: 28 июн 2010, 16:46
- Версия LabVIEW: 7.1
- Откуда: Россия
- Контактная информация:
-
mzu2006
- doctor
- Сообщения: 2456
- Зарегистрирован: 16 авг 2008, 02:12
- Награды: 3
- Версия LabVIEW: 7.1 10 11 12
- Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
- Контактная информация:
Re: прохождение по массиву
Из простого напрашивается реализация c перебором типа flood fill, используя поочерёдно все значения =-1 на начальной границе массива как затравки (seed).
Отличие от flood fill в том, что остановку рекурсии делать по достижении границы. Из рекуррентной функции возвращать true/false флаг: достигли или не достигли границы.
Если версия позволяет сделать рекурсию, то простая реализация совсем проста: http://en.wikipedia.org/wiki/Flood_fill
Если нет, то нужно использовать очереди, или альтернативные реализации (fast fill, например).
Если есть желание распараллелить процесс, то элегантную ООП идею для реализации рекурсии-распараллеливания можно позаимствовать отсюда: http://expressionflow.com/2009/11/10/un ... -dataflow/ Там, правда надо будет немного доработать.
Отличие от flood fill в том, что остановку рекурсии делать по достижении границы. Из рекуррентной функции возвращать true/false флаг: достигли или не достигли границы.
Если версия позволяет сделать рекурсию, то простая реализация совсем проста: http://en.wikipedia.org/wiki/Flood_fill
Если нет, то нужно использовать очереди, или альтернативные реализации (fast fill, например).
Если есть желание распараллелить процесс, то элегантную ООП идею для реализации рекурсии-распараллеливания можно позаимствовать отсюда: http://expressionflow.com/2009/11/10/un ... -dataflow/ Там, правда надо будет немного доработать.
Правила форума (Forum rules in Russian)
rm -rf /mnt/windows
rm -rf /mnt/windows
-
- beginner
- Сообщения: 49
- Зарегистрирован: 28 июн 2010, 16:46
- Версия LabVIEW: 7.1
- Откуда: Россия
- Контактная информация:
Re: Прохождение по массиву
mzu2006, спасибо конечно за статьи но честно говоря ничего н епонятно....
-
Eugen Graf
- guru
- Сообщения: 6502
- Зарегистрирован: 13 ноя 2007, 02:20
- Награды: 4
- Версия LabVIEW: 2009
- Откуда: Saarbrücken
- Контактная информация:
Re: Прохождение по массиву
Моя идея:
Если взять For Loop с автоиндексацией.
В первой итерации у нас имеется первая строка.
Берём Search 1D Array и находим индекс элемента -1 и запоминаем в сдвиговом регистре.
Во второй итерации у нас вторая строка.
Берём Search 1D Array и находим индекс элемента -1, сравниваем с тем что запомнили в сдвиг. регистре при прошлой итерации, запоминаем в сдвиговом регистре, если >=.
И так далее пока не закончатся строки или Search 1D Array не выдаст -1 или индексы не будут >= (For Loop тоже можно заранее прекратить).
Если взять For Loop с автоиндексацией.
В первой итерации у нас имеется первая строка.
Берём Search 1D Array и находим индекс элемента -1 и запоминаем в сдвиговом регистре.
Во второй итерации у нас вторая строка.
Берём Search 1D Array и находим индекс элемента -1, сравниваем с тем что запомнили в сдвиг. регистре при прошлой итерации, запоминаем в сдвиговом регистре, если >=.
И так далее пока не закончатся строки или Search 1D Array не выдаст -1 или индексы не будут >= (For Loop тоже можно заранее прекратить).
-
mzu2006
- doctor
- Сообщения: 2456
- Зарегистрирован: 16 авг 2008, 02:12
- Награды: 3
- Версия LabVIEW: 7.1 10 11 12
- Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
- Контактная информация:
Re: Прохождение по массиву
eg, в той форме в которой задача поставлена, в каждой строке может быть больше одного элемента, содержащего "-1". Кроме того, множество всех элементов, содержащих -1 может быть овсем не простое. Например, такое:
0 - это "-1", X - всё, что угодно другое
Если расширять твой алгоритм на такие случаи, то он приведёт к одному из вариантов Fast Fill, реализованному, например, в моём решении на конкурс с пятном:
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение номер 2)
Код: Выделить всё
XXXX0X
000X0X
0X000X
0XXXXX
Если расширять твой алгоритм на такие случаи, то он приведёт к одному из вариантов Fast Fill, реализованному, например, в моём решении на конкурс с пятном:
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение номер 2)
Последний раз редактировалось mzu2006 04 ноя 2010, 01:19, всего редактировалось 1 раз.
Правила форума (Forum rules in Russian)
rm -rf /mnt/windows
rm -rf /mnt/windows
-
mzu2006
- doctor
- Сообщения: 2456
- Зарегистрирован: 16 авг 2008, 02:12
- Награды: 3
- Версия LabVIEW: 7.1 10 11 12
- Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
- Контактная информация:
Re: Прохождение по массиву
V1taliy2009, так а что непонятно, спрашивай.
Для того, чтобы написать программу, ищущую путь через массив надо:
1. Разобраться с тем как работает Flood Fill.
2. Реализовать это на
3. Поменять условие окончания работы на "достижение границы"
Начни делать, и мы тебе поможем
V1taliy2009, условие задачи надо уточнить. Например, могут ли быть такие "пути из -1" как я показал в предыдущем посте?
Для того, чтобы написать программу, ищущую путь через массив надо:
1. Разобраться с тем как работает Flood Fill.
2. Реализовать это на
3. Поменять условие окончания работы на "достижение границы"
Начни делать, и мы тебе поможем
V1taliy2009, условие задачи надо уточнить. Например, могут ли быть такие "пути из -1" как я показал в предыдущем посте?
Правила форума (Forum rules in Russian)
rm -rf /mnt/windows
rm -rf /mnt/windows
-
- beginner
- Сообщения: 49
- Зарегистрирован: 28 июн 2010, 16:46
- Версия LabVIEW: 7.1
- Откуда: Россия
- Контактная информация:
Re: Прохождение по массиву
mzu2006, "-1" могут быть расставлены как угодно (изначально массив генерируеться рандомом и если число в поле массива меньше 0,4 то его меняем на "-1", если нет то на 0 это я проделал) . сейчас попробую решить так как показал eg, если не получиться буду изучать Flood Fill
-
mzu2006
- doctor
- Сообщения: 2456
- Зарегистрирован: 16 авг 2008, 02:12
- Награды: 3
- Версия LabVIEW: 7.1 10 11 12
- Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
- Контактная информация:
Re: Прохождение по массиву
Тот алгоритм не сработает на примере, который я привёл. Если алгоритм дорабатывать, то получится FastFill:
http://www.codeproject.com/KB/GDI-plus/ ... dfill.aspx
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение 2)
http://www.codeproject.com/KB/GDI-plus/ ... dfill.aspx
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение 2)
Правила форума (Forum rules in Russian)
rm -rf /mnt/windows
rm -rf /mnt/windows
-
- beginner
- Сообщения: 49
- Зарегистрирован: 28 июн 2010, 16:46
- Версия LabVIEW: 7.1
- Откуда: Россия
- Контактная информация:
Re: Прохождение по массиву
mzu2006, и eg, большое спасибо! я почти до делал! алгоритм использовал на основе того что подсказал eg,
-
- Похожие темы
- Ответы
- Просмотры
- Последнее сообщение
-
- 2 Ответы
- 310 Просмотры
-
Последнее сообщение BAS