Алгоритмы
Конфигурация:
Доброго времени суток.
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
Ну тут в голову приходит только итерации. То есть я бы создал массив "обработанных" ячеек, идем по циклу ячеек.
Если находим пустоту - запускается итерация, где проверяется наличие стены сверху, потом справа, потом снизу и потом слева. Соответственно, каждая ячейка, которая уже побывала в итерации помечается как посещенная (чтобы не было зацикливания). Таким образом идем по итерации, пока не получим стены. Если доходим до края массива - помечаем, что вся эта пустота не может быть дыркой. Как только получаем все стены - запоминаем, что есть дырка. Так как все посещенные точки помечены, а итерация проверяет все возможные соприкосновения - эта дырка больше не попадет в цикл проверок. Так идем по всему массиву, считаем дырки.
Далее уже идет построение кода по алгоритму.