Алгоритм вычисления смежных ячеек #806204

Внешняя обработка (Платформа 8.3.5, конфигурация 10.3.35.1). Доброго времени суток. 1С изучаю недавно, но знаком с ней дольше. Программирую несложные задачи, но на что-то сложное пока не хватает опыта. Есть задача, полагаю связанная с циклами и условиями, и чем-то ещё. Размер поля не больше 200*200 (строк*столбцов). Из текстового файла загружается массив из произвольного количества строк, содержащий символы "_" и "#".  "_"(нижний пробел) - это пустота, "#"(решётка) - это стена. Нужно программно определить количество замкнутых несвязанных между собою пустот. Пустота считается несвязанной с другими, если у неё нет смежных с другой пустотой клеток по горизонтали или вертикали. Т.е. из одной пустоты нельзя перейти в другую пустоту двигаясь по любой траектории и делая шаги по горизонтали и/или вертикали. Чтение из текстового файла сделал. Каким образом можно найти изолированные со всех сторон дыры(пустоты)? Даже в голову почти ничего не приходит.. Полагаю нужно разложить строки на символы (как?). Затем либо заполнить значениями таблицу, либо вычислять уже в процессе. Может быть индексация найденных пустот, а на следующей строке проверять по индексу, есть ли в предыдущей строке по вертикали дыра и записывать как-то в переменную найденную дыру, а если условие нарушается (к примеру вверху стена через пустоту), то удалить значение переменной. По количеству таких переменных определить, сколько дыр на поле. Вот примеры таких полей: _____#######     _____####### В этом примере две дыры, помеченные цифрами 1 и 2. ##########     ########## #__##__###     #11##22### ##########     ########## В этом примере у нас шесть дырок. #####_____     #####_____ ____#_____     ____#_____ ______###_     ______###_ В этом примере у нас одна дырка.

По одной методичке учитесь?

Картинка двух последних примеров:

Дадада, "весь интернет облазил, решения не нашел, поэтому..."

Посмотрел ту тему, да, возможно та же история, но решения там нет. По крайней мере кусок тот мне не понятен. Хотелось бы подробнее, ведь я только учусь =_=

Выгружаешь данные в таблицу значений 2 цикла, один вложенный, во время каждого прохода сравниваешь ячейку -1 по по x и по y, смотришь значения, есть ли пересчения, и т.д.

Ты должен написать нашему новичку готовое решение, иначе он не поймет =_=

как разложить строки на ячейки?

Я хочу научиться, а не просто получить решение..

Выбрать платформенную структуру данных 1С для хранения. Получить каждую строку файла, получить каждый символ строки. По анализу символа понять что там находится и установить данные в выбранной структуре.

Символ5 = Сред(ТекСтрока, 5, 1);

Совсем  предварительно (может и "неправильно"): 1. Строим матрицу смежности для графа, в котором: - точки - ячейки входной матрицы, в которых нет "стены"; Таких точек может быть много (200х200) - из точки X в Y идет дуга, если между X в Y нет стены (смежны по горизонтали или вертикали). 2. По матрице смежности строим транзитивное замыкание: тем самым получаем для каждой точки X ВСЕ точки, куда из нее можно попасть. 3. Выделяем в графе компоненты связности.

> По матрице смежности строим транзитивное замыкание Взрыв мозга ТС повлек за собой землетрясение в 8 баллов по шкале Рихтера. Аккуратней надо-бы, а?

Вас слово "транзитивное" рассмешило? Вроде как все понимают транзит из А в Б через М (Москва).

Наверное так будет "поспортивнее" - сразу строить компоненты связности. Заводим группу 1: Г1. Берем любую свободную ячейку Я1 и заносим ее в Г1. Берем следующую свободную ячейку Яj. Смотрим, можно ли ее отнести в какую-нибудь из уже существующих групп (можно отнести в Гi, если она рядом (не через стену) с какой-нибудь из ячеек из Гi. Если таких групп несколько - объединяем их. Если таких групп нет - заводим новую и относим к ней эту ячейку. По сути это и есть транзитивное замыкание. Вроде как на выходе должны получиться компоненты связности.

а вот какую схему данных выбрать чтоб описать связность ячеек склада, чтобы при размещении товаров, габарит которых больше одной ячейки - было понятно что соседняя ячейка (или даже две ячейки - одна справа и одна слева от ячейки размещения или даже N ячеек - М слева и K справа - окажутся занятыми...?

Опиши алгоритм по шагам, 1 Чтение файла, 2 Запись в ТЗ, 3... с нужным тебе уровнем декомпозиции. Дальше прикинь по объектам 1С, которые уже знаешь что тебе поможет решить задачу на каждом шаге. Если не получиться - спрашивай по конкретному вопросу. А так тут довольно простой алгоритм, я начал расписывать уже, но понял, что сделаю медвежью услугу.

Плоская или объемная? Для плоской, вроде как, просто: матрица, в которой пометка, что ячейка занята. Для определения соседей смотрим вправо, влево, вверх, вниз на нужную глубину. Для и для объемной - аналогично, только матрица 3-х мерная. Или я чего-то не понял? Похоже, это повторение : "Чукча не читатель, чукча писатель".

Нет. Скорей твои потуги попадания в ЦА

Точно такую же, как и для обычной схемы (: Вводишь "частичную занятость" ячейки. Число там, перечисление занятых частей, пофиг. При помещении объекта в ячейку "занимаешь" как целевую, так и соседние. В результате получаешь, например "занятые полностью" и соседние "занятые наполовину", куда можно впихнуть еще полтовара. Какую из соседних ячеек насколько занимать - надо смотреть, это отдельная операция отображающая, как ты физически запихиваешь. Ну и при отсутствии соседних получаешь гарантию, что у тебя в проход ничего не торчит.

"Медвежьей услугой" это не будет, я из каждого урока извлекаю пользу, и потом применяю это. Я для своей компании  уже много не сложного и полезного напрограммировал, даже не зная ни кода, ни структуры, лишь читая фрагменты и применяя полученный опыт для своих целей. Язык 1С изучаю по учебнику всего 10 дней, пошагово, поэтому всех компонентов и возможностей пока не знаю. Пока пишу разложение строк на ячейки))

на самом деле тут не нужно таких сложностей, в этом частном случае. Никаких графов и таблиц значений. Тупо, за один проход всё делается. Читаем строку, определяем список незакрытых снизу областей и общее количество областей. Потом читаем следующую строку, определяем, в какой позиции область открывается, в какой закрывается, в остальных ничего не происходит. Области слева и справа - вообще ничего не делать, просто если новая область рядом, просто ее не добавляем в общий итог.

плоская.Вопрос в том как описать соседей и чтобы быстро получать этих соседей и соседей соседей

Вдобавок ячейки-соседи могут быть несвязными, ибо физически могут быть разграничены

Соответственно вопрос для выбора правильной архитектуры описания с прицелом на быстрое получение данных...

Ну как быстрое... Наверное этот критерий несущественен

Навскидку. В памяти - массив. Индекс - идентификатор ячейки. Содержимое - структура описания ячейки: * Тип (что вообще влезает) * Состояние (насколько заполнена) * Индекс соседа сверху, неопределено если нет * Индекс соседа справа, неопределено если нет * Индекс соседа снизу, неопределено если нет * Индекс соседа слева, неопределено если нет * Индекс соседа выше, неопределено если нет * Индекс соседа ниже, неопределено если нет В базе - справочник топологии ячеек, индекс - ссылка. Состояние - регистр сведений, измерение - ячейка, ресурс - состояние.

Про содержимое надо думать, там может быть одна палетта или 10 товаров... ща лень (:

для каждой ячейки определить,куда модно из неё попасть потом выьираем ячейку и добавляем к ней все смежные,в которые можно попасть,двигаясь в разные стороны,пока область не кончится,дален,переходим в следующуб область

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

проходим первую строку и "красим" цветами 1, 2.. не смежные, кидаем первую в переменную берем вторую и начинаем красить. 1 проверяем что это диапазон по горизонтали 2 пытаемся получить цвет сверху 3 если цвет сверху присваивается уже покрашенной кидаем его в соответствие(лишний)=правильный в конце количество различных правильных будет ответ

да,как то так и мне представляется.. Но из смежной ячейки доступна следующая смежная для смежной может быть... В итоге например обращаемся (запросом?) к данным и получаем перечень цеочек, состоящих из смежных ячеек... При 5-10 тысячах ячеек не сильно долго будет получение перечня цепочек свободных смежных ячеек?

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

Храни все предрассчитанные цепочки как отдельную сущность, делов-то. Выдашь цепочке идентификатор, одна ячейка - тоже цепочка (м

мозг мой закостенед.. не понявши я

и искать подходящие цепочки как? тупо их выбирая из большой таблицы? допустимм.. выбрал все цепочки "размером" в 3 ячейки... из этих цепочек выбрал "подходящую"... допустим... в подходящей ячейке теперь надо определить "среднюю" ячейку, чтобы к ней отправить погрузчик с крупногабаритным товаром.. как определить эту среднюю ячейку...? это уже проще... . другой вопрос, что при изменении топологии - придется пересчитывать как-то и автоматом модифицировать все существующие цепочки... которые могут распадаться на более мелкие цепочки и соединяться в более крупные.. и это в том числе и при размещении обычных товаров (размером с 1 ячейку) в одну ячейку и при освобождении таких ячеек... - и как-то тут навскидку наличие предрасчитанных цепочек не поможет? при превращении цепочки из 5 ячеек в две цепочки по две ячейки (при размещении товара в ячейку середины цепочки) -  надо знать какая ячейка с какой связана..то есть просто цепочки как перечень ячеек - не потянет.. обязательно тем или иным способом надо "знать" какая чейка с какой связана... опять же если три ячейки свободные 1-2-3 - то будет как миниум три цепочки если задавать впрямую: 1-2-3 1-2 2-3

Спасибо всем, кто пытался помочь: ___ Остальным флудерам интеллекта хватило лишь на стёб... Вы ещё через интеграл транзитивное квантование ячейки проведите, и через вариативный вакуум выделите дырки антиматериальной структуры, через цикл многомерных стенок...

Да мы такие заходи ещё. А, да, и ещё смайлик нужен, как ты там делал... =_=

Ну да, смысл в том чтобы свести задачу к выборкам, которые легко на sql ложатся. Можно попробовать строить цепочки тем же sql каждый раз заново про запросе. Или размножать строки или даже, если длина цепочек ограничена сверху - разворачивать в колонки левым соединением и искать длину по первому null в столбце... Реструктуризация при изменении топологии склада опасна ещё тем, что может изменить существующие идентификаторы ячеек, цепочек и т.п., кроме топологии возможно придётся перетряхивать ещё и данные о текущем размещении. Про то, что топология и фактическая занятость ячеек хранятся отдельно возражений нет?

> Про то, что топология и фактическая занятость ячеек хранятся отдельно возражений нет? - нет. топология отдельно. фактическая занятость ячеек отдельными сведениями не заполняется, если в ячейке есть остаток (например, РН) - значит занята...

Делается рекурсией. Находишь пустоту далее алгоритм заливки области к примеру тем же #. Далее ищешь другую пустоту и заливаешь и так пока до конца все не зальешь. Количество посчитаешь и все.

стандартный алгоритм заливки ходит по диагонали,а здесь этого нет

"Стадартный" это какой? По реберным точкам? Горизонтальный XOR? Или тот единственный, который ты знаешь? (: