En las Damas chinas , una pieza puede moverse saltando sobre cualquier otra pieza, o haciendo una secuencia de tales saltos. Su tarea es encontrar la secuencia más larga posible de saltos.

Entrada

Una secuencia de 121 ceros o unos, cada uno representando un lugar en un tablero. Un cero significa que el lugar está vacío; uno significa que el lugar está ocupado. Las posiciones se enumeran de izquierda a derecha; de arriba hacia abajo. Por ejemplo, la entrada de esta configuración sería

1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Explicación:

El lugar superior está ocupado por una pieza verde, por lo que el primer dígito en la entrada es 1. La segunda fila tiene una posición vacía y luego una posición ocupada, entonces 01viene la siguiente. La tercera fila está ocupada, entonces 111. La cuarta fila tiene dos espacios vacíos y dos espacios ocupados (de izquierda a derecha), entonces 0011. Luego vienen cinco 0, a 1y siete 0para la siguiente fila, y así sucesivamente.

Al igual que en esa configuración, hay una esquina apuntando hacia arriba. Puede haber cualquier cantidad de piezas en el tablero (de 1 a 121). Tenga en cuenta que las piezas de diferentes colores no se representan de manera diferente.

Salida

La longitud máxima de un salto legal, usando cualquier pieza en el tablero. No puede visitar el mismo lugar más de una vez (incluidas las posiciones inicial y final). Sin embargo, puede saltar sobre la misma pieza más de una vez. Si no hay salto legal, salida 0. No considere si existe un movimiento legal sin salto.

Por ejemplo, la salida a la configuración descrita anteriormente es 3.

La entrada y salida se pueden realizar a través de stdin y stdout, a través de argumentos de línea de comandos, a través de llamadas a funciones o cualquier método similar.

Casos de prueba

Entrada:

0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Salida: 0(no hay dos piezas una al lado de la otra)

Entrada:

0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Salida: 1(configuración inicial para un jugador en la esquina superior izquierda)

Perl, 345 322

Editar: golf, un poco.

Sería bueno tener más casos de prueba, pero por ahora parece que funciona. Agregaré comentarios más tarde si es necesario. Con nuevas líneas y sangría para facilitar la lectura:

$_=<>;
$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

Código de golf ( código de depuración y espacios en blanco innecesarios eliminados. Cambió de entrada a través de stdin a entrada a través de la línea de comando, y aprovechó la oportunidad para declarar la variable i allí. Última edición: el código se movió entre paréntesis de forbucles para guardar dos puntos y coma).

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

Explicación

Esto se basa en un tablero de 20x21 que se ve así, inicialmente lleno de ceros cuando se inicia el programa (este arte ASCII fue generado por una versión modificada del programa, y ​​como el ibucle cuenta hacia abajo, el cero está en la esquina inferior derecha):

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

El bucle irecorre este tablero dos veces, usando x e y para calcular si un cuadrado pertenece realmente al tablero de ajedrez o no (esto requiere 6 desigualdades separadas en x e y).

Si lo hace, la primera vez llena los cuadrados, colocando un 0(falso) para un 1(ocupado) y un 1(verdadero) para un0 (desocupado). Esta inversión es importante, porque todos los cuadrados fuera de límites ya contienen un 0, lo que significa que se parecen a los cuadrados ocupados y está claro que no se pueden saltar, sin la necesidad de una verificación específica.

La segunda ronda, si el cuadrado está ocupado (contiene 0), llama a la función fque busca los movimientos.

fbusca recursivamente en las 6 direcciones posibles codificadas por +/- 1 (horizontal), +/- 20 (vertical) y +/- 19 (diagonal) codificadas en la expresión "AST?-,"[k]-64. Cuando encuentra un hit, establece esa celda en 0 (ocupada) antes de llamarse recursivamente, luego la vuelve a establecer en 1 (vacía) cuando se devuelve la función. El valor de la celda debe cambiarse antes de la llamada recursiva para evitar saltar en esa celda más de una vez.

Código sin golf

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
}