Вход | Регистрация


1С:Предприятие :: 1С:Предприятие 8 общая

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

Алгоритм вычисления смежных ячеек
Я
   NeoGelios
 
07.10.17 - 15:59
Внешняя обработка (Платформа 8.3.5, конфигурация 10.3.35.1).

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

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

Есть задача, полагаю связанная с циклами и условиями, и чем-то ещё.

Размер поля не больше 200*200 (строк*столбцов). Из текстового файла загружается массив из произвольного количества строк, содержащий символы "_" и "#".  "_"(нижний пробел) - это пустота, "#"(решётка) - это стена.

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

Чтение из текстового файла сделал. Каким образом можно найти изолированные со всех сторон дыры(пустоты)? Даже в голову почти ничего не приходит.. Полагаю нужно разложить строки на символы (как?). Затем либо заполнить значениями таблицу, либо вычислять уже в процессе.

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

Вот примеры таких полей:

###___###_##     ###___###_##
#_##_###__##     #1##_###__##

####______##     ####______##

______###### >   ______######

_###_#___###     _###_#222###

_____#######     _____#######
В этом примере две дыры, помеченные цифрами 1 и 2.

##########     ##########

#__##__###     #11##22###

###_###__# >   ###3###44#

#__##_#__#     #55##6#44#

##########     ##########

В этом примере у нас шесть дырок.

#####_____     #####_____

____#_____     ____#_____

#####_###_ >   #####_###_

_____#___#     _____#111#

______###_     ______###_
В этом примере у нас одна дырка.
 
 
   Филиал-msk
 
1 - 07.10.17 - 16:08
По одной методичке учитесь?

Задача про лабиринт
   NeoGelios
 
2 - 07.10.17 - 16:09
Картинка двух последних примеров:
http://prntscr.com/guei5l
   Филиал-msk
 
3 - 07.10.17 - 16:09
Дадада, "весь интернет облазил, решения не нашел, поэтому..."
   NeoGelios
 
4 - 07.10.17 - 16:12
Посмотрел ту тему, да, возможно та же история, но решения там нет. По крайней мере кусок тот мне не понятен.
Хотелось бы подробнее, ведь я только учусь =_=
   breezee
 
5 - 07.10.17 - 16:39
Выгружаешь данные в таблицу значений
2 цикла, один вложенный, во время каждого прохода сравниваешь ячейку -1 по по x и по y, смотришь значения, есть ли пересчения, и т.д.
   Филиал-msk
 
6 - 07.10.17 - 16:41
(5) Ты должен написать нашему новичку готовое решение, иначе он не поймет
=_=
   NeoGelios
 
7 - 07.10.17 - 16:46
(5) как разложить строки на ячейки?
   NeoGelios
 
8 - 07.10.17 - 16:48
(6) Я хочу научиться, а не просто получить решение..
   Филиал-msk
 
9 - 07.10.17 - 16:50
(7) Выбрать платформенную структуру данных 1С для хранения. Получить каждую строку файла, получить каждый символ строки. По анализу символа понять что там находится и установить данные в выбранной структуре.
   h-sp
 
10 - 07.10.17 - 16:52
(7) Символ5 = Сред(ТекСтрока, 5, 1);
 
 Рекламное место пустует
   Михаил Козлов
 
11 - 07.10.17 - 17:02
Совсем  предварительно (может и "неправильно"):
1. Строим матрицу смежности для графа, в котором:
- точки - ячейки входной матрицы, в которых нет "стены"; Таких точек может быть много (200х200)
- из точки X в Y идет дуга, если между X в Y нет стены (смежны по горизонтали или вертикали).
2. По матрице смежности строим транзитивное замыкание: тем самым получаем для каждой точки X ВСЕ точки, куда из нее можно попасть.
3. Выделяем в графе компоненты связности.
   Филиал-msk
 
12 - 07.10.17 - 17:04
(11) > По матрице смежности строим транзитивное замыкание

Взрыв мозга ТС повлек за собой землетрясение в 8 баллов по шкале Рихтера. Аккуратней надо-бы, а?
   Михаил Козлов
 
13 - 07.10.17 - 17:06
(12) Вас слово "транзитивное" рассмешило? Вроде как все понимают транзит из А в Б через М (Москва).
   Михаил Козлов
 
14 - 07.10.17 - 17:20
Наверное так будет "поспортивнее" - сразу строить компоненты связности.
Заводим группу 1: Г1.
Берем любую свободную ячейку Я1 и заносим ее в Г1.
Берем следующую свободную ячейку Яj. Смотрим, можно ли ее отнести в какую-нибудь из уже существующих групп (можно отнести в Гi, если она рядом (не через стену) с какой-нибудь из ячеек из Гi. Если таких групп несколько - объединяем их. Если таких групп нет - заводим новую и относим к ней эту ячейку. По сути это и есть транзитивное замыкание.
Вроде как на выходе должны получиться компоненты связности.
   Злопчинский
 
15 - 07.10.17 - 17:23
а вот какую схему данных выбрать чтоб описать связность ячеек склада, чтобы при размещении товаров, габарит которых больше одной ячейки - было понятно что соседняя ячейка (или даже две ячейки - одна справа и одна слева от ячейки размещения или даже N ячеек - М слева и K справа - окажутся занятыми...?
   breezee
 
16 - 07.10.17 - 17:29
(0) Опиши алгоритм по шагам, 1 Чтение файла, 2 Запись в ТЗ, 3...
с нужным тебе уровнем декомпозиции. Дальше прикинь по объектам 1С, которые уже знаешь что тебе поможет решить задачу на каждом шаге. Если не получиться - спрашивай по конкретному вопросу. А так тут довольно простой алгоритм, я начал расписывать уже, но понял, что сделаю медвежью услугу.
   Михаил Козлов
 
17 - 07.10.17 - 17:31
(15) Плоская или объемная?
Для плоской, вроде как, просто: матрица, в которой пометка, что ячейка занята. Для определения соседей смотрим вправо, влево, вверх, вниз на нужную глубину.
Для и для объемной - аналогично, только матрица 3-х мерная.
Или я чего-то не понял?
(14) Похоже, это повторение (5): "Чукча не читатель, чукча писатель".
   Филиал-msk
 
18 - 07.10.17 - 17:33
(13) Нет. Скорей твои потуги попадания в ЦА
   Филиал-msk
 
19 - 07.10.17 - 17:40
(15) Точно такую же, как и для обычной схемы (:

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

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

Ну и при отсутствии соседних получаешь гарантию, что у тебя в проход ничего не торчит.
   NeoGelios
 
20 - 07.10.17 - 17:41
(16) "Медвежьей услугой" это не будет, я из каждого урока извлекаю пользу, и потом применяю это. Я для своей компании  уже много не сложного и полезного напрограммировал, даже не зная ни кода, ни структуры, лишь читая фрагменты и применяя полученный опыт для своих целей.
Язык 1С изучаю по учебнику всего 10 дней, пошагово, поэтому всех компонентов и возможностей пока не знаю.
Пока пишу разложение строк на ячейки))
   h-sp
 
21 - 07.10.17 - 18:39
на самом деле тут не нужно таких сложностей, в этом частном случае. Никаких графов и таблиц значений. Тупо, за один проход всё делается. Читаем строку, определяем список незакрытых снизу областей и общее количество областей. Потом читаем следующую строку, определяем, в какой позиции область открывается, в какой закрывается, в остальных ничего не происходит.

Области слева и справа - вообще ничего не делать, просто если новая область рядом, просто ее не добавляем в общий итог.
   Злопчинский
 
22 - 07.10.17 - 18:53
(17) плоская.
Вопрос в том как описать соседей и чтобы быстро получать этих соседей и соседей соседей
   Злопчинский
 
23 - 07.10.17 - 18:54
Вдобавок ячейки-соседи могут быть несвязными, ибо физически могут быть разграничены
   Злопчинский
 
24 - 07.10.17 - 18:55
Соответственно вопрос для выбора правильной архитектуры описания с прицелом на быстрое получение данных...
   Злопчинский
 
25 - 07.10.17 - 18:56
Ну как быстрое... Наверное этот критерий несущественен
   Филиал-msk
 
26 - 07.10.17 - 19:05
(25) Навскидку.
В памяти - массив. Индекс - идентификатор ячейки. Содержимое - структура описания ячейки:
* Тип (что вообще влезает)
* Состояние (насколько заполнена) 
* Индекс соседа сверху, неопределено если нет
* Индекс соседа справа, неопределено если нет
* Индекс соседа снизу, неопределено если нет
* Индекс соседа слева, неопределено если нет
* Индекс соседа выше, неопределено если нет
* Индекс соседа ниже, неопределено если нет

В базе - справочник топологии ячеек, индекс - ссылка. Состояние - регистр сведений, измерение - ячейка, ресурс - состояние.
   Филиал-msk
 
27 - 07.10.17 - 19:07
Про содержимое надо думать, там может быть одна палетта или 10 товаров... ща лень (:
   Сияющий в темноте
 
28 - 07.10.17 - 19:20
для каждой ячейки определить,куда модно из неё попасть
потом выьираем ячейку и добавляем к ней все смежные,в которые можно попасть,двигаясь в разные стороны,пока область не кончится,дален,переходим в следующуб область
   Сияющий в темноте
 
29 - 07.10.17 - 19:23
ещё,когда мы рассматриваем область,можно найти граничные точки-это те,из которых можно шагнуть вне известной области,соответственно,перебирая их,мы можем увеличивать область,а когда из какой-то точки больше шагнуть некуда,она становится внутренней и исключается из рассмотрения
   Йохохо
 
30 - 07.10.17 - 19:28
проходим первую строку и "красим" цветами 1, 2.. не смежные, кидаем первую в переменную
берем вторую и начинаем красить. 1 проверяем что это диапазон по горизонтали 2 пытаемся получить цвет сверху 3 если цвет сверху присваивается уже покрашенной кидаем его в соответствие(лишний)=правильный
в конце количество различных правильных будет ответ
   Злопчинский
 
31 - 07.10.17 - 19:35
(29) да,как то так и мне представляется.. Но из смежной ячейки доступна следующая смежная для смежной может быть...
В итоге например обращаемся (запросом?) к данным и получаем перечень цеочек, состоящих из смежных ячеек... При 5-10 тысячах ячеек не сильно долго будет получение перечня цепочек свободных смежных ячеек?
   Tatitutu
 
32 - 07.10.17 - 19:38
   Сияющий в темноте
 
33 - 07.10.17 - 19:39
второй вариант,выбрать все пустые точки в массив,присвоив каждой свой номер,далее когда из одной ячейки можно шагнуть в другую,мы выбираем из них старший номер и во всех ячейках старший номер заменяем на младший
 
 
   Филиал-msk
 
34 - 07.10.17 - 19:44
(31) Храни все предрассчитанные цепочки как отдельную сущность, делов-то. Выдашь цепочке идентификатор, одна ячейка - тоже цепочка (м
   Злопчинский
 
35 - 07.10.17 - 22:42
(33) мозг мой закостенед.. не понявши я
   Злопчинский
 
36 - 07.10.17 - 22:52
(34) и искать подходящие цепочки как? тупо их выбирая из большой таблицы? допустимм.. выбрал все цепочки "размером" в 3 ячейки... из этих цепочек выбрал "подходящую"... допустим... в подходящей ячейке теперь надо определить "среднюю" ячейку, чтобы к ней отправить погрузчик с крупногабаритным товаром.. как определить эту среднюю ячейку...? это уже проще...
.
другой вопрос, что при изменении топологии - придется пересчитывать как-то и автоматом модифицировать все существующие цепочки... которые могут распадаться на более мелкие цепочки и соединяться в более крупные.. и это в том числе и при размещении обычных товаров (размером с 1 ячейку) в одну ячейку и при освобождении таких ячеек... - и как-то тут навскидку наличие предрасчитанных цепочек не поможет? при превращении цепочки из 5 ячеек в две цепочки по две ячейки (при размещении товара в ячейку середины цепочки) -  надо знать какая ячейка с какой связана..то есть просто цепочки как перечень ячеек - не потянет.. обязательно тем или иным способом надо "знать" какая чейка с какой связана... опять же если три ячейки свободные 1-2-3 - то будет как миниум три цепочки если задавать впрямую:
1-2-3
1-2
2-3
   NeoGelios
 
37 - 08.10.17 - 08:50
Спасибо всем, кто пытался помочь:
breezee, h-sp, Сияющий в темноте
___
Остальным флудерам интеллекта хватило лишь на стёб...
Вы ещё через интеграл транзитивное квантование ячейки проведите, и через вариативный вакуум выделите дырки антиматериальной структуры, через цикл многомерных стенок...
   Филиал-msk
 
38 - 08.10.17 - 10:38
(37) Да мы такие заходи ещё.
А, да, и ещё смайлик нужен, как ты там делал...
=_=
   Филиал-msk
 
39 - 08.10.17 - 10:46
(36) Ну да, смысл в том чтобы свести задачу к выборкам, которые легко на sql ложатся. Можно попробовать строить цепочки тем же sql каждый раз заново про запросе. Или размножать строки или даже, если длина цепочек ограничена сверху - разворачивать в колонки левым соединением и искать длину по первому null в столбце...

Реструктуризация при изменении топологии склада опасна ещё тем, что может изменить существующие идентификаторы ячеек, цепочек и т.п., кроме топологии возможно придётся перетряхивать ещё и данные о текущем размещении.
Про то, что топология и фактическая занятость ячеек хранятся отдельно возражений нет?
   Злопчинский
 
40 - 08.10.17 - 18:56
(39) > Про то, что топология и фактическая занятость ячеек хранятся отдельно возражений нет?
- нет.
топология отдельно. фактическая занятость ячеек отдельными сведениями не заполняется, если в ячейке есть остаток (например, РН) - значит занята...
   VS-1976
 
41 - 08.10.17 - 19:00
Делается рекурсией. Находишь пустоту далее алгоритм заливки области к примеру тем же #. Далее ищешь другую пустоту и заливаешь и так пока до конца все не зальешь. Количество посчитаешь и все.
   Сияющий в темноте
 
42 - 08.10.17 - 19:52
стандартный алгоритм заливки ходит по диагонали,а здесь этого нет
   Филиал-msk
 
43 - 08.10.17 - 20:00
(42) "Стадартный" это какой? По реберным точкам? Горизонтальный XOR? Или тот единственный, который ты знаешь? (:


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует