Wprowadzenie

Niedawno zaakceptowałeś ofertę pracy w Pretty Good Software Company. Jesteś całkiem zadowolony z wielkości swojego biura, ale czy masz największe biuro? Trudno to odróżnić od spojrzenia na biura współpracowników, kiedy wpadniesz. Jedynym sposobem na rozwiązanie tego problemu jest sprawdzenie planów budynku ...

Twoje zadanie

Napisz program, skrypt lub funkcję, która bierze plan piętra dla twojego budynku i wskazuje, czy twoje biuro jest największe. Plan piętra jest łatwy do odczytania, ponieważ budynek ma kwadrat n na n .

Dane wejściowe będą składały się z n + 1 \n -niepełnionych linii. Pierwszy wiersz będzie miał na sobie liczbę n . Kolejne n wierszy będzie planem budynku. Prosty przykładowy wpis:

6
......
.  . .
.X . .
.  . .
.  . .
......

Zasady dotyczące planu piętra są następujące:

• .(ASCII 46) Będzie używany do reprezentowania ścian. (Spacja [ASCII 32]) zostanie użyta do przedstawienia otwartej przestrzeni.
• Jesteś reprezentowany przez X(ASCII 88). Jesteś w swoim biurze
• Plansem będzie n linii, każda z n znakami.
• Budynek jest całkowicie otoczony ścianami ze wszystkich stron. Oznacza to, że drugi wiersz danych wejściowych (pierwszy wiersz planu piętra) i ostatni wiersz danych wejściowych będą .s. Oznacza to również, że pierwszymi i ostatnimi znakami każdej linii planu piętra będą litery .s.
• Wielkość biura jest definiowana jako suma sąsiadujących ze sobą przestrzeni (sąsiadujących, przesuwając się w 4 kierunkach, N, S, E, W, bez przechodzenia przez ścianę).
• Dla celów wielkości biura X reprezentujący cię liczy się jako (otwarta przestrzeń)
• 4 <= n <= 80

Powinieneś wypisać, czy twoje biuro jest ściśle większe niż wszystkie inne biura. Wynikiem może być wszystko, co jednoznacznie oznacza Prawdę lub Fałsz w wybranym języku programowania i jest zgodne ze standardowymi konwencjami zero, zero i puste, oznaczające fałsz. Prawda oznacza, że ​​twoje biuro jest ściśle największe.

Przykładowe dane wyjściowe dla powyższego wejścia:

1

Ponieważ twoje biuro ma 8 stóp kwadratowych, a jedyne inne biuro ma 4 stopy kwadratowe.

Wytyczne I / O

• Dane wejściowe można odczytać ze standardowego wejścia, a odpowiedź na standardowe wyjście.

Lub

• Dane wejściowe mogą być argumentem pojedynczego ciągu funkcji, a odpowiedzią może być wartość zwracana przez tę funkcję.

FAQ

• Cały budynek składa się ze ścian i biur.
• Budynek ma tylko jedno piętro
• Na wejściu jest gwarantowane X, ale nie ma żadnych spacji. Możesz mieć biuro 1x1, a reszta budynku to ściany (masz największe biuro! Hura!).

Inny przykład

10
..........
.   .  . .
.  .   . .
.  .   . .
. ..   . .
..       .
..........
.      X .
.        .
..........

Tutaj są 3 biura, twoje biuro południowe jest prostokątne, biuro północno-zachodnie to trójkąt (ish), a biuro północno-wschodnie jest dziwnie zniekształcone, ale większe niż twoje. Wynik powinien być fałszywy.

Wyzwanie polega na napisaniu najkrótszego kodu, udanej gry w golfa !

Ruby 2.0, 133 znaki

Współpraca z @Ventero. Zawsze dobry znak, gdy zaczyna łamać zakreślacz składni!

Jest to rekurencyjne rozwiązanie wypełniania powodzi. Odczytuje ze STDIN i wysyła do STDOUT:

f=->*a{a.product([~n=$_.to_i,-1,1,n+1]){|p,d|a|=[p]if$_[p+=d]<?.}!=a ?f[*a]:a.size}
gets(p).scan(/ /){$*<<f[$`.size]}
p$*.max<f[~/X/]

Zobacz, jak działa na Ideone .

GolfScript (85 bajtów)

n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%{{{.2$*!!{[\]$-1=.}*}*]}%zip}N*[]*0-:A{.N=A@-,2*+}$0=N=

Demo online

Zawiera trzy sekcje:

1. Początkowa transformacja wejściowa, która tworzy tablicę 2D przy użyciu 0do reprezentowania ściany N(całkowitej liczby komórek) do reprezentowania mojej pozycji początkowej i wyraźnej liczby między nimi dla każdej otwartej przestrzeni.

   n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%
   

2. Wypełnienie powodziowe.

   {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
   

3. Ostateczne liczenie. Wykorzystuje wariant na końcówce dla najbardziej powszechnego elementu w tablicy , dodając przerywacz remisu, który jest tendencyjny N.

   []*0-:A{.N=A@-,2*+}$0=N=
   

JavaScript (E6) 155 292

F=(a,n=parseInt(a)+1,x,y)=>[...a].map((t,p,b,e=0,f=p=>b[p]==' '|(b[p]=='X'&&(e=1))&&(b[p]=1,1+f(p+n)+f(p-n)+f(p+1)+f(p-1)))=>(t=f(p))&&e?y=t:t<x?0:x=t)|y>x

Wersja podstawowa bez golfisty

F=a=>
{
  var k, max=0, my=0, k=1, t, n = parseInt(a)+1;
  [...a].forEach( 
    (e,p,b) =>
    {
       x=0;
       F=p=>
       {
          var r = 1;
          if (b[p] == 'X') x = 1;
          else if (b[p] != ' ') return 0;
          b[p] = k;
          [n,1,-n,-1].forEach(q => r+=F(q+p));
          return r;
       }
       t = F(p);
       if (t) {
          if (x) my = t;
          if (t > max) max = t;
          k++;
          console.log(b.join(''));
       }    
    }
  )
  return my >= max
}

Test

Konsola JavaScript w Firefoksie

F('6\n......\n. . .\n.X . .\n. . .\n. . .\n......')

1

F('10\n..........\n. . . .\n. . . .\n. . . .\n. .. . .\n.. .\n..........\n. X .\n. .\n..........\n')

0

C #, 444 372 / (342 dzięki HackerCow) bajtów

Raczej kiepski wynik i spóźniony na imprezę, ale wydaje się, że działa. Wyjście 1, gdy masz jedno największe biuro, 0, gdy nie. Nie byłem jeszcze zbyt skomplikowany w golfa. Działa poprzez budowanie rozłącznych zestawów z wejścia (pierwsza pętla), obliczanie wielkości każdego zestawu (druga pętla), a następnie sprawdzanie, czy mój zestaw jest największy (trzecia pętla).

Dostępne są dwie wersje, jedna to program, który można skompilować, tat przyjmuje dane z wiersza poleceń, druga to tylko funkcja, która oczekuje ciągu jako danych wejściowych i zwraca wartość int jako wynik (i jest tylko przerobioną kopią pierwszej) - nie potrzebuje żadnych klauzul używających itp., powinien być w stanie umieścić go w dowolnym miejscu i będzie działać.

Program 372 bajtów :

using System;class P{static void Main(){int s=int.Parse(Console.ReadLine()),e=0,d=s*s,a=d;int[]t=new int[d],r=new int[d];Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;T=v=>t[v]!=v?T(t[v]):v;for(;a>0;)foreach(var m in Console.ReadLine()){a--;if(m!=46){t[a]=a;e=m>46?a:e;k(a+s);k(a+1);}}for(a=d;a-->2;)r[T(a)]++;for(;d-->1;)a=d!=T(e)&&r[d]>=r[T(e)]?0:a;Console.WriteLine(a);}}

Funkcja 342 bajtów :

static int F(string g){var b=g.Split('\n');int s=int.Parse(b[0]),e=0,d=s*s,a=d;int[]t=new int[d],r=new int[d];System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;T=v=>t[v]!=v?T(t[v]):v;for(;a>0;)foreach(var m in b[a/s]){a--;if(m!=46){t[a]=a;e=m>46?a:e;k(a+s);k(a+1);}}for(a=d;a-->2;)r[T(a)]++;for(;d-->1;)a=d!=T(e)&&r[d]>=r[T(e)]?0:a;return a;

Mniej golfa:

using System;

class P
{
    static int F(string g)
    {
        var b=g.Split('\n');
        int s=int.Parse(b[0]),e=0,d=s*s,a=d;
        int[]t=new int[d],r=new int[d];
        System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;
        T=v=>t[v]!=v?T(t[v]):v;

        for(;a>0;)
            foreach(var m in b[a/s])
            {
                a--;
                if(m!=46)
                {
                    t[a]=a;
                    e=m>46?a:e;
                    k(a+s);
                    k(a+1);
                }
            }
        for(a=d;a-->2;)
            r[T(a)]++;
        for(;d-->1;)
            a=d!=T(e)&&r[d]>=r[T(e)]?0:a;
        return a;
    }

    static void Main()
    {
        /* F() test
        var s=Console.ReadLine();
        int i=int.Parse(s);
        for(;i-->0;)
        {
            s+="\n"+Console.ReadLine();
        }
        Console.WriteLine(F(s));*/


        int s=int.Parse(Console.ReadLine()),e=0,d=s*s,a=d;
        int[]t=new int[d],r=new int[d];
        Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;
        T=v=>t[v]!=v?T(t[v]):v;

        for(;a>0;)
            foreach(var m in Console.ReadLine())
            {
                a--;
                if(m!=46)
                {
                    t[a]=a;
                    e=m>46?a:e;
                    k(a+s);
                    k(a+1);
                }
            }
        for(a=d;a-->2;)
            r[T(a)]++;
        for(;d-->1;)
            a=d!=T(e)&&r[d]>=r[T(e)]?0:a;
        Console.WriteLine(a);
    }
}

CJam, 106 bajtów

Inne podejście do wypełniania powodziowego. Chociaż sprawia, że ​​dłużej ...

liqN-'Xs0aer\_:L*{_A=' ={[AAL-A(]1$f=$:D1=Sc<{D2<(aer}*D0=_' ={T):T}@?A\t}*}fAT),\f{\a/,}_$W%_2<~>@@0=#0=&

Wypróbuj tutaj

Python 2 - 258 bajtów

r=range;h=input();m="".join(raw_input()for x in r(h))
w=len(m)/h;n=0;f=[x!='.'for x in m]
for i in r(w*h):
 if f[i]:
    a=[i];M=s=0
    while a:
     i=a.pop();s+=1;M|=m[i]=='X';f[i]=0
     for j in(i-1,i+1,i-w,i+w):a+=[[],[j]][f[j]]
    n=max(s,n)
    if M:A=s
print A==n

używa wejściowego stdin

Uwaga: pierwsze ifjest wcięte pojedynczą spacją, inne wcięte linie albo używają pojedynczego znaku tabulacji, albo tabulacji i spacji.

J: 150 121 bajtów

(({~[:($<@#:I.@,)p=1:)=([:({.@#~(=>./))/@|:@}.({.,#)/.~@,))(>./**@{.)@(((,|."1)0,.0 _1 1)&|.)^:_[(*i.@:$)2>p=:' X'i.];._2

Edycja : idi compbyły absurdalnie skomplikowane i powolne. Teraz przesuwa mapę 4 razy, zamiast skanować ją za pomocą okna 3x3 za pomocą cut( ;.).

Bierze jako argument plan jako ciąg znaków. Wyjaśniono poniżej:

    s =: 0 :0
..........
.   .  . .
.  .   . .
.  .   . .
. ..   . .
..       .
..........
.      X .
.        .
..........
)
p=:' X' i. ];._2 s                NB. 0 where space, 1 where X, 2 where wall
id=:*i.@:$2>p                     NB. Give indices (>0) to each space
comp =: (>./ * *@{.)@shift^:_@id  NB. 4 connected neighbor using shift
  shift =: ((,|."1)0,.0 _1 1)&|.  NB. generate 4 shifts
size=:|:}.({.,#)/.~ , comp        NB. compute sizes of all components
NB. (consider that wall is always the first, so ditch the wall surface with }.)
NB. is the component where X is the one with the maximal size?
i=: $<@#:I.@,                     NB. find index where argument is 1
(comp {~ i p=1:) = {.((=>./)@{: # {.) size

NB. golfed:
(({~[:($<@#:I.@,)p=1:)=([:({.@#~(=>./))/@|:@}.({.,#)/.~@,))(>./**@{.)@(((,|."1)0,.0 _1 1)&|.)^:_[(*i.@:$)2>p=:' X'i.];._2 s
0

Python 2 - 378 bajtów

Łał. Jestem poza treningiem.

def t(l,x,y,m,c=' '):
 if l[y][x]==c:l[y][x]=m;l=t(l,x-1,y,m);l=t(l,x+1,y,m);l=t(l,x,y-1,m);l=t(l,x,y+1,m)
 return l
def f(s):
 l=s.split('\n');r=range(int(l.pop(0)));l=map(list,l);n=1
 for y in r:
    for x in r:l=t(l,x,y,*'0X')
 for y in r:
  for x in r:
    if l[y][x]==' ':l=t(l,x,y,`n`);n+=1
 u=sum(l,[]).count;o=sorted(map(u,map(str,range(n))));return n<2or u('0')==o[-1]!=o[-2]

To jest odpowiedź funkcji, ale zanieczyszcza globalną przestrzeń nazw. Jeśli jest to nie do przyjęcia, można to naprawić kosztem 1 bajtu:

• Dodaj spację na początku wiersza 1 (+1)
• Zastąp spację na początku wiersza 2 i 3 znakiem tabulacji (+0)
• Przenieś linię 4 na początek (+0)

Napisałem całe długie wyjaśnienie, ale najwyraźniej nie zapisało się to właściwie i nie robię tego ponownie, Lmao