Eine arborally erfüllte Punktmenge ist eine 2D-Punktmenge, bei der für jedes achsenausgerichtete Rechteck, das unter Verwendung von zwei Punkten in der Menge als gegenüberliegende Ecken gebildet werden kann, dieses Rechteck mindestens einen anderen Punkt enthält oder berührt. Hier ist eine gleichwertige Definition aus Wikipedia:

Eine Punktmenge gilt als arboral erfüllt, wenn die folgende Eigenschaft gilt: Für jedes Paar von Punkten, die nicht beide auf derselben horizontalen oder vertikalen Linie liegen, gibt es einen dritten Punkt, der in dem von den ersten beiden Punkten aufgespannten Rechteck liegt ( entweder innerhalb oder an der Grenze).

Das folgende Bild zeigt, wie die Rechtecke gebildet werden. Dieser Punktesatz ist nicht bäuerlich erfüllt, da dieses Rechteck mindestens einen weiteren Punkt enthalten muss.

In ASCII-Kunst kann diese Punktmenge wie folgt dargestellt werden:

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

Eine geringfügige Modifikation kann dies arborally befriedigen:

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

Oben sehen Sie, dass alle Rechtecke (von denen es nur ein Rechteck gibt) mindestens drei Punkte enthalten.

Hier ist ein weiteres Beispiel für eine komplexere Punktmenge, die auf dem Baum erfüllt ist:

Für jedes Rechteck, das über zwei Punkte gezeichnet werden kann, enthält dieses Rechteck mindestens einen weiteren Punkt.

Die Herausforderung

Ausgehend von einem rechteckigen Gitter von Punkten (die ich darstelle O) und einem leeren Raum (die ich darstelle .), geben Sie einen Wahrheitswert aus , wenn er vom Baum erfüllt ist, oder einen Falschwert , wenn er nicht erfüllt ist. Das ist Code-Golf.

Zusätzliche Regeln:

• Sie können die Zeichen auswählen Ound .mit jedem anderen Paar druckbarer ASCII-Zeichen austauschen. Geben Sie einfach an, welche Zeichenzuordnung Ihr Programm verwendet.
• Das Gitter wird immer rechteckig sein. Ein abschließender Zeilenumbruch ist zulässig.

Mehr Beispiele

Baum zufrieden:

.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

Nicht zufrieden mit dem Baum:

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

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

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

Schnecken , 29 30 39 Bytes

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

Es funktioniert, indem zwei Seiten des Rechtecks ​​nachgezeichnet werden und dann geprüft wird, ob es ein Quadrat mit einem O gibt, sodass das Fahren in einer geraden Linie vom Quadrat in zwei Hauptrichtungen dazu führt, dass eine Seite des Rechtecks ​​berührt wird.

Gibt das Maximum von 1 und die Rasterfläche aus, wenn die Eingabe "arborally satisfied" ist. sonst 0.

Oracle SQL 11.2, 364 344 Bytes

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 ist das Gitter als Zeichenfolge
: w ist die Breite des Gitters

Gibt keine Zeile als wahr zurück, gibt die Rechtecke, die nicht den Kriterien entsprechen, als falsch zurück

Nicht golfen

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));

Die Ansicht v berechnet die Koordinaten jedes O-Punktes.
Der erste Teil des Minus gibt alle Rechtecke zurück. Die where-Klausel stellt sicher, dass ein Punkt nicht mit sich selbst gepaart werden kann.
Der zweite Teil sucht in jedem Rechteck nach einem dritten Punkt. Dieser Punkt muss eine Koordinate haben, x oder y, die dieser Koordinate für einen der beiden Punkte entspricht, die das Rechteck definieren. Die andere Koordinate dieses dritten Punktes muss in dem Bereich liegen, der durch diese Koordinate für jeden der Punkte begrenzt ist, die das Rechteck definieren.
Der letzte Teil der where-Klausel stellt sicher, dass der dritte Punkt nicht einer der beiden Punkte ist, die das Rechteck definieren.
Wenn alle Rechtecke mindestens einen dritten Punkt haben, entspricht der erste Teil des Minus dem zweiten Teil und die Abfrage gibt nichts zurück.

MATL , 38 Bytes

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

Dies verwendet ein 2D-Zeichen-Array als Eingabe, wobei die Zeilen durch voneinander getrennt sind ;. Das erste Beispiel ist also

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

Die restlichen Testfälle in diesem Format lauten wie folgt.

• Baum zufrieden:

  ['.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']
  

• Nicht bäuerlich zufrieden:

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

Probieren Sie es online! Sie können auch alle Testfälle gleichzeitig überprüfen .

Erläuterung

Der Code erhält zuerst die Koordinaten der Zeichen O in der Eingabe. Dann werden zwei verschachtelte Schleifen verwendet. Die äußere Schleife wählt jeden Punkt P (2-Tupel seiner Koordinaten) aus, vergleicht ihn mit allen Punkten und speichert Punkte, die sich in den beiden Koordinaten von P unterscheiden. Das sind die Punkte, die mit P ein Rechteck bilden können. Nenne sie set R.

Die innere Schleife wählt jeden Punkt T aus R aus und prüft, ob das durch P und T definierte Rechteck mindestens 3 Punkte enthält. Dazu subtrahiert es P von allen Punkten; Das heißt, der Koordinatenursprung wird nach P verschoben. Ein Punkt befindet sich im Rechteck, wenn sich jede seiner durch die entsprechende Koordinate von T geteilten Koordinaten im geschlossenen Intervall [0, 1] befindet.

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 Bytes , 851 Bytes , 657 Bytes

(Neuling 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;

Erklärung (kommentierter Code):

<?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 Bytes

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);}

Erfordert nachgestellte Zeilenumbrüche, was zulässig ist (ohne diese Zeilenumbrüche wäre der Code zwei Byte größer). Ausgänge 0 (nicht bäuerlich erfüllt) oder 1 (bäuerlich erfüllt).