Алгоритмы

Опубликовано сб, 07/10/2017 - 15:05 пользователем Исследователь
Версия для печатиPDF-версия

Платформа:

Конфигурация:

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

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

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

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

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

Внешняя обработка (Платформа 8.3.5, конфигурация 10.3.35.1)

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

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

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

###___###_##     ###___###_##
#_##_###__##      #1##_###__##
####______##     ####______##
______###### > ______######
_###_#___###      _###_#222###
_____#######     _____#######
В этом примере две дыры, помеченные цифрами 1 и 2.
 
##########     ##########
#__##__###      #11##22###
###_###__# >  ###3###44#
#__##_#__#      #55##6#44#
##########     ##########
В этом примере у нас шесть дырок.
 
#####_____     #####_____
____#_____     ____#_____
#####_###_ > #####_###_
_____#___#      _____#111#
______###_     ______###_
В этом примере у нас одна дырка.

K1RSAN

пт, 13/10/2017 - 09:27

Ну тут в голову приходит только итерации. То есть я бы создал массив "обработанных" ячеек, идем по циклу ячеек.
Если находим пустоту - запускается итерация, где проверяется наличие стены сверху, потом справа, потом снизу и потом слева. Соответственно, каждая ячейка, которая уже побывала в итерации помечается как посещенная (чтобы не было зацикливания). Таким образом идем по итерации, пока не получим стены. Если доходим до края массива - помечаем, что вся эта пустота не может быть дыркой. Как только получаем все стены - запоминаем, что есть дырка. Так как все посещенные точки помечены, а итерация проверяет все возможные соприкосновения - эта дырка больше не попадет в цикл проверок. Так идем по всему массиву, считаем дырки.

Далее уже идет построение кода по алгоритму.