Suponga que tiene un $m \times n$ que puede contener valores booleanos. Inicialmente está vacía, llena de $0$ s.
La única manera de cambiar la matriz es suministrando dos pares de coordenadas, definiendo un área rectangular dentro de la matriz; cada bit en esa área se voltea. Un primer movimiento de este tipo te daría algo así:
(No estoy seguro de la notación ideal para eso, pero es (2,4)-(8,15) según mis cálculos, definiendo las coordenadas de las esquinas inclusivas opuestas).
Sin embargo, observe lo que sucede cuando juega una segunda jugada, (4,4)-(6,17) :
Al ser un exclusivo-o, los bits del medio vuelven a $0$ mientras que el voladizo de la derecha pasa a $1$ . Ingenuamente, uno podría mirar esta segunda imagen y concluir que eran necesarios tres movimientos para alcanzar esa configuración si se partía de todos los ceros, un movimiento por cada rectángulo. Como hemos visto, esto se hizo con sólo dos.
Este es un ejemplo sencillo, pero cuando se combinan incluso un puñado de movimientos superpuestos, se aparece a ser extremadamente difícil de desentrañar. Si no me equivoco, esto es no el caso de una matriz unidimensional análoga, donde es sencillo derivar la serie óptima de movimientos (es decir, XORing segmentos de línea) para recrear una configuración en $O(n)$ tiempo. Esto se debe a que cada par adyacente desigual implica un segmento XOR con un punto final entre ese par.
El objetivo es calcular el número mínimo de movimientos necesarios para recrear cualquier configuración final, partiendo de una matriz vacía. Consideraré que mi pregunta ha sido respondida si alguien puede decirme si se conoce un algoritmo eficiente para esto o algo similar, puede esbozar uno él mismo, o puede dar una opinión informada sobre por qué es probable que exista tal algoritmo o no. Por algoritmo eficiente, me refiero a uno que se ejecute en tiempo polinómico en el caso general.
(Me doy cuenta de que esto es posiblemente una pregunta de CS, pero lo intento aquí primero).
Confirmada la buena solución de RobPratt.
Para futuras referencias, este código de Mathematica ejecutará una prueba con parámetros aleatorios y te dará un resultado como el de la captura de pantalla de abajo.
a[i_, j_, i1_, j1_, i2_, j2_] := Boole[i1 <= i <= i2 && j1 <= j <= j2]
x[coords_] := Boole@MemberQ[rects, coords]
m = Table[0, 9, 13];
randrect := Module[{x1, y1, x2, y2},
{x1, x2} = Sort[RandomInteger[{1, Length@First@m}, 2]];
{y1, y2} = Sort[RandomInteger[{1, Length@m}, 2]];
{y1, x1, y2, x2}
];
rects = Table[randrect, RandomInteger[{1, 13}]]
Do[
m[[rect[[1]] ;; rect[[3]], rect[[2]] ;; rect[[4]]]] =
1 - m[[rect[[1]] ;; rect[[3]], rect[[2]] ;; rect[[4]]]];
, {rect, rects}];
ArrayPlot[m, Mesh -> True]
t = Minimize[{Sum[
x[{i1, j1, i2, j2}], {i2, Length@m}, {j2, Length@First@m}, {i1,
i2}, {j1, j2}],
And @@ Flatten@
Table[y[i, j] \[Element] Integers && y[i, j] >= 0 &&
Sum[a[i, j, i1, j1, i2, j2] x[{i1, j1, i2, j2}], {i2,
Length@m}, {j2, Length@First@m}, {i1, i2}, {j1, j2}] ==
2 y[i, j] + m[[i, j]], {i, Length@m}, {j, Length@First@m}]},
Flatten[Table[y[i, j], {i, Length@m}, {j, Length@First@m}]]];
TextGrid[{{Length@rects, "rectangles drawn"}, {First[t],
"rectangles calculated"}}]
ArrayPlot[Partition[Last /@ Last@t, Length@First@m], Mesh -> True]Ejemplo de salida:
