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


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? Или тот единственный, который ты знаешь? (:


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