W chińskich warcabach element może się przesuwać, przeskakując nad dowolnym innym elementem lub wykonując sekwencję takich przeskoków. Twoim zadaniem jest znalezienie jak najdłuższej sekwencji skoków.

Wejście

Sekwencja 121 zer lub jedynek, każde reprezentujące miejsce na planszy. Zero oznacza, że ​​miejsce jest puste; jeden oznacza, że ​​miejsce jest zajęte. Pozycje są wymienione od lewej do prawej; od góry do dołu. Na przykład wejście tego ustawienia byłoby

1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Wyjaśnienie:

Najwyższe miejsce zajmuje zielony kawałek, więc pierwszą cyfrą na wejściu jest 1. Drugi rząd ma jedną pustą pozycję, a następnie jedną zajmowaną pozycję, więc 01jest następny. Trzeci rząd jest zajęty, więc 111. Czwarty rząd ma dwa puste i dwa zajęte miejsca (od lewej do prawej), więc 0011. Potem przychodzi pięć 0„S, A 1, i siedem 0” s do następnego wiersza, i tak dalej.

Podobnie jak w tej konfiguracji, róg jest skierowany prosto w górę. Na planszy może znajdować się dowolna liczba elementów (od 1 do 121). Pamiętaj, że elementy o różnych kolorach nie są reprezentowane w różny sposób.

Wynik

Maksymalna długość legalnego skoku przy użyciu dowolnego elementu na planszy. Nie możesz odwiedzić tego samego miejsca więcej niż raz (w tym pozycji początkowej i końcowej). Możesz jednak przeskoczyć nad tym samym kawałkiem więcej niż raz. Jeśli nie ma legalnego przeskoku, wyjście 0. Nie rozważaj, czy istnieje legalny ruch inny niż chmiel.

Na przykład dane wyjściowe do konfiguracji opisanej powyżej to 3.

Dane wejściowe i wyjściowe można realizować za pomocą stdin i stdout, argumentów wiersza poleceń, wywołań funkcji lub dowolnej podobnej metody.

Przypadki testowe

Wejście:

0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Wyjście: 0(nie ma dwóch kawałków obok siebie)

Wejście:

0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Wyjście: 1(początkowa konfiguracja dla jednego gracza w lewym górnym rogu)

Perl, 345 322

Edycja: lekko golfa.

Przydałoby się więcej przypadków testowych, ale na razie wygląda na to, że działa. W razie potrzeby dodam komentarze. Z nowymi liniami i wcięciem dla czytelności:

$_=<>;
$s=2x185;
substr$s,(4,22,unpack'C5(A3)*','(:H[n129148166184202220243262281300')[$i++],0,$_ 
    for unpack A.join A,1..4,13,12,11,10,9..13,4,3,2,1;
$_=$s;
sub f{
    my(@a,%h)=@_;
    $h{$_}++&&return for@a;
    $-+=$#a>$-;
    $s=~/^.{$a[0]}$_/&&f($+[1],@a)
        for map{("(?=.{$_}1.{$_}(0))","(?<=(0).{$_}1.{$_}.)")}0,17,18
}
f$+[0]while/1/g;
print$-

C 262 260

Kod w golfa ( usunięto kod debugowania i niepotrzebne białe znaki. Zmieniono z wprowadzania przez stdin na wprowadzanie za pomocą wiersza poleceń i wykorzystano okazję do zadeklarowania tam zmiennej i. Ostatnia edycja: kod przeniesiono do nawiasów forpętli, aby zapisać dwa średniki).

t[420],j,l,x,y;f(p,d){int z,q,k;for(k=6;k--;t[q]&!t[p+z]?t[q]=0,f(q,d+1),t[q]=1:0)z="AST?-,"[k]-64,q=p+z*2;l=d>l?d:l;}main(int i,char**s){for(i=840;i--;x>3&y>5&x+y<23|x<13&y<15&x+y>13?i>420?t[i-420]=49-s[1][j++]:t[i]||f(i,0):0)x=i%20,y=i/20%21;printf("%d",l);}

Wyjaśnienie

Opiera się to na płycie 20x21, która wygląda tak, początkowo wypełniona zerami podczas uruchamiania programu (ta grafika ASCII została wygenerowana przez zmodyfikowaną wersję programu, a gdy ipętla liczy się w dół, zero znajduje się w prawym dolnym rogu):

....................
....................
...............#....
..............##....
.............###....
............####....
.......#############
.......############.
.......###########..
.......##########...
.......#########....
......##########....
.....###########....
....############....
...#############....
.......####.........
.......###..........
.......##...........
.......#............
....................
....................

Pętla iprzebiega przez tę tablicę dwukrotnie, używając xiy, aby obliczyć, czy kwadrat rzeczywiście należy do szachownicy, czy nie (wymaga to 6 oddzielnych nierówności w xiy).

Jeśli tak, za pierwszym razem runda wypełnia kwadraty, stawiając 0(fałsz) dla 1(zajętego) i 1(prawda) dla 0(niezajętego). Ta inwersja jest ważna, ponieważ wszystkie kwadraty poza zakresem zawierają już 0, co oznacza, że ​​przypominają zajmowane kwadraty i jasne jest, że nie można do nich wskoczyć, bez potrzeby specjalnego sprawdzania.

Za drugim razem, jeśli kwadrat jest zajęty (zawiera 0), wywołuje funkcję, fktóra szuka ruchów.

fwyszukuje rekurencyjnie w 6 możliwych kierunkach zakodowanych przez +/- 1 (poziomo), +/- 20 (pionowo) i +/- 19 (przekątna) zakodowanych w wyrażeniu "AST?-,"[k]-64. Kiedy znajdzie trafienie, ustawia tę komórkę na 0 (zajęte) przed wywołaniem się rekurencyjnie, a następnie ustawia ją z powrotem na 1 (pustą) po zwróceniu funkcji. Wartość komórki musi zostać zmieniona przed wywołaniem rekurencyjnym, aby zapobiec wskakiwaniu do tej komórki więcej niż raz.

Nieskluczony kod

char s[999];                           //input string.
t[420],i,j,l,x,y;                      //t=board. i=board counter, j=input counter. l=length of longest hop found so far.

f(p,d){                                //p=position, d= recursion depth.
  //printf("%d,%d ",p,d);              //debug code: uncomment to show the nodes visited.
  int k,z,q;                           //k=counter,z=displacement,q=destination
  for(k=6;k--;)                        //for each direction
    z="AST?-,"[k]-64,                  //z=direction
    q=p+z*2,                           //q=destination cell
    t[q]&!t[p+z]?                      //if destination cell is empty (and not out of bounds) and intervening cell is full
      t[q]=0,f(q,d+1),t[q]=1           //mark destination cell as full, recurse, then mark it as empty again.
      :0;
  l=d>l?d:l;                           //if d exceeds the max recorded recursion depth, update l
}

main(){
  gets(s);                             //get input
  for(i=840;i--;)                      //cycle twice through t
    x=i%20,                            //get x
    y=i/20%21,                         //and y coordinates
    x>3&y>5&x+y<23|x<13&y<15&x+y>13?   //if they are in the bounds of the board
      i>420?
        t[i-420]=49-s[j++]             //first time through the array put 0 for a 1 and a 1 for a 0 ('1'=ASCII49)
        :t[i]||f(i,0)                  //second time, if t[i]=0,call f(). 
       //,puts("")                     //puts() formats debug output to 1 line per in-bounds cell of the board
      :0;
  printf("%d",l);                      //print output
}