Прохождение по массиву

Простейшие вопросы в области инженерной разработки
Ответить
V1taliy2009
beginner
beginner
Сообщения: 49
Зарегистрирован: 28 июн 2010, 16:46
Версия LabVIEW: 7.1
Откуда: Россия
Контактная информация:

Прохождение по массиву

Сообщение V1taliy2009 »

Доброго времени суток.

Есть массив размерностью X на X (в данном случае 4 на 4) в котором некоторые ячейки заняты "-1"
lab2.png
lab2.png (2.76 КБ) 2910 просмотров
Подскажите пожалуйста как выполнить проверку на то можно ли пройти от одной стороны массива до другой (с право на лево или снизу вверх) по пути из "-1" как показано на рисунке:
lab1.png
lab1.png (5.38 КБ) 2910 просмотров
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: прохождение по массиву

Сообщение mzu2006 »

Из простого напрашивается реализация c перебором типа flood fill, используя поочерёдно все значения =-1 на начальной границе массива как затравки (seed).
Отличие от flood fill в том, что остановку рекурсии делать по достижении границы. Из рекуррентной функции возвращать true/false флаг: достигли или не достигли границы.
Если версия :labview: позволяет сделать рекурсию, то простая реализация совсем проста: http://en.wikipedia.org/wiki/Flood_fill

Если нет, то нужно использовать очереди, или альтернативные реализации (fast fill, например).

Если есть желание распараллелить процесс, то элегантную ООП идею для реализации рекурсии-распараллеливания можно позаимствовать отсюда: http://expressionflow.com/2009/11/10/un ... -dataflow/ Там, правда надо будет немного доработать.
V1taliy2009
beginner
beginner
Сообщения: 49
Зарегистрирован: 28 июн 2010, 16:46
Версия LabVIEW: 7.1
Откуда: Россия
Контактная информация:

Re: Прохождение по массиву

Сообщение V1taliy2009 »

mzu2006, спасибо конечно за статьи но честно говоря ничего н епонятно....
Аватара пользователя
Eugen Graf

Activity Professionalism Silver Black
guru
guru
Сообщения: 6502
Зарегистрирован: 13 ноя 2007, 02:20
Награды: 4
Версия LabVIEW: 2009
Откуда: Saarbrücken
Контактная информация:

Re: Прохождение по массиву

Сообщение Eugen Graf »

Моя идея:

Если взять For Loop с автоиндексацией.
В первой итерации у нас имеется первая строка.
Берём Search 1D Array и находим индекс элемента -1 и запоминаем в сдвиговом регистре.
Во второй итерации у нас вторая строка.
Берём Search 1D Array и находим индекс элемента -1, сравниваем с тем что запомнили в сдвиг. регистре при прошлой итерации, запоминаем в сдвиговом регистре, если >=.
И так далее пока не закончатся строки или Search 1D Array не выдаст -1 или индексы не будут >= (For Loop тоже можно заранее прекратить).
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: Прохождение по массиву

Сообщение mzu2006 »

eg, в той форме в которой задача поставлена, в каждой строке может быть больше одного элемента, содержащего "-1". Кроме того, множество всех элементов, содержащих -1 может быть овсем не простое. Например, такое:

Код: Выделить всё

XXXX0X
000X0X
0X000X
0XXXXX
0 - это "-1", X - всё, что угодно другое

Если расширять твой алгоритм на такие случаи, то он приведёт к одному из вариантов Fast Fill, реализованному, например, в моём решении на конкурс с пятном:
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение номер 2)
Последний раз редактировалось mzu2006 04 ноя 2010, 01:19, всего редактировалось 1 раз.
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: Прохождение по массиву

Сообщение mzu2006 »

V1taliy2009, так а что непонятно, спрашивай.

Для того, чтобы написать программу, ищущую путь через массив надо:
1. Разобраться с тем как работает Flood Fill.
2. Реализовать это на :labview:
3. Поменять условие окончания работы на "достижение границы"

Начни делать, и мы тебе поможем

V1taliy2009, условие задачи надо уточнить. Например, могут ли быть такие "пути из -1" как я показал в предыдущем посте?
V1taliy2009
beginner
beginner
Сообщения: 49
Зарегистрирован: 28 июн 2010, 16:46
Версия LabVIEW: 7.1
Откуда: Россия
Контактная информация:

Re: Прохождение по массиву

Сообщение V1taliy2009 »

mzu2006, "-1" могут быть расставлены как угодно (изначально массив генерируеться рандомом и если число в поле массива меньше 0,4 то его меняем на "-1", если нет то на 0 это я проделал) . сейчас попробую решить так как показал eg, если не получиться буду изучать Flood Fill
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: Прохождение по массиву

Сообщение mzu2006 »

Тот алгоритм не сработает на примере, который я привёл. Если алгоритм дорабатывать, то получится FastFill:
http://www.codeproject.com/KB/GDI-plus/ ... dfill.aspx
http://www.labviewportal.org/viewtopic. ... 385#p17385 (решение 2)
V1taliy2009
beginner
beginner
Сообщения: 49
Зарегистрирован: 28 июн 2010, 16:46
Версия LabVIEW: 7.1
Откуда: Россия
Контактная информация:

Re: Прохождение по массиву

Сообщение V1taliy2009 »

mzu2006, и eg, большое спасибо! я почти до делал! алгоритм использовал на основе того что подсказал eg,
Ответить
  • Похожие темы
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в «Для чайников»