Arborally удовлетворены заданное значение является 2D множества точек, что для любой оси выровнено прямоугольника , который может быть образован с использованием двух точек в наборе как противоположные углы, что прямоугольник содержит или штрихи , по меньшей мере , один другую точку. Вот эквивалентное определение из Википедии:

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

На следующем рисунке показано, как формируются прямоугольники. Этот набор точек НЕ выполняется произвольно, потому что этот прямоугольник должен содержать хотя бы еще одну точку.

В искусстве ASCII этот набор точек может быть представлен как:

......
....O.
......
.O....
......

Небольшая модификация может сделать это в целом удовлетворительным:

......
....O.
......
.O..O.
......

Выше вы можете видеть, что все прямоугольники (из которых только один) содержат как минимум три точки.

Вот еще один пример более сложного набора точек, который в целом выполняется:

Для любого прямоугольника, который можно нарисовать, охватывающий две точки, этот прямоугольник содержит хотя бы одну другую точку.

Соревнование

Учитывая прямоугольную сетку точек (которую я представляю O) и пустое пространство (которое я представляю .), выведите истинное значение, если оно выполнено произвольно, или значение false, если это не так. Это код-гольф.

Дополнительные правила:

• Вы можете выбрать символы Oи .заменить их любой другой парой печатных символов ASCII. Просто укажите, какое отображение символов использует ваша программа.
• Сетка всегда будет прямоугольной. Завершающий перевод строки разрешен.

Больше примеров

Дословно доволен:

.OOO.
OO...
.O.OO
.O..O
....O

..O..
OOOO.
...O.
.O.O.
...OO

O.O.
..O.
OOOO
.O.O
OO..

...
...
...

...
..O
...

O.....
O.O..O
.....O

OOO.OO

Не полностью удовлетворены

..O..
O....
...O.
.O...
....O

..O..
O.OO.
...O.
.O.O.
...OO

O.....
..O...
.....O

Улитки , 29 30 39 байт

!{t\Oo\.+c\.,\O!{t\O{w!(.,~}2

Он работает, отрисовывая 2 стороны прямоугольника, а затем проверяя, есть ли какой-нибудь квадрат, содержащий O, такой, что перемещение по прямой линии от квадрата в 2 из кардинальных направлений приведет к попаданию на сторону прямоугольника.

Печатает максимум 1 и площадь сетки, если вход «арборально удовлетворен»; в противном случае 0.

Oracle SQL 11.2, 364 344 байта

WITH v AS(SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y FROM DUAL WHERE'O'=SUBSTR(:g,LEVEL,1)CONNECT BY LEVEL<=LENGTH(:g))SELECT a.*,b.*FROM v a,v b WHERE b.x>a.x AND b.y>a.y MINUS SELECT a.*,b.*FROM v a,v b,v c WHERE((c.x IN(a.x,b.x)AND c.y>=a.y AND c.y<=b.y)OR(c.y IN(a.y,b.y)AND c.x>=a.x AND c.x<=b.x))AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

: g - сетка в виде строки
: w - ширина сетки

Не возвращает ни одной строки как верной, возвращает прямоугольники, которые не соответствуют критериям, как ложные

Un-golfed

WITH v AS
(
  SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y,SUBSTR(:g,LEVEL,1)p 
  FROM   DUAL 
  WHERE  'O'=SUBSTR(:g,LEVEL,1)
  CONNECT BY LEVEL<=LENGTH(:g)
)
SELECT a.*,b.*FROM v a,v b
WHERE b.x>a.x AND b.y>a.y
MINUS
SELECT a.*,b.*FROM v a,v b,v c
WHERE((c.x IN(a.x,b.x) AND c.y>=a.y AND c.y<=b.y) OR (c.y IN(a.y,b.y) AND c.x>=a.x AND c.x<=b.x))
  AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

Представление v вычисляет координаты каждой точки O.
Первая часть минуса возвращает все прямоугольники, предложение where гарантирует, что точка не может быть соединена с самой собой.
Вторая часть ищет третью точку в каждом прямоугольнике. Эта точка должна иметь одну координату, x или y, равную этой координате для одной из двух точек, определяющих прямоугольник. Другая координата этой третьей точки должна находиться в диапазоне, ограниченном этой координатой для каждой из точек, определяющих прямоугольник.
Последняя часть предложения where гарантирует, что третья точка не является одной из двух точек, определяющих прямоугольник.
Если все прямоугольники имеют хотя бы третью точку, то первая часть минуса равна второй части, и запрос ничего не возвращает.

MATL , 38 байт

Ti2\2#fh!XJ"J@-XKtAZ)"@K-@/Eq|1>~As2>*

В качестве входных данных используется двумерный массив символов, разделенные строками ;. Итак, первый пример

['......';'....O.';'......';'.O..O.';'......']

Остальные тестовые случаи в этом формате выглядят следующим образом.

• Дословно доволен:

  ['.OOO.';'OO...';'.O.OO';'.O..O';'....O']
  ['..O..';'OOOO.';'...O.';'.O.O.';'...OO']
  ['O.O.';'..O.';'OOOO';'.O.O';'OO..']
  ['...';'...';'...']
  ['...';'..O';'...']
  ['O.....';'O.O..O';'.....O']
  ['OOO.OO']
  

• Не полностью удовлетворен

  ['..O..';'O....','...O.';'.O...';'....O']
  ['..O..';'O.OO.';'...O.';'.O.O.';'...OO']
  ['O.....';'..O...';'.....O']
  

Попробуйте онлайн! Вы также можете проверить все тестовые случаи одновременно .

объяснение

Код сначала получает координаты символов Oна входе. Затем он использует два вложенных цикла. Внешний цикл выбирает каждую точку P (два набора ее координат), сравнивает со всеми точками и сохраняет точки, которые отличаются от P в двух координатах. Это те точки, которые могут образовывать прямоугольник с помощью P. Назовите их набором R.

Внутренний цикл выбирает каждую точку T из R и проверяет, содержит ли прямоугольник, определенный P и T, хотя бы 3 точки. Для этого он вычитает P из всех точек; то есть перемещает начало координат в P. Точка находится в прямоугольнике, если каждая из ее координат, разделенная на соответствующую координату T, находится в замкнутом интервале [0, 1].

T          % push "true"
i          % take input 2D array
2\         % modulo 2: gives 1 for 'O', 0 for '.'
2#f        % row and column coordinates of ones. Gives two column arrays
h!         % concatenate horizontally. Transpose. Each point is a column
XJ         % copy to clipboard J
"          % for each column
  J        %   push all points
  @-       %   subtract current point (move to origin)
  XK       %   copy to clipboard K
  tA       %   logical index of points whose two coordinates are non-zero
  Z)       %   keep only those points. Each is a column
  "        %   for each column (point)
    @K-    %     push that point. Subtract all others
    @/     %     divide by current point
    Eq|1>~ %     true if in the interval [0,1]
    A      %     true if that happens for the two coordinates
    s      %     sum: find out how many points fulfill that
    2>     %     true if that number is at least 3
    *      %     multiply (logical and). (There's an initial true value at the bottom)
           %   end
           % end
           % implicit display

PHP, 1123 байта , 851 байт , 657 байт

(новичок php)

<?php
$B=array_map("str_split",array_map("trim",file('F')));$a=[];$b=-1;foreach($B as $c=>$C){foreach($C as $d=>$Z){if($Z=='O'){$a[++$b][]=$c;$a[$b][]=$d;}}}$e=array();foreach($a as $f=>$l){foreach($a as $g=>$m){$h=$l[0];$i=$l[1];$j=$m[0];$k=$m[1];if($h!=$j&&$i!=$k&&!(in_array([$g,$f],$e,1)))$e[]=[$f,$g];}}$A=array();foreach($e as $E){$n=$E[0];$o=$E[1];$q=$a[$n][0];$s=$a[$n][1];$r=$a[$o][0];$t=$a[$o][1];$u=($q<$r)?$q:$r;$v=($s<$t)?$s:$t;$w=($q>$r)?$q:$r;$X=($s>$t)?$s:$t;$Y=0;foreach($a as $p){$x=$p[0];$y=$p[1];if($x>=$u&&$x<=$w&&$y>=$v&&$y<=$X){$Y=($x==$q&&$y==$s)||($x==$r&&$y==$t)?0:1;}if($Y==1)break;}if($Y==1)$A[]=1;}echo count($A)==count($e)?1:0;

объяснение (закомментированный код):

<?php
//read the file
$lines=array_map("str_split",array_map("trim",file('F'))); // grid in file 'F'

//saving coords
$coords=[]; // new array
$iCoord=-1;
foreach($lines as $rowIndex=>$line) {
    foreach($line as $colIndex=>$value) {
        if ($value=='O'){
            $coords[++$iCoord][]=$rowIndex;//0 is x
            $coords[$iCoord][]=$colIndex;  //1 is y
        }
    }
}

/* for each point, draw as many rectangles as other points
 * without creating 'mirror' rectangles
 */ 
$rectangles=array();

foreach ($coords as $point1Index=>$point1) {
     //draw
     foreach ($coords as $point2Index=>$point2) {
            $point1X=$point1[0];
            $point1Y=$point1[1];
            $point2X=$point2[0];
            $point2Y=$point2[1];
            //if not on the same line or on the same column, ...
            if ($point1X!=$point2X &&   // same line
                $point1Y!=$point2Y &&   // same column
                !(in_array([$point2Index,$point1Index],$rectangles,true)) //... and if no 'mirror one' already
             ) $rectangles[]=[$point1Index,$point2Index]; //create a new rectangle
     }
 }

//now that we have rectangles and coords
//try and put a third point into each
$tests=array();
foreach ($rectangles as $rectangle) {
    $pointA=$rectangle[0];    // points of the rectangle
    $pointB=$rectangle[1];    // __________"____________
    $xA=$coords[$pointA][0];
    $yA=$coords[$pointA][1];
    $xB=$coords[$pointB][0];
    $yB=$coords[$pointB][1];
    $minX=($xA<$xB)?$xA:$xB;
    $minY=($yA<$yB)?$yA:$yB;
    $maxX=($xA>$xB)?$xA:$xB;
    $maxY=($yA>$yB)?$yA:$yB;

    $arborally=false;
    foreach ($coords as $point) {
        $x=$point[0];
        $y=$point[1];
        if ($x>=$minX &&
            $x<=$maxX &&
            $y>=$minY &&
            $y<=$maxY) {
                $arborally=($x==$xA&&$y==$yA) || ($x==$xB&&$y==$yB)?0:1; //same point (pointA or pointB)
        }     
        if ($arborally==true) break;//1 found, check next rectangle
    }
    if ($arborally==true) $tests[]=1;//array of successes

}

echo count($tests)==count($rectangles)?1:0; //if as many successes than rectangles...

?>

C, 289 байтов

a[99][99],x,X,y,Y,z,Z,i,c;main(k){for(;x=getchar(),x+1;x-10||(y=0,i++))a[y++][i]=x;for(;X<i;X++)for(x=0;a[x][X]-10;x++)for(Y=X+1;Y<i;Y++)for(y=0;a[y][Y]-10;y++)if(x-y&&!(a[x][X]-79||a[y][Y]-79)){c=0;for(Z=X;Z<=Y;Z++)for(z=x<y?x:y;z<=(x>y?x:y);)a[z++][Z]-79||c++;c-2||(k=0);}putchar(k+48);}

Требуется завершающий перевод строки, что разрешено (без перевода строки код был бы на два байта больше). Выходы 0 (не удовлетворены в целом) или 1 (выполнены в целом).