В то время как мы находимся на треугольной сетки пинать , я хотел бы отметить, что есть эквивалент полимино на треугольной сетке. Их называют полиалмазами , и они представляют собой формы, образованные склеиванием равносторонних треугольников вдоль их краев. В этом задании вы будете решать, какие подмножества треугольной сетки являются полиалмазами, и есть ли в них отверстия. Поскольку для создания полиамонда с дырой требуется всего 9 треугольников, ваш код должен быть как можно короче.
Сетки
Мы будем использовать раскладку треугольной сетки Мартина для ввода:
Обратите внимание на тот факт, что центры треугольников образуют примерно прямоугольную сетку и что верхний левый треугольник "указывает" вверх. Затем мы можем описать подмножество этой сетки, дав прямоугольную «звездную карту», указывающую, какие треугольники включены, а какие нет. Например, эта карта:
** **
*****
соответствует наименьшему polyiamond, который содержит отверстие:
Отверстия
Полиалмаз, который содержит отверстие, как в примере выше (область, не являющаяся частью полиамонта, которая со всех сторон окружена областями, которые являются ), топологически говоря, не просто соединена .
Соревнование
Напишите функцию или программу, которые принимают в качестве входных данных «звездную карту», как описано выше, и выводят истинные значения в том и только в том случае, если указанное подмножество треугольной сетки является односвязным многоугольником .
Больше примеров
*** ***
*******
соответствует polyiamond
который просто связан.
* *
** **
***
соответствует polyiamond
который просто связан.
** **
*** **
****
соответствует non- polyiamond
который не был бы просто связан, даже если бы это был polyiamond.
Входные характеристики
- Ввод будет состоять только из звездочек, пробелов и перевода строки.
- Первым символом ввода всегда будет пробел или звездочка (соответствует направленному вверх треугольнику в левом верхнем углу сетки).
- В первой и последней строках всегда будет хотя бы одна звездочка.
- НЕТ гарантии, что строки после первой строки не будут пустыми. Два перевода строки в строке могут появиться в допустимом вводе.
- Длина линий не обязательно должна быть одинаковой.
Условие победы
Это Код-гольф, так что кратчайший ответ в байтах выигрывает.
Тестовые случаи
Правдивые карты:
1) *
2) *
*
3) **
4) *** ***
*******
5) * *
** **
***
6) *
**
*
7) **
***
****
8) ****
** *
*****
9) ***********
** ** **
**** ** **
**
************
Ложные карты:
1) *
*
*
2) * *
3) *
*
4) **
**
5) ***
***
6) ** **
*****
7) ** **
*** **
****
8) *
*
9) *****
** *
*****
источник
AV VA\nVAVAV
вместо того,** **\n*****
чтобы облегчить визуализацию для человека. Я уже внес изменение в одну из диаграмм Мартина ASCII.Ответы:
Улитки , 95 байт
Это действительно страдало от дублирования, так как я не реализовывал макросы или какие-либо обратные ссылки. Он проверяет, что для каждой звезды существует путь к самой левой звезде в верхней строке; и для каждого пространства есть путь к краю сетки.
источник
CJam,
10198 байтПопробуйте онлайн.
Я наконец преодолел свой страх перед выполнением заливки в CJam. Это примерно так же безобразно, как я ожидал, и вполне определенно можно играть в гольф.
Общая идея состоит в том, чтобы выполнить две заливки (которые фактически выполняются как удаления из списка не посещенных ячеек). Первый проход удалит все пробелы, которые достижимы от края. Затем второй проход выберет первый
*
в порядке чтения и удалит все треугольники, доступные для этого. Если и только если результирующий список пуст, полиамонт был просто связан:источник