Sebuah set point arborally puas adalah seperangkat 2D poin sehingga, untuk setiap persegi panjang sumbu-blok yang dapat dibentuk dengan menggunakan dua poin di set sebagai sudut yang berlawanan, yang persegi panjang berisi atau sentuhan setidaknya satu titik lainnya. Berikut ini definisi yang setara dari Wikipedia:

Set poin dikatakan puas secara arboral jika properti berikut ini berlaku: untuk setiap pasangan poin yang tidak keduanya terletak pada garis horizontal atau vertikal yang sama, ada titik ketiga yang terletak di dalam persegi panjang yang direntang oleh dua titik pertama ( baik di dalam atau di batas).

Gambar berikut menggambarkan bagaimana persegi panjang terbentuk. Set titik ini TIDAK puas secara arboral karena persegi panjang ini perlu mengandung setidaknya satu titik lagi.

Dalam seni ASCII, set poin ini dapat direpresentasikan sebagai:

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

Sedikit modifikasi dapat membuat ini cukup memuaskan:

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

Di atas, Anda dapat melihat bahwa semua persegi panjang (yang hanya ada satu) mengandung setidaknya tiga poin.

Berikut adalah contoh lain dari set point yang lebih kompleks yang dipuaskan secara arborally:

Untuk setiap persegi panjang yang dapat ditarik yang mencakup dua titik, persegi panjang itu mengandung setidaknya satu titik lainnya.

Tantangan

Mengingat kotak persegi panjang poin (yang saya mewakili dengan O) dan ruang kosong (yang saya mewakili dengan .), output truthy nilai jika arborally puas, atau falsey nilai jika tidak. Ini adalah kode-golf.

Aturan tambahan:

• Anda dapat memilih untuk memiliki karakter Odan .bertukar dengan pasangan karakter ASCII yang dapat dicetak lainnya. Cukup tentukan pemetaan karakter yang digunakan program Anda.
• Grid akan selalu berbentuk persegi panjang. Baris baru tambahan diperbolehkan.

Lebih banyak contoh

Puas puas:

.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

Tidak Puas Arborally:

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

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

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

Siput , 29 30 39 byte

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

Ini bekerja dengan menelusuri 2 sisi dari persegi panjang, dan kemudian memeriksa apakah ada beberapa persegi yang mengandung O sehingga bepergian dalam garis lurus dari persegi di 2 arah mata angin akan menghasilkan memukul sisi persegi panjang.

Mencetak maksimal 1 dan area kisi-kisi jika input "memuaskan secara arbor"; jika tidak 0.

Oracle SQL 11.2, 364 344 byte

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 adalah kisi sebagai string
: w adalah lebar kisi

Mengembalikan tidak ada garis sebagai kebenaran, mengembalikan persegi panjang yang tidak cocok dengan kriteria sebagai falsy

Tidak bermain golf

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

Tampilan v menghitung koordinat dari setiap titik O.
Bagian pertama dari minus mengembalikan semua persegi panjang, di mana klausa memastikan bahwa suatu titik tidak dapat dipasangkan dengan dirinya sendiri.
Bagian kedua mencari titik ketiga di setiap persegi panjang. Titik itu perlu memiliki satu koordinat, x atau y, sama dengan koordinat itu untuk salah satu dari dua titik yang mendefinisikan persegi panjang. Koordinat lain dari titik ketiga harus berada dalam kisaran yang dibatasi oleh koordinat tersebut untuk masing-masing poin yang menentukan persegi panjang.
Bagian terakhir dari klausa where memastikan bahwa titik ketiga bukan salah satu dari dua titik yang menentukan persegi panjang.
Jika semua persegi panjang memiliki setidaknya titik ketiga maka bagian pertama minus sama dengan bagian kedua dan kueri tidak mengembalikan apa pun.

MATL , 38 byte

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

Ini menggunakan array char 2D sebagai input, dengan baris dipisahkan oleh ;. Jadi contoh pertama adalah

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

Sisa dari kasus uji dalam format ini adalah sebagai berikut.

• Puas puas:

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

• Tidak puas puas:

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

Cobalah online! Anda juga dapat memverifikasi semua kasus uji sekaligus .

Penjelasan

Kode pertama kali mendapatkan koordinat karakter Odalam input. Kemudian menggunakan dua loop bersarang. Loop luar mengambil setiap titik P (2-tupel koordinatnya), membandingkan dengan semua titik, dan membuat titik-titik yang berbeda dari P dalam dua koordinat. Itu adalah poin dari yang bisa membentuk persegi panjang dengan P. Sebut saja set R.

Loop dalam mengambil setiap titik T dari R, dan memeriksa apakah persegi panjang yang ditentukan oleh P dan T mencakup setidaknya 3 poin. Untuk melakukan itu, ia mengurangi P dari semua poin; yaitu, memindahkan asal koordinat ke P. Titik berada dalam persegi panjang jika masing-masing koordinat dibagi dengan koordinat T yang sesuai dalam interval tertutup [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 byte , 851 byte , 657 byte

(php pemula)

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

penjelasan (kode komentar):

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

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

Membutuhkan trailing newline, yang diizinkan (tanpa baris baru, kodenya akan dua byte lebih besar). Output 0 (tidak puas arborally) atau 1 (puas arborally).